Please use this identifier to cite or link to this item:
Title: Probabilistic combinatorial optimization: Moments, semidefinite programming, and asymptotic bounds
Authors: Bertsimas, D.
Natarajan, K.
Teo, C.-P. 
Keywords: Combinatorial optimization
Convex optimization
Moments problem
Probabilistic analysis
Issue Date: 2005
Citation: Bertsimas, D., Natarajan, K., Teo, C.-P. (2005). Probabilistic combinatorial optimization: Moments, semidefinite programming, and asymptotic bounds. SIAM Journal on Optimization 15 (1) : 185-209. ScholarBank@NUS Repository.
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. © 2004 Society for Industrial and Applied Mathematics.
Source Title: SIAM Journal on Optimization
ISSN: 10526234
DOI: 10.1137/S1052623403430610
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
2005-probabilistic_combinatorial_optimization_moments_semidefinite-published.pdf247.88 kBAdobe PDF



Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.