research-article

Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems

Authors:

Marek Karpinski,

Warren SchudyAuthors Info & Claims

STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

Pages 313 - 322

https://doi.org/10.1145/1536414.1536458

Published: 31 May 2009 Publication History

Abstract

We design a linear time approximation scheme for the Gale-Berlekamp Switching Game and generalize it to a wider class of dense fragile minimization problems including the Nearest Codeword Problem (NCP) and Unique Games Problem. Further applications include, among other things, finding a constrained form of matrix rigidity and maximum likelihood decoding of an error correcting code. As another application of our method we give the first linear time approximation schemes for correlation clustering with a fixed number of clusters and its hierarchical generalization. Our results depend on a new technique for dealing with small objective function values of optimization problems and could be of independent interest.

References

[1]

N. Ailon and M. Charikar. Fitting tree metrics: Hierarchical clustering and phylogeny. In Proc. 46th IEEE FOCS, pages 73--82, 2005.

Digital Library

[2]

N. Alon, W. Fernandez de la Vega, R. Kannan, and M. Karpinski. Random Sampling and Approximation of MAX-CSP Problems. In Proc. 34th ACM STOC, pages 232--239, 2002. Journal version in J. Comput. System Sciences, 67(2):212--243, 2003.

Digital Library

[3]

N. Alon, R. Panigrahy, and S. Yekhanin. Deterministic Approximation Algorithms for the Nearest Codeword Problem. Technical report, Elec. Coll. on Comp. Compl., ECCC TR08--065, 2008.

[4]

S. Arora, L. Babai, J. Stern, and Z. Sweedyk. The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations. In Proc. 34th IEEE FOCS, pages 724--733, Nov 1993. Journal version in J. Comput. System Sciences, 54(2):317--331, 1997.

Digital Library

[5]

S. Arora, A. Frieze, and H. Kaplan. A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems. In Proc. 37th IEEE FOCS, pages 21--30, Oct 1996. Journal version in Mathematical Programming, 92(1):1--36, 2002.

Digital Library

[6]

S. Arora, D. Karger, and M. Karpinski. Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems. In Proc. 27th ACM STOC, pages 284--293, 1995. Journal version in J. Comput. System Sciences, 58(1):193--210, 1999.

Digital Library

[7]

C. Bazgan, W. Fernandez de la Vega, and M. Karpinski. Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction. Random Structures and Algorithms, 23(1):73--91, 2003.

Digital Library

[8]

P. Berman and M. Karpinski. Approximating Minimum Unsatisfiability of Linear Equations. In Proc. 13th ACM-SIAM SODA, pages 514--516, 2002.

Digital Library

[9]

P. Berman and M. Karpinski. Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION. In Proc. 29th ICALP, LNCS 2380, pages 623--632. Springer, 2002.

Digital Library

[10]

J. Carlson and D. Stolarski. The Correct Solution to Berlekamp's Switching Game. Discrete Mathematics, 287(1--3):145--150, 2004.

[11]

I. Dinur, G. Kindler, R. Raz, and S. Safra. Approximating CVP to Within Almost-Polynomial Factors is NP-Hard. Combinatorica, 23(2):205--243, 2003.

Digital Library

[12]

U. Feige and L. Lovasz. Two prover one round proof systems: Their power and their problems. In Proc. 24th STOC, pages 733--741, 1992.

Digital Library

[13]

W. Fernandez de la Vega. MAX-CUT has a Randomized Approximation Scheme in Dense Graphs. Random Struct. Algorithms, 8(3):187--198, 1996.

Digital Library

[14]

W. Fernandez de la Vega, R. Kannan, and M. Karpinski. Approximation of Global MAX-CSP Problems. Technical Report TR06-124, Electronic Colloquim on Computation Complexity, 2006.

[15]

P. C. Fishburn and N. J. Sloane. The Solution to Berlekamp's Switching Game. Discrete Math., 74(3):263--290, 1989.

Digital Library

[16]

A. M. Frieze and R. Kannan. Quick Approximation to Matrices and Applications. Combinatorica, 19(2):175--220, 1999.

[17]

I. Giotis and V. Guruswami. Correlation clustering with a fixed number of clusters. Theory of Computing, 2(1):249--266, 2006.

[18]

A. Gupta and K. Talvar. Approximating unique games. In Proc. 17th ACM-SIAM SODA, pages 99--106, 2006.

Digital Library

[19]

S. V. Lokam. Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeoffs and Communication Complexity. In Proc. 36th IEEE FOCS, pages 6--15, 1995.

Digital Library

[20]

