hide
Free keywords:
-
Abstract:
We present a probabilistic analysis for a large class of combinatorial
optimization problems containing, e.g., all {\em binary optimization
problems} defined by linear constraints and a linear objective
function over $\{0,1\}^n$. By parameterizing which constraints are of
stochastic and which are of adversarial nature, we obtain a
semi-random input model that enables us to do a general average-case
analysis for a large class of optimization problems while at the same
time taking care for the combinatorial structure of individual
problems. Our analysis 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 optimization problems in terms of their random
worst-case complexity.
\begin{center}
\begin{minipage}{0.42\textwidth}
A binary optimization problem has a {\em polynomial smoothed complexity}
if and only if it has a pseudopolynomial complexity.
\end{minipage}
\end{center}
Our analysis is centered around structural properties of binary optimization
problems, called {\em winner}, {\em loser}, and {\em feasibility gaps}. We
show, when the coefficients of the objective function and/or some of the
constraints are stochastic, then there usually exist a polynomial
$n^{-\Omega(1)}$ gap between the best and the second best solution as well as
a polynomial slack to the boundary of the constraints. Similar to the
condition number for linear programming, these gaps describe the sensitivity
of the optimal solution to slight perturbations of the input and
can be used to bound the necessary accuracy as well as the complexity
for solving an instance. We exploit the gaps in form of an
adaptive rounding scheme increasing 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 the first
algorithms with polynomial average-case/smoothed complexity.
