Typical Properties of Winners and Losers [0.2ex] in Discrete Optimization

DOI10.1137/S0097539705447268zbMath1096.68066OpenAlexW3022308742MaRDI QIDQ5470717

Rene Beier, Berthold Vöcking

Publication date: 1 June 2006

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539705447268

zbMATH Keywords

optimization problemsaverage-case analysissmoothed analysis

Mathematics Subject Classification ID

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

Related Items (11)

Smoothed analysis of binary search trees ⋮ Smoothed analysis for tensor methods in unsupervised learning ⋮ Smoothed Analysis of the Successive Shortest Path Algorithm ⋮ An average polynomial algorithm for solving antagonistic games on graphs ⋮ Smoothed analysis of integer programming ⋮ A quantization framework for smoothed analysis of Euclidean optimization problems ⋮ Beyond the worst case: semi-random complexity analysis of winner determination ⋮ On smoothed analysis of quicksort and Hoare's find ⋮ The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes ⋮ Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes ⋮ Improved smoothed analysis of multiobjective optimization

This page was built for publication: Typical Properties of Winners and Losers [0.2ex] in Discrete Optimization