2019/01/09 by Mikhail V. Batsyn, Mikhail Batsyn, Ekaterina Batsyna +6
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #Optimization and Packing Problems #cs.CC
paper · pdf · doi:10.48550/arxiv.1901.02778
9 pages
arxiv created 2019/01/09 · openalex publication_date 2019/01/09 · arxiv updated 2019/01/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the current paper we provide a proof of NP-completeness for the CFP problem with the fractional grouping efficacy objective. For this purpose we first consider the CFP with the linear objective minimizing the total number of exceptions and voids. Following the ideas of Pinheiro et al. (2016) we show that it is equivalent to the Bicluster Graph Editing Problem (BGEP), which is known to be NP-complete (Amit, 2004). Then we suggest a reduction of the CFP problem with the linear objective function to the CFP with the grouping efficacy objective.