IMPROVED APPROXIMATION GUARANTEES FOR WEIGHTED MATCHING IN THE SEMI-STREAMING MODEL

被引：12

作者：

Epstein, Leah ^{[1
]}

Levin, Asaf ^{[2
]}

Mestre, Julian ^{[3
]}

Segev, Danny ^{[4
]}

机构：

[1] Univ Haifa, Dept Math, IL-31905 Haifa, Israel

[2] Technion, Fac Ind Engn & Management, IL-32000 Haifa, Israel

[3] Max Planck Inst Informat, D-66123 Saarbrucken, Germany

[4] Univ Haifa, Dept Stat, IL-31905 Haifa, Israel

来源：

27TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2010) | 2010年 / 5卷

关键词：

ALGORITHMS;

D O I：

10.4230/LIPIcs.STACS.2010.2476

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the maximum weight matching problem in the semi-streaming model, and improve on the currently best one-pass algorithm due to Zelke (Proc. STACS '08, pages 669-680) by devising a deterministic approach whose performance guarantee is 4.91 + epsilon. In addition, we study preemptive online algorithms, a sub-class of one-pass algorithms where we are only allowed to maintain a feasible matching in memory at any point in time. All known results prior to Zelke's belong to this sub-class. We provide a lower bound of 4.967 on the competitive ratio of any such deterministic algorithm, and hence show that future improvements will have to store in memory a set of edges which is not necessarily a feasible matching. We conclude by presenting an empirical study, conducted in order to compare the practical performance of our approach to that of previously suggested algorithms.

引用

页码：347 / 358

页数：12

共 16 条

[1] [Anonymous], FDN TRENDS THEORETIC
[2] [Anonymous], 2003, COMBINATORIAL OPTIMI
[3] Bansal N, 2007, LECT NOTES COMPUT SC, V4698, P522
[4] Efficient algorithms for constructing (1+ε,β)-spanners in the distributed and streaming models
Elkin, M
Zhang, J
[J]. DISTRIBUTED COMPUTING, 2006, 18 (05) : 375 - 385
[5] Epstein L., 2009, IMPROVED APPROXIMATI
[6] On graph problems in a semi-streaming model
Feigenbaum, J
Kannan, S
McGregor, A
Suri, S
Zhang, J
[J]. THEORETICAL COMPUTER SCIENCE, 2005, 348 (2-3) : 207 - 216
[7] GRAPH DISTANCES IN THE DATA-STREAM MODEL
Feigenbaum, Joan
Kannan, Sampath
Mcgregor, Andrew
Suri, Siddharth
Zhang, Jian
[J]. SIAM JOURNAL ON COMPUTING, 2008, 38 (05) : 1709 - 1727
[8] Efficient on-line call control algorithms
Garay, JA
Gopal, IS
Kutten, S
Mansour, Y
Yung, M
[J]. JOURNAL OF ALGORITHMS, 1997, 23 (01) : 180 - 194
[9] ONLINE WEIGHTED MATCHING
KALYANASUNDARAM, B
PRUHS, K
[J]. JOURNAL OF ALGORITHMS, 1993, 14 (03) : 478 - 488
[10] Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
Kao, MY
Reif, JH
Tate, SR
[J]. INFORMATION AND COMPUTATION, 1996, 131 (01) : 63 - 79

← 1 2 →