Name
Title | ||
|---|---|---|
Approximation Algorithms for General Packing Problems with Modified Logarithmic Potential Function |
Abstract | ||
|---|---|---|
Abstract: In this paper we present an approximation algorithm based on a Lagrangiandecomposition via a logarithmic potential reduction to solve ageneral packing or min-max resource sharing problem with M nonnegativeconvex constraints on a convex set B. We generalize a method byGrigoriadis et al to the case with weak approximate block solvers (i.e.with only constant, logarithmic or even worse approximation ratios).We show that the algorithm needs at most O(M("calls to the block solver, a bound ... |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1007/978-0-387-35608-2_22 | IFIP TCS |
Keywords | Field | DocType |
general packing problems,modified logarithmic potential function,approximation algorithms,resource sharing,convex set | Approximation algorithm,Discrete mathematics,Combinatorics,Packing problems,Convex set,Regular polygon,Lagrangian decomposition,Solver,Logarithm,Mathematics | Conference |
Volume | ISSN | ISBN |
96 | 1571-5736 | 1-4020-7181-7 |
Citations | PageRank | References |
20 | 0.88 | 11 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Klaus Jansen | 1 | 789 | 82.68 |
| Hu Zhang | 2 | 123 | 7.99 |