Please use this identifier to cite or link to this item:
|Title:||Probabilistic combinatorial optimization: Moments, semidefinite programming, and asymptotic bounds||Authors:||Bertsimas, D.
|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. 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:
|2005-probabilistic_combinatorial_optimization_moments_semidefinite-published.pdf||247.88 kB||Adobe PDF|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.