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:








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, Abstract, ©

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},
ADDRESS = {Philadelphia, PA, USA},
MONTH = {February},
}


Entry last modified by Uwe Brahm, 04/27/2007
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
René Beier
Created
04/12/2006 09:44:32 AM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Uwe Brahm
René Beier
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
04/27/2007 09:07:04 AM
03/05/2007 11:05:19 AM
05.02.2007 17:21:58
05.02.2007 17:21:44
01/22/2007 03:00:00 PM