C. Mathieu and W. Schudy. Yet Another Algorithm for Dense Max Cut: Go Greedy. In Proc. 19th ACM-SIAM SODA, pages 176--182, 2008.

Digital Library

[21]

R. Roth and K. Viswanathan. On the Hardness of Decoding the Gale-Berlekamp Code. IEEE Transactions on Information Theory, 54(3):1050--1060, March 2008.

Digital Library

[22]

M. Rudelson and R. Vershynin. Sampling from large matrices: An approach through geometric functional analysis. J. ACM, 54(4):21, 2007.

Digital Library

[23]

J. Spencer. Ten Lectures on the Probabilistic Method. SIAM, Regional Conference Series, second edition, 1994.

Cited By

Cao NCohen-Addad VLee ELi SNewman AVogl LMohar BShinkar IO'Donnell R(2024)Understanding the Cluster Linear Program for Correlation ClusteringProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649749(1605-1616)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649749
Cohen-Addad VLolck DPilipczuk MThorup MYan SZhang HMohar BShinkar IO'Donnell R(2024)Combinatorial Correlation ClusteringProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649712(1617-1628)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649712
Cohen-Addad VLee ELi SNewman A(2023)Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00065(1082-1104)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00065
Show More Cited By

Index Terms

Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems
ITCS '14: Proceedings of the 5th conference on Innovations in theoretical computer science

We consider approximation schemes for the maximum constraint satisfaction problems and the maximum assignment problems. Though they are NP-Hard in general, if the instance is "dense" or "locally dense", then they are known to have approximation schemes ...
Polynomial time approximation schemes for dense instances of minimum constraint satisfaction

It is known that large fragments of the class of dense Minimum Constraint Satisfaction (MIN-CSP) problems do not have polynomial time approximation schemes (PTASs) contrary to their Maximum Constraint Satisfaction analogs. In this paper we prove, ...
Approximation Algorithms for Multi-Criteria Traveling Salesman Problems

We analyze approximation algorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with ź-triangle inequality. For this problem, we present a deterministic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

May 2009

750 pages

ISBN:9781605585062

DOI:10.1145/1536414

Program Chair:
Michael Mitzenmacher
Harvard University

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '09

Sponsor:

STOC '09: Symposium on Theory of Computing

May 31 - June 2, 2009

MD, Bethesda, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
313
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cao NCohen-Addad VLee ELi SNewman AVogl LMohar BShinkar IO'Donnell R(2024)Understanding the Cluster Linear Program for Correlation ClusteringProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649749(1605-1616)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649749
Cohen-Addad VLolck DPilipczuk MThorup MYan SZhang HMohar BShinkar IO'Donnell R(2024)Combinatorial Correlation ClusteringProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649712(1617-1628)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649712
Cohen-Addad VLee ELi SNewman A(2023)Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00065(1082-1104)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00065
Yin HNg KMa SWong HMak H(2022)Two-State Alien Tiles: A Coding-Theoretical PerspectiveMathematics10.3390/math1016299410:16(2994)Online publication date: 19-Aug-2022
https://doi.org/10.3390/math10162994
Cohen-Addad VLee ENewman A(2022)Correlation Clustering with Sherali-Adams2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00068(651-661)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00068
Hao STang NLi GFeng JWang N(2021)Mis-categorized entities detectionThe VLDB Journal10.1007/s00778-021-00653-wOnline publication date: 6-Mar-2021
https://doi.org/10.1007/s00778-021-00653-w
Chawla SMakarychev KSchramm TYaroslavtsev GServedio RRubinfeld R(2015)Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite GraphsProceedings of the forty-seventh annual ACM symposium on Theory of Computing10.1145/2746539.2746604(219-228)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2746539.2746604
Anava YAvigdor-Elgrabli NGamzu IGangemi ALeonardi SPanconesi A(2015)Improved Theoretical and Practical Guarantees for Chromatic Correlation ClusteringProceedings of the 24th International Conference on World Wide Web10.1145/2736277.2741629(55-65)Online publication date: 18-May-2015
https://dl.acm.org/doi/10.1145/2736277.2741629
Lindzey N(2015)Speeding up Graph Algorithms via Switching ClassesCombinatorial Algorithms10.1007/978-3-319-19315-1_21(238-249)Online publication date: 7-Jun-2015
https://doi.org/10.1007/978-3-319-19315-1_21
Hauptmann MSchmied RViehmann C(2012)Approximation complexity of Metric Dimension problemJournal of Discrete Algorithms10.1016/j.jda.2011.12.01014(214-222)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1016/j.jda.2011.12.010
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents