Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor(s)
 Author(s): Beier, René Vöcking, Berthold dblp dblp Not MPG Author(s): Vöcking, Berthold
 BibTeX cite key*: Beier2006

 Title
 Title*: Typical Properties of Winners and Losers in Discrete Optimization

 Journal
 Journal Title*: SIAM Journal on Computing Journal's URL: http://www.siam.org/journals/sicomp.php Download URL for the article: http://epubs.siam.org/SICOMP/volume-35/art_44726.html Language: English

 Publisher
 Publisher's Name: SIAM Publisher's URL: http://www.siam.org/ Publisher's Address: Philadelphia, PA, USA ISSN:

 Vol, No, pp, Date
 Volume*: 35 Number: 4 Publishing Date: February 2006 Pages*: 855-881 Number of VG Pages: 35 Page Start: 855 Page End: 991 Sequence Number: DOI:

 Note: (LaTeX) Abstract: We present a probabilistic analysis of a large class of combinatorial optimization problems containing all {\em binary optimization problems} defined by linear constraints and a linear objective function over $\{0,1\}^n$. Our analysis is based on a semirandom input model that preserves the combinatorial structure of the underlying optimization problem by parameterizing which input numbers are of a stochastic and which are of an adversarial nature. This input model covers various probability distributions for the choice of the stochastic numbers and includes {\em smoothed analysis} with Gaussian and other kinds of perturbation models as a special case. In fact, we can exactly characterize the smoothed complexity of binary optimization problems in terms of their worst-case complexity: A binary optimization problem has polynomial smoothed complexity if and only if it admits a (possibly randomized) algorithm with pseudo-polynomial worst-case complexity. Our analysis is centered around structural properties of binary optimization problems, called {\em winner}, {\em loser}, and {\em feasibility gap}. We show that if the coefficients of the objective function are stochastic, then the gap between the best and second best solution is likely to be of order $\Omega(1/n)$. Furthermore, we show that if the coefficients of the constraints are stochastic, then the slack of the optimal solution with respect to this constraint is typically of order $\Omega(1/n^2)$. We exploit these properties in an adaptive rounding scheme that increases the accuracy of calculation until the optimal solution is found. The strength of our techniques is illustrated by applications to various \npc-hard optimization problems from mathematical programming, network design, and scheduling for which we obtain the first algorithms with polynomial smoothed/average-case complexity. URL for the Abstract: http://epubs.siam.org/SICOMP/volume-35/art_44726.html Categories, Keywords: Optimization problems, Average-case analysis, Smoothed analysis HyperLinks / References / URLs: Copyright Message: Personal Comments: Download Access Level: Intranet

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{Beier2006,
AUTHOR = {Beier, Ren{\'e} and V{\"o}cking, Berthold},
TITLE = {Typical Properties of Winners and Losers in Discrete Optimization},
JOURNAL = {SIAM Journal on Computing},
PUBLISHER = {SIAM},
YEAR = {2006},
NUMBER = {4},
VOLUME = {35},
PAGES = {855--881},