Lattice-based algorithms for number partitioning in the hard phase
From MaRDI portal
Publication:1926495
DOI10.1016/j.disopt.2012.06.002zbMath1254.90124MaRDI 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
90C10: Integer programming
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Uses Software
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
