期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2014
卷号：2014
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We give an exact algorithm for the 0-1 Integer Linear Programming problem with a linear number of constraints that improves over exhaustive search by an exponential factor. Specifically, our algorithm runs in time 2(1−poly(1c))n where n is thenumber of variables and cn is the number of constraints. The key idea for the algorithm is a reduction to the Vector Domination problem and a new algorithm for that subproblem.
