Lattice-based algorithms for number partitioning in the hard phase

DOI10.1016/j.disopt.2012.06.002zbMath1254.90124OpenAlexW2080030999MaRDI QIDQ1926495

Bala Krishnamoorthy, William A. Webb, Nathan Moyer

Publication date: 28 December 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2012.06.002

zbMATH Keywords

number partitioningclosest vector problemMIPbasis reduction

Mathematics Subject Classification ID

Integer programming (90C10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Uses Software

• NTL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Column basis reduction and decomposable knapsack problems
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• Improved low-density subset sum algorithms
• A complete anytime algorithm for number partitioning
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Solving a System of Linear Diophantine Equations with Lower and Upper Bounds on the Variables
• A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
• Integer Programming with a Fixed Number of Variables
• Sieve algorithms for the shortest vector problem are practical
• New Generic Algorithms for Hard Knapsacks
• Probabilistic analysis of optimum partitioning
• Minkowski's Convex Body Theorem and Integer Programming
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• Exponentially small bounds on the expected optimum of the partition and subset sum problems
• The hardness of the closest vector problem with preprocessing
• Phase diagram for the constrained integer partitioning problem
• The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp
• Sharp threshold and scaling window for the integer partitioning problem
• Predicting Lattice Reduction
• Hard Equality Constrained Integer Knapsacks
• A physicist's approach to number partitioning

This page was built for publication: Lattice-based algorithms for number partitioning in the hard phase