Sketching Cuts in Graphs and Hypergraphs

被引：45
作者：
Kogan, Dmitry [1 ]
Krauthgamer, Robert [1 ]
机构：
[1] Weizmann Inst Sci, Rehovot, Israel
来源：
PROCEEDINGS OF THE 6TH INNOVATIONS IN THEORETICAL COMPUTER SCIENCE (ITCS'15) | 2015年
基金：
以色列科学基金会;
关键词：
Sketching; Sparsifiers; Streaming; Hypergraphs; Max-Cut; APPROXIMATION ALGORITHMS; MAX-CUT;
D O I：
10.1145/2688073.2688093
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Sketching and streaming algorithms are in the forefront of current research directions for cut problems in graphs. In the streaming model, we show that (1-epsilon)-approximation for MAX-CUT must use n(1-O(epsilon)) space; moreover, beating 4/5-approximation requires polynomial space. For the sketching model, we show that every r-uniform hypergraph admits a (1+epsilon)-cut-sparsifier (i.e., a weighted subhypergraph that approximately preserves all the cuts) with O (epsilon(-2 )n(r + log n)) edges. We also make first steps towards sketching general CSPs (Constraint Satisfaction Problems).
引用
收藏
页码：366 / 375
页数：10
相关论文
共 37 条
[1]  
Ahn Kook J., 2012, P 23 ANN ACM SIAM S, P459
[2]  
Ahn KJ, 2009, LECT NOTES COMPUT SC, V5556, P328
[3]  
Ahn Kook Jin, 2012, P 31 S PRINCIPLES DA, P5, DOI 10.1145
[4]  
Andoni A., 2014, CORR
[5]  
Bencz'ur Andr'asA., 2002, CoRR
[6]  
Benczur A. A., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P47, DOI 10.1145/237814.237827
[7]  
de Carli Silva M. K., 2011, CORR
[8]  
Dell H, 2010, ACM S THEORY COMPUT, P251
[9]  
Dinitz E.A., 1976, Studies in Discrete Optimization, P290
[10]  
Goel A., 2012, CoRR
1234