Cited By
View all- Galbiati GMaffioli F(2006)Approximating maximum cut with limited unbalanceProceedings of the 4th international conference on Approximation and Online Algorithms10.1007/11970125_16(202-213)Online publication date: 14-Sep-2006
Approximating almost all instances of MAX-CUT within a ratio above the håstad threshold
Pages 432 - 443
Abstract
We give a deterministic polynomial-time algorithm which for any given average degree d and asymptotically almost all random graphs G in G ( n, m = [ d /2 n ]) outputs a cut of G whose ratio (in cardinality) with the maximum cut is at least 0.952. We remind the reader that it is known that unless P=NP, for no constant ε>0 is there a Max-Cut approximation algorithm that for all inputs achieves an approximation ratio of (16/17) +ε (16/17 < 0.94118).
References
[1]
F. Barahona, M. Grotschel, M. Junger, and G. Reinelt. An application of combinatorial optimization to statistical physics and circuit layout design. Operations Research , 36:493-513, 1988.
[2]
M. Beis, W. Duckworth, and M. Zito. Packing edges in random regular graphs. In K. Diks and W. Rytter, editors, MFCS , volume 2420 of Lecture Notes in Computer Science , pages 118-130. Springer, 2002.
[3]
M. Beis, W. Duckworth, and M. Zito. Large k-separated matchings of random regular graphs. In V. Estivill-Castro, editor, ACSC , volume 38 of CRPIT , pages 175-182. Australian Computer Society, 2005.
[4]
A. Bertoni, P. Campadelli, and R. Posenato. Un upper bound for the maximum cut mean value. In Proceedings of the 23rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG97) , volume 1335, pages 78-84. Lecture Notes in Computer Science, Springer, 1997.
[5]
M. Charikar, K. Makarychev, and Y. Makarychev. Near-optimal algorithms for unique games. In Proceedings of the 38th ACM Symposium on Theory of Computing Seattle, Washington, USA , 2006.
[6]
A. Coja-Oghlan, C. Moore, and V. Sanwalani. Max k-cut and approximating the chromatic number of random graphs. In J.C.M. Baeten, J.K. Lenstra, J. Parrow, and G.J. Woeginger, editors, ICALP , volume 2719 of Lecture Notes in Computer Science , pages 200-211. Springer, 2003.
[7]
D. Coppersmith, D. Gamarnik, M.T. Hajiaghayi, and G.B. Sorkin. Random max sat, random max cut, and their phase transitions. Random Struct. Algorithms , 24(4):502-545, 2004.
[8]
W. Fernandez de la Vega and M. Karpinski. 9/8-approximation algorithm for random max-3sat. Electronic Colloquium on Computational Complexity (ECCC) , (070), 2002.
[9]
J. Díaz, G. Grammatikopoulos, A.C. Kaporis, L.M. Kirousis, X. Pérez, and D.G. Sotiropoulos. 5-regular graphs are 3-colorable with positive probability. In G.S. Brodal and S. Leonardi, editors, ESA , volume 3669 of Lecture Notes in Computer Science , pages 215-225. Springer, 2005.
[10]
O. Dubois and J. Mandler. On the non-3-colourability of random graphs. ArXiv Mathematics e-prints , September 2002.
[11]
A.M. Frieze and C. McDiarmid. Algorithmic theory of random graphs. Random Struct. Algorithms , 10(1-2):5-42, 1997.
[12]
M. Goemans and D.Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM , 42:1115-1145, 1995.
[13]
J. Håstad. Some optimal inapproximability results. Journal of the ACM , 48:798- 869, 2001.
[14]
Y. Interian. Approximation algorithm for random MAX- k -SAT. In International Conference on Theory and Applications of Satisfiability Testing (SAT 2004) , 2004.
[15]
V. Kalapala and C. Moore. Max-cut on sparse random graphs. TR-CS-2002-24, University of New Mexico Department of Computer Science , 2002.
[16]
S. Khot. Hardness of approximating the shortest vector problem in lattices. In FOCS , pages 126-135. IEEE Computer Society, 2004.
[17]
M. Mitzenmacher. Tight thresholds for the pure literal rule. Technical report, Digital Equipment Corporation, 1997. Available at: www.research.compaq.com/SRC/.
[18]
Ng. Van Ngoc and Zs. Tuza. Linear-time algorithms for the max cut problem. Combinatorics, Probability & Computing , 2:201-210, 1993.
[19]
S. Poljak and Z. Tuza. The expected relative error of the polyhedral approximation of the max-cut problem. Operations Research Letters , 16:191-198, 1994.
[20]
L. Trevisan, G. Sorkin, M. Sudan, and D. Williamson. Gadgets, approximation, and linear programming. SIAM Journal on Computing , 29(6):2074-2097, 2000.
[21]
N.C. Wormald. Differential equations for random processes and random graphs. The Annals of Applied Probability , 5(4):1217-1235, 1995.
Index Terms
- Approximating almost all instances of MAX-CUT within a ratio above the håstad threshold
Recommendations
Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of ComputingIn the Densest k-Subgraph (DkS) problem, given an undirected graph G and an integer k, the goal is to find a subgraph of G on k vertices that contains maximum number of edges. Even though Bhaskara et al.'s state-of-the-art algorithm for the problem ...
Bilu-linial stable instances of max cut and minimum multiway cut
SODA '14: Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithmsWe investigate the notion of stability proposed by Bilu and Linial. We obtain an exact polynomial-time algorithm for γ-stable Max Cut instances with γ ≥ c√log n log log n for some absolute constant c > 0. Our algorithm is robust: it never returns an ...
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?
In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of $\alpha_{\text{\tiny{GW}}} + \epsilon$ for all $\epsilon > 0$; here $\alpha_{\text{\tiny{GW}}} \approx .878567$ denotes the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 11 September 2006
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 23 Dec 2024
Other Metrics
Citations
Cited By
View all- Galbiati GMaffioli F(2006)Approximating maximum cut with limited unbalanceProceedings of the 4th international conference on Approximation and Online Algorithms10.1007/11970125_16(202-213)Online publication date: 14-Sep-2006