W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
Combinatorial optimization can be described as the problem of finding a feasible subset that maximizes a objective function. The paper discusses combinatorial optimization problems, where for each dimension the set of feasible subsets is fixed. It is demonstrated that in some cases fixing the structure makes the problem easier, whereas in general the problem remains NP-complete.
W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
Matthew A Grayson
Journal of Complexity
Naga Ayachitula, Melissa Buco, et al.
SCC 2007
Jianke Yang, Robin Walters, et al.
ICML 2023