Name
Abstract | ||
|---|---|---|
The sub-optimality approximation problem considers an op- timization problemO, its optimal solution ��, and a variable x with do- main{d1,...,dm} and returns approximations toO(x d1),...,O(x dm), whereO(x d1) denotes the problemO with x assigned to di. The sub-optimality approximation problem is at the core of online stochastic optimization algorithms and it can also be used for solution repair and approximate filtering of optimization constraints. This paper formalizes the problem and presents sub-optimality approximation algorithms for metric TSPs, packet scheduling, and metric k-medians that run faster than the optimal or approximation algorithms. It also presents results on the hardness/easiness of sub-optimality approximations. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11564751_12 | CP |
Keywords | Field | DocType |
stochastic optimization | Approximation algorithm,Discrete mathematics,Randomized algorithm,Mathematical optimization,Stochastic optimization,Filter (signal processing),Travelling salesman problem,Stochastic programming,Optimization problem,Mathematics,Constrained optimization | Conference |
Citations | PageRank | References |
4 | 0.50 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Russell Bent | 1 | 335 | 26.14 |
| Irit Katriel | 2 | 176 | 13.72 |
| Pascal Van Hentenryck | 3 | 4052 | 425.66 |