Name
Title | ||
|---|---|---|
On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems |
Abstract | ||
|---|---|---|
Combinatorial optimization is often used to "plan ahead," purchasing and allocating resources for demands that are not precisely known at the time of solution. This advance planning may be done because resources become very expensive to purchase or difficult to allocate at the last minute when the demands are known. In this work we study the tradeoffs involved in making some purchase/allocation decisions early to reduce cost while deferring others at greater expense to take advantage of additional, late-arriving information. We consider a number of combinatorial optimization problems in which the problem instance is uncertain---modeled by a probability distribution---and in which solution elements can be purchased cheaply now or at greater expense after the distribution is sampled. We show how to approximately optimize the choice of what to purchase in advance and what to defer. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.5555/982792.982898 | SODA |
Keywords | Field | DocType |
solution element,combinatorial optimization problem,stochastic combinatorial optimization problem,combinatorial optimization,advance planning,greater expense,problem instance,approximation algorithm,allocation decision,last minute,late-arriving information,probability distribution,matching,linear programming relaxation,costs and benefits,complexity,spanning tree,crossing number,triangulation | Approximation algorithm,Discrete mathematics,Mathematical optimization,Combinatorics,Procrastination,Quadratic assignment problem,Computer science,Combinatorial optimization,Cost–benefit analysis,Purchasing,Linear programming relaxation,Optimization problem | Conference |
ISBN | Citations | PageRank |
0-89871-558-X | 81 | 3.98 |
References | Authors | |
9 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicole Immorlica | 1 | 1636 | 100.87 |
| David R. Karger | 2 | 19367 | 2233.64 |
| Maria Minkoff | 3 | 310 | 19.51 |
| VAHAB S. MIRROKNI | 4 | 4309 | 287.14 |