Please use this identifier to cite or link to this item: https://doi.org/10.1137/S1052623403430610
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
Source: 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. https://doi.org/10.1137/S1052623403430610
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
URI: http://scholarbank.nus.edu.sg/handle/10635/44011
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

OPEN

PublishedView/Download

SCOPUSTM   
Citations

24
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

24
checked on Nov 19, 2017

Page view(s)

53
checked on Dec 10, 2017

Download(s)

4
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


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