Smoothed analysis of integer programming

DOI10.1007/S10107-006-0055-7MaRDI QIDQ877191zbMATH OpenOpenAlexFDO

Authors Heiko Röglin, Berthold Vöcking

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) Combinatorial optimization (90C27) Integer programming (90C10)

Recommendations

• Smoothed Analysis of Integer Programming
• Smoothed analysis of termination of linear programming algorithms
• Smoothed analysis of condition numbers and complexity implications for linear programming
• scientific article; zbMATH DE number 2119754
• Item:QQ5890963

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Algorithms and Computation
• Algorithms and Computation
• An experimental study of random knapsack problems
• Average saving effects in enumerative methods for solving knapsack problems
• Average-Case Analysis of Off-Line and On-Line Knapsack Problems
• Mathematical Foundations of Computer Science 2003
• Probabilistic Analysis of the Multidimensional Knapsack Problem
• Probabilistic analysis of knapsack core algorithms
• Random knapsack in expected polynomial time
• Smoothed analysis of algorithms
• Typical Properties of Winners and Losers [0.2ex] in Discrete Optimization

Cited in

(11)

• On smoothed analysis of quicksort and Hoare's find
• Typical properties of winners and losers in discrete optimization
• Fundamentals of Computation Theory
• Computational complexity of kernel-based density-ratio estimation: a condition number analysis
• Typical Properties of Winners and Losers [0.2ex] in Discrete Optimization
• Smoothed Analysis of Integer Programming
• Settling the complexity of local max-cut (almost) completely
• Smoothed analysis of local search algorithms
• The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes
• On the integrality gap of binary integer programs with Gaussian data
• On the integrality gap of binary integer programs with Gaussian data

This page was built for publication: Smoothed analysis of integer programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q877191)