Stochastic Combinatorial Optimization with Risk
We consider general combinatorial optimization problems that can be formulated as minimizing the weight of a feasible solution wT x over an arbitrary feasible set. For these problems we describe a broad class of corresponding stochastic problems where the weight vector W has independent random compo...
| Main Author: | |
|---|---|
| Other Authors: | |
| Published: |
2008
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/42837 |
| _version_ | 1826191282597265408 |
|---|---|
| author | Nikolova, Evdokia |
| author2 | David Karger |
| author_facet | David Karger Nikolova, Evdokia |
| author_sort | Nikolova, Evdokia |
| collection | MIT |
| description | We consider general combinatorial optimization problems that can be formulated as minimizing the weight of a feasible solution wT x over an arbitrary feasible set. For these problems we describe a broad class of corresponding stochastic problems where the weight vector W has independent random components, unknown at the time of solution. A natural and important objective which incorporates risk in this stochastic setting, is to look for a feasible solution whose stochastic weight has a small tail or a small linear combination of mean and standard deviation. Our models can be equivalently reformulated as deterministic nonconvex programs for which no efficient algorithms are known. In this paper, we make progress on these hard problems. Our results are several efficient general-purpose approximation schemes. They use as a black-box (exact or approximate) the solution to the underlying deterministic combinatorial problem and thus immediately apply to arbitrary combinatorial problems. For example, from an available ?-approximation algorithm to the deterministic problem, we construct a ?(1 + ?)-approximation algorithm that invokes the deterministic algorithm only a logarithmic number of times in the input and polynomial in 1/?, for any desired accuracy level ? > 0. The algorithms are based on a geometric analysis of the curvature and approximability of the nonlinear level sets of the objective functions. |
| first_indexed | 2024-09-23T08:53:27Z |
| id | mit-1721.1/42837 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:53:27Z |
| publishDate | 2008 |
| record_format | dspace |
| spelling | mit-1721.1/428372019-04-10T09:16:07Z Stochastic Combinatorial Optimization with Risk Nikolova, Evdokia David Karger Theory of Computation approximation algorithms, combinatorial optimization, stochastic optimization, risk, nonconvex optimization, concave programming We consider general combinatorial optimization problems that can be formulated as minimizing the weight of a feasible solution wT x over an arbitrary feasible set. For these problems we describe a broad class of corresponding stochastic problems where the weight vector W has independent random components, unknown at the time of solution. A natural and important objective which incorporates risk in this stochastic setting, is to look for a feasible solution whose stochastic weight has a small tail or a small linear combination of mean and standard deviation. Our models can be equivalently reformulated as deterministic nonconvex programs for which no efficient algorithms are known. In this paper, we make progress on these hard problems. Our results are several efficient general-purpose approximation schemes. They use as a black-box (exact or approximate) the solution to the underlying deterministic combinatorial problem and thus immediately apply to arbitrary combinatorial problems. For example, from an available ?-approximation algorithm to the deterministic problem, we construct a ?(1 + ?)-approximation algorithm that invokes the deterministic algorithm only a logarithmic number of times in the input and polynomial in 1/?, for any desired accuracy level ? > 0. The algorithms are based on a geometric analysis of the curvature and approximability of the nonlinear level sets of the objective functions. 2008-09-25T19:00:16Z 2008-09-25T19:00:16Z 2008-09-13 http://hdl.handle.net/1721.1/42837 MIT-CSAIL-TR-2008-055 25 p. application/pdf application/postscript |
| spellingShingle | approximation algorithms, combinatorial optimization, stochastic optimization, risk, nonconvex optimization, concave programming Nikolova, Evdokia Stochastic Combinatorial Optimization with Risk |
| title | Stochastic Combinatorial Optimization with Risk |
| title_full | Stochastic Combinatorial Optimization with Risk |
| title_fullStr | Stochastic Combinatorial Optimization with Risk |
| title_full_unstemmed | Stochastic Combinatorial Optimization with Risk |
| title_short | Stochastic Combinatorial Optimization with Risk |
| title_sort | stochastic combinatorial optimization with risk |
| topic | approximation algorithms, combinatorial optimization, stochastic optimization, risk, nonconvex optimization, concave programming |
| url | http://hdl.handle.net/1721.1/42837 |
| work_keys_str_mv | AT nikolovaevdokia stochasticcombinatorialoptimizationwithrisk |