Name
Title | ||
|---|---|---|
Probabilistic Combinatorial Optimization: Moments, Semidefinite Programming, and Asymptotic Bounds |
Abstract | ||
|---|---|---|
We address the problem of evaluating the expected optimal objective value of a 0-1 optimization problem under uncertainty in the objective coefficients. The probabilistic model we consider prescribes limited marginal distribution information for the objective coefficients in the form of moments. We show that for a fairly general class of marginal information, a tight upper (lower) bound on the expected optimal objective value of a 0-1 maximization (minimization) problem can be computed in polynomial time if the corresponding deterministic problem is solvable in polynomial time. We provide an efficiently solvable semidefinite programming formulation to compute this tight bound. We also analyze the asymptotic behavior of a general class of combinatorial problems that includes the linear assignment, spanning tree, and traveling salesman problems, under knowledge of complete marginal distributions, with and without independence. We calculate the limiting constants exactly. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1137/S1052623403430610 | SIAM Journal on Optimization |
Keywords | Field | DocType |
probabilistic analysis,salesman problem,expected optimal objective value,asymptotic bounds,semidefinite programming,general class,moments problem,combinatorial optimization,combinatorial problem,complete marginal distribution,probabilistic combinatorial optimization,convex optimization,objective coefficient,marginal distribution information,optimization problem,polynomial time,corresponding deterministic problem,spanning tree,lower bound,moment problem,traveling salesman problem,probabilistic model | Weapon target assignment problem,Bottleneck traveling salesman problem,Discrete mathematics,Mathematical optimization,Quadratic assignment problem,Generalized assignment problem,Combinatorial optimization,Cross-entropy method,Optimization problem,Mathematics,Semidefinite programming | Journal |
Volume | Issue | ISSN |
15 | 1 | 1052-6234 |
Citations | PageRank | References |
23 | 1.47 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dimitris J. Bertsimas | 1 | 4513 | 365.31 |
| Karthik Natarajan | 2 | 407 | 31.52 |
| Chung-Piaw Teo | 3 | 864 | 69.27 |