Smoothed analysis of integer programming

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

zbMATH Keywords

Integer programmingProbabilistic analysis

Mathematics Subject Classification ID

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