Smoothed analysis of integer programming
From MaRDI portal
Publication:877191
DOI10.1007/s10107-006-0055-7zbMath1111.90077OpenAlexW2170959740MaRDI QIDQ877191
Berthold Vöcking, Heiko Röglin
Publication date: 19 April 2007
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-006-0055-7
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Combinatorial optimization (90C27)
Related Items (8)
Smoothed Analysis of Local Search Algorithms ⋮ On smoothed analysis of quicksort and Hoare's find ⋮ Computational complexity of kernel-based density-ratio estimation: a condition number analysis ⋮ The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes ⋮ Settling the Complexity of Local Max-Cut (Almost) Completely ⋮ Smoothed analysis of balancing networks ⋮ On the integrality gap of binary integer programs with Gaussian data ⋮ On the integrality gap of binary integer programs with Gaussian data
Cites Work
- Unnamed Item
- Unnamed Item
- Average saving effects in enumerative methods for solving knapsack problems
- An experimental study of random knapsack problems
- Smoothed analysis of algorithms
- Probabilistic Analysis of the Multidimensional Knapsack Problem
- Average-Case Analysis of Off-Line and On-Line Knapsack Problems
- Mathematical Foundations of Computer Science 2003
- Typical Properties of Winners and Losers [0.2ex in Discrete Optimization]
- Algorithms and Computation
- Algorithms and Computation
- Random knapsack in expected polynomial time
This page was built for publication: Smoothed analysis of integer programming