0-1 Integer Linear Programming with a Linear Number of Constraints

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-\text{poly}(1/c))n}$ where n is the number 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.

• Publication year

  2014

• Venue

  Electron. Colloquium Comput. Complex.

• Publication date

  2014-01-21

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1401.5512
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• New algorithms and lower bounds for circuits with linear threshold gates

  2014cited by this paper
• A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits

  2012cited by this paper
• LINEAR INTEGER PROGRAMMING METHODS AND APPROACHES-A SURVEY

  2011cited by this paper
• A new algorithm for optimal 2-constraint satisfaction and its implications

  2005influential reference
• An algorithm for the satisfiability problem of formulas in conjunctive normal form

  2005influential reference
• All-Pairs Shortest Paths with Real Weights in O(n3/log n) Time

  2005cited by this paper
• Complexity of k-SAT

  1999cited by this paper
• Which problems have strongly exponential complexity?

  1998cited by this paper
• Multidimensional divide-and-conquer

  1980cited by this paper

• Analytically Determining the Robustness of Binarized Neural Networks

  2024cites this paper
• Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming

  2023cites this paper
• Application of ant colony optimization metaheuristic on set covering problems

  2022cites this paper
• An Optimization Model for Ordering and Transporting Raw Materials by Manufacturers Based on Linear Programming

  2022cites this paper
• The Fine-Grained Complexity of Multi-Dimensional Ordering Properties

  2022cites this paper
• Enriching Data Imputation under Similarity Rule Constraints

  2020cites this paper
• Continuous-Time Systems for Solving 0-1 Integer Linear Programming Feasibility Problems

  2019cites this paper
• Green Spectrum Assignment in Secure Cloud Radio Network with Cluster Formation

  2019cites this paper
• Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression

  2019cites this paper
• Bridging between 0/1 and linear programming via random walks

  2019cites this paper
• Conception d'un solveur matériel spécifique pour la résolution rapide du problème SAT appliqué à l'évaluation du risque en génie industriel

  2018cites this paper
• Flexible distributed control plane deployment

  2018cites this paper
• A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates

  2018cites this paper
• PREPRINT Flexible distributed control plane deployment

  2018cites this paper
• Tighter Connections Between Formula-SAT and Shaving Logs

  2018cites this paper
• Scheduling Tool for the Nevada Test and Training Range

  2018cites this paper
• Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back

  2017influential citation
• On the Fine-grained Complexity of One-Dimensional Dynamic Programming

  2017cites this paper
• Faster space-efficient algorithms for subset sum and k-sum

  2017cites this paper
• Improved Subquadratic 3SUM

  2017cites this paper
• Asymmetric Transmission Game for Interference Coordination in Wireless Ad-Hoc Relay Networks

  2017cites this paper
• Mathematical programming for server consolidation in cloud data centers

  2017cites this paper
• Deterministic APSP, Orthogonal Vectors, and More

  2016cites this paper
• Finding Large Set Covers Faster via the Representation Method

  2016cites this paper
• Green Distributed Storage Using Energy Harvesting Nodes

  2016cites this paper
• Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related Problems

  2016cites this paper
• Mathematik in den Naturwissenschaften Leipzig From Typical Sequences to Typical Genotypes

  2016cites this paper
• More Applications of the Polynomial Method to Algorithm Design

  2015cites this paper
• On Maximal Layers of Random Orders on Maximal Layers of Random Orders

  2015cites this paper
• Quadratic-Time Hardness of LCS and other Sequence Similarity Measures

  2015cites this paper
• Data-Intensive Mobile Cloud Computing

  2015cites this paper
• An Improved Combinatorial Algorithm for Boolean Matrix Multiplication

  2015cites this paper
• On Maximal Layers Of Random Orders

  2015cites this paper
• Computing Maximal Layers of Points in Ef(n)

  2015cites this paper
• Tight Hardness Results for LCS and Other Sequence Similarity Measures

  2015cites this paper
• Speeding up the Four Russians Algorithm by About One More Logarithmic Factor

  2015cites this paper
• Threesomes, Degenerates, and Love Triangles

  2014cites this paper
• New algorithms and lower bounds for circuits with linear threshold gates

  2014cites this paper
• Exact Algorithms for 0-1 Integer Programs with Linear Equality Constraints

  2014influential citation
• A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits

  2012cites this paper
• A Faster Algorithm for 0 - 1 Integer Programming from Communication Complexity

  year unknowncites this paper
• The fine-grained complexity of multi-dimensional ordering properties

  year unknowncites this paper