Name
Abstract | ||
|---|---|---|
We propose an approximation algorithm based on the Lagrangian or price - directive decomposition method to compute an -approximate solution of the mixed fractional packing and covering problem: find such that , where are vectors with nonnegative convex and concave functions, and are - dimensional nonnegative vectors and is a convex set that can be queried by an optimization or feasibility ora- cle. We propose an algorithm that needs only iterations or calls to the oracle. The main contribution is that the algori thm solves the general mixed fractional packing and covering problem (in contrast to pure fractional packing and covering problems and to the special mixed packing and covering problem with ) and runs in time independent of the so-called width of the problem. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/1-4020-8141-3_19 | WAOA |
Keywords | Field | DocType |
convex and concave optimization,following form,m nonnegative continuous concave,feasible vector,general mixed fractional packing,approximation algorithms.,rm ir,approximation algorithm,relative tolerance,m nonnegative continuous convex,dimensional nonnegative,nonempty convex compact | Approximation algorithm,Mathematical optimization,Combinatorics,Concave function,Compact space,Regular polygon,Convex function,Mathematics,Covering problems | Conference |
Volume | Issue | ISSN |
3351 | 2 | 0302-9743 |
ISBN | Citations | PageRank |
3-540-24574-X | 3 | 0.39 |
References | Authors | |
13 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Klaus Jansen | 1 | 137 | 18.78 |