
Previous Article
Fouriersplitting method for solving hyperbolic LQR problems
 NACO Home
 This Issue
 Next Article
Linearlygrowing reductions of Karp's 21 NPcomplete problems
1.  School of Computer Science, Engineering and Mathematics, Flinders University, Bedford Park, SA 5042, Australia 
2.  Defence Science and Technology Group, Canberra, ACT 2600, Australia 
We address the question of whether it may be worthwhile to convert certain, now classical, NPcomplete problems to one of a smaller number of kernel NPcomplete problems. In particular, we show that Karp's classical set of 21 NPcomplete problems contains a kernel subset of six problems with the property that each problem in the larger set can be converted to one of these six problems with only linear growth in problem size. This finding has potential applications in optimisation theory because the kernel subset includes 01 integer programming, job sequencing and undirected Hamiltonian cycle problems.
References:
show all references
The reviewing process was handled by A. Baghirov
References:
[1] 
René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in twostage stochastic mixedinteger programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 363384. doi: 10.3934/jimo.2008.4.363 
[2] 
Zhiguo Feng, KaFai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 557566. doi: 10.3934/jimo.2014.10.557 
[3] 
Mahmoud Ameri, Armin Jarrahi. An executive model for networklevel pavement maintenance and rehabilitation planning based on linear integer programming. Journal of Industrial and Management Optimization, 2020, 16 (2) : 795811. doi: 10.3934/jimo.2018179 
[4] 
Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixedinteger linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial and Management Optimization, 2017, 13 (4) : 16011623. doi: 10.3934/jimo.2017009 
[5] 
Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probebased traffic monitoring systems using mixed integer linear programming. Networks and Heterogeneous Media, 2013, 8 (3) : 783802. doi: 10.3934/nhm.2013.8.783 
[6] 
Mahdi Roozbeh, Saman Babaie–Kafaki, Zohre Aminifard. Two penalized mixed–integer nonlinear programming approaches to tackle multicollinearity and outliers effects in linear regression models. Journal of Industrial and Management Optimization, 2021, 17 (6) : 34753491. doi: 10.3934/jimo.2020128 
[7] 
Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the kerror linear complexity of 2^{n}periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429444. doi: 10.3934/amc.2017036 
[8] 
Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353362. doi: 10.3934/jimo.2008.4.353 
[9] 
Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial and Management Optimization, 2011, 7 (4) : 10271039. doi: 10.3934/jimo.2011.7.1027 
[10] 
Zhenbo Wang, ShuCherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multiinteger quadratic programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 213225. doi: 10.3934/jimo.2008.4.213 
[11] 
Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial and Management Optimization, 2011, 7 (1) : 6778. doi: 10.3934/jimo.2011.7.67 
[12] 
Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 117131. doi: 10.3934/jimo.2019102 
[13] 
Mohamed A. Tawhid, Ahmed F. Ali. A simplex grey wolf optimizer for solving integer programming and minimax problems. Numerical Algebra, Control and Optimization, 2017, 7 (3) : 301323. doi: 10.3934/naco.2017020 
[14] 
Charles Fefferman. Interpolation by linear programming I. Discrete and Continuous Dynamical Systems, 2011, 30 (2) : 477492. doi: 10.3934/dcds.2011.30.477 
[15] 
Dandan Wang, Xiwang Cao, Gaojun Luo. A class of linear codes and their complete weight enumerators. Advances in Mathematics of Communications, 2021, 15 (1) : 7397. doi: 10.3934/amc.2020044 
[16] 
Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323344. doi: 10.3934/amc.2010.4.323 
[17] 
Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 115132. doi: 10.3934/naco.2014.4.115 
[18] 
Alina Ostafe, Igor E. Shparlinski, Arne Winterhof. On the generalized joint linear complexity profile of a class of nonlinear pseudorandom multisequences. Advances in Mathematics of Communications, 2010, 4 (3) : 369379. doi: 10.3934/amc.2010.4.369 
[19] 
Hongwei Jiao, Junqiao Ma, Peiping Shen, Yongjian Qiu. Effective algorithm and computational complexity for solving sum of linear ratios problem. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022135 
[20] 
Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193206. doi: 10.3934/naco.2012.2.193 
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]