How Well Can Primal-Dual and Local-Ratio Algorithms Perform?

被引：1

作者：

Borodin, Allan ^{[1
]}

Cashman, David ^{[2
]}

Magen, Avner ^{[1
]}

机构：

[1] Univ Toronto, Dept Comp Sci, Toronto, ON M5S 1A1, Canada

[2] Altera Corp, Toronto, ON, Canada

来源：

ACM TRANSACTIONS ON ALGORITHMS | 2011年 / 7卷 / 03期

关键词：

Local ratio; primal dual; greedy algorithms; approximation algorithms; algorithmic limitations; Steiner tree; set cover; interval scheduling; bandwidth allocation; APPROXIMATION ALGORITHM; RESOURCE-ALLOCATION; FACILITY LOCATION; STEINER PROBLEM; RELAXATIONS; SCHEMA; TREES;

D O I：

10.1145/1978782.1978784

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We define an algorithmic paradigm, the stack model, that captures many primal-dual and local-ratio algorithms for approximating covering and packing problems. The stack model is defined syntactically and without any complexity limitations and hence our approximation bounds are independent of the P versus NP question. Using the stack model, we bound the performance of a broad class of primal-dual and local-ratio algorithms and supply a (log n + 1)/2 inapproximability result for set cover, a 4/3 inapproximability for min Steiner tree, and a 0.913 inapproximability for interval scheduling on two machines.

引用

页数：26

共 62 条

[1] ADAMY U, 2004, P WORKSH APPR ONL AL, P211
[2] WHEN TREES COLLIDE - AN APPROXIMATION ALGORITHM FOR THE GENERALIZED STEINER PROBLEM ON NETWORKS
AGRAWAL, A
KLEIN, P
RAVI, R
[J]. SIAM JOURNAL ON COMPUTING, 1995, 24 (03) : 440 - 456
[3] AKCOGLU K, 2000, CSCE0010031 CORR, P143
[4] ALEKHNOVICH M, 2005, P 20 ANN IEEE C COMP
[5] AMZALLAG D, 2008, P IEEE INFOCOM, P700
[6] The power of priority algorithms for facility location and set cover
Angelopoulos, S
Borodin, A
[J]. ALGORITHMICA, 2004, 40 (04) : 271 - 291
[7] [Anonymous], 2001, Approximation algorithms
[8] [Anonymous], 1992, P IND US WORKSH COOP
[9] SCHEDULING JOBS WITH FIXED START AND END TIMES
ARKIN, EM
SILVERBERG, EB
[J]. DISCRETE APPLIED MATHEMATICS, 1987, 18 (01) : 1 - 8
[10] Arora S, 2002, ANN IEEE SYMP FOUND, P313, DOI 10.1109/SFCS.2002.1181954

← 1 2 3 4 5 6 7 →