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

被引：42

作者：

Epstein, Leah ^{[1
]}

Levin, Asaf ^{[2
]}

Mestre, Julian ^{[3
]}

Segev, Danny ^{[4
]}

机构：

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

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

[3] Univ Sydney, Sch Informat Technol, Sydney, NSW 2006, Australia

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

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2011年 / 25卷 / 03期

关键词：

weighted matching; semi-streaming; competitive analysis; approximation algorithms; ALGORITHMS;

D O I：

10.1137/100801901

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We study the maximum weight matching problem in the semi-streaming model, and improve on the currently best one-pass algorithm due to Zelke [Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, 2008, pp. 669-680] by devising a deterministic approach whose performance guarantee is 4.91 + epsilon. In addition, we study preemptive online algorithms, a class of algorithms related to one-pass semi-streaming algorithms, where we are allowed to maintain only a feasible matching in memory at any point in time. 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 that 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.

引用

页码：1251 / 1265

页数：15

共 19 条

[1]

[Anonymous], 1998, Online Computation and Competitive Analysis

[2]

[Anonymous], 2005, DATA STREAMS ALGORIT

[3]

[Anonymous], 2003, COMBINATORIAL OPTIMI

[4]

Bansal N, 2007, LECT NOTES COMPUT SC, V4698, P522

[5]

Chi-Chih Yao A., 1977, 18th Annual Symposium on Foundations of Computer Science, P222

[6] Efficient algorithms for constructing (1+ε,β)-spanners in the distributed and streaming models [J].

Elkin, M ;

Zhang, J .

DISTRIBUTED COMPUTING, 2006, 18 (05) :375-385

[7] On graph problems in a semi-streaming model [J].

Feigenbaum, J ;

Kannan, S ;

McGregor, A ;

Suri, S ;

Zhang, J .

THEORETICAL COMPUTER SCIENCE, 2005, 348 (2-3) :207-216

[8] GRAPH DISTANCES IN THE DATA-STREAM MODEL [J].

Feigenbaum, Joan ;

Kannan, Sampath ;

Mcgregor, Andrew ;

Suri, Siddharth ;

Zhang, Jian .

SIAM JOURNAL ON COMPUTING, 2008, 38 (05) :1709-1727

[9] Efficient on-line call control algorithms [J].

Garay, JA ;

Gopal, IS ;

Kutten, S ;

Mansour, Y ;

Yung, M .

JOURNAL OF ALGORITHMS, 1997, 23 (01) :180-194

[10] ONLINE WEIGHTED MATCHING [J].

KALYANASUNDARAM, B ;

PRUHS, K .

JOURNAL OF ALGORITHMS, 1993, 14 (03) :478-488

← 1 2 →