Smoothed analysis of integer programming

DOI10.1007/S10107-006-0055-7zbMATH Open1111.90077OpenAlexW2170959740MaRDI QIDQ877191FDOQ877191

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

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
• Smoothed complexity theory

zbMATH Keywords

Integer programmingProbabilistic analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Integer programming (90C10)

Cites Work

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

Cited In (11)

• Smoothed analysis of balancing networks
• On smoothed analysis of quicksort and Hoare's find
• Smoothed Analysis of Local Search Algorithms
• Typical Properties of Winners and Losers [0.2ex] in Discrete Optimization
• Computational complexity of kernel-based density-ratio estimation: a condition number analysis
• Settling the Complexity of Local Max-Cut (Almost) Completely
• Fundamentals of Computation Theory
• On the integrality gap of binary integer programs with Gaussian data
• On the integrality gap of binary integer programs with Gaussian data
• Smoothed Analysis of Integer Programming
• The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes

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)