We present a probabilistic analysis of a large class of combinatorial optimization problems containing all 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 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 winner, loser, and 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.

We study fundamental algorithmic questions concerning the complexity of market equilibria under perfect and imperfect information by means of a basic microeconomic game. Suppose a provider offers a service to a set of potential customers. Each customer has a particular demand of service and her behavior is determined by a utility function that is nonincreasing in the sum of demands that are served by the provider.Classical game theory assumes complete information : the provider has full knowledge of the behavior of all customers. We present a complete characterization of the complexity of computing optimal pricing strategies and of computing best/worst equilibria in this model. Basically, we show that most of these problems are inapproximable in the worst case but admit an FPAS in the average case. Our average case analysis covers large classes of distributions for customer utilities. We generalize our analysis to robust equilibria in which players change their strategies only when this promises a significant utility improvement.A more realistic model considers providers with incomplete information . Following the game theoretic framework of Bayesian games introduced by Harsanyi, the provider is aware of probability distributions describing the behavior of the customers and aims at estimating its expected revenue under best/worst equilibria. Somewhat counterintuitively, we obtain an FPRAS for the equilibria problem in the model with imperfect information although the problem with perfect information is inapproximable under the worst-case measures. In particular, the worst-case complexity of the considered problems increases with the precision of the available knowledge.

We present a probabilistic analysis of a large class of combinatorial\noptimization problems containing all {\\em binary optimization problems}\ndefined by linear constraints and a linear objective function over $\\{0,1\\}^n$.\nOur analysis is based on a semirandom input model that preserves the\ncombinatorial structure of the underlying optimization problem by\nparameterizing which input numbers are of a stochastic and which are of an\nadversarial nature. This input model covers various probability distributions\nfor the choice of the stochastic numbers and includes {\\em smoothed analysis}\nwith Gaussian and other kinds of perturbation models as a special case. In\nfact, we can exactly characterize the smoothed complexity of binary optimization\nproblems in terms of their worst-case complexity: A binary optimization\nproblem has polynomial smoothed complexity if and only if it admits a\n(possibly randomized) algorithm with pseudo-polynomial worst-case complexity.\n\nOur analysis is centered around structural properties of binary optimization\nproblems, called {\\em winner}, {\\em loser}, and {\\em feasibility gap}. We show\nthat if the coefficients of the objective function are stochastic, then the\ngap between the best and second best solution is likely to be of order\n$\\Omega(1/n)$. Furthermore, we show that if the coefficients of the constraints\nare stochastic, then the slack of the optimal solution with respect to this\nconstraint is typically of order $\\Omega(1/n^2)$. We exploit these properties\nin an adaptive rounding scheme that increases the accuracy of calculation\nuntil the optimal solution is found. The strength of our techniques is\nillustrated by applications to various \\npc-hard optimization problems from\nmathematical programming, network design, and scheduling for which we obtain\nthe first algorithms with polynomial smoothed/average-case complexity.

In this paper, we present the first average-case analysis proving an expected polynomial running time for an exact algorithm for the 0/1 knapsack problem. In particular, we prove, for various input distributions, that the number of dominating solutions (i.e., Pareto-optimal knapsack fillings) to this problem is polynomially bounded in the number of available items. An algorithm by Nemhauser and Ullmann can enumerate these solutions very efficiently so that a polynomial upper bound on the number of dominating solutions implies an algorithm with expected polynomial running time.The random input model underlying our analysis is very general and not restricted to a particular input distribution. We assume adversarial weights and randomly drawn profits (or vice versa). Our analysis covers general probability distributions with finite mean, and, in its most general form, can even handle different probability distributions for the profits of different items. This feature enables us to study the effects of correlations between profits and weights. Our analysis confirms and explains practical studies showing that so-called strongly correlated instances are harder to solve than weakly correlated ones.