Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems
From MaRDI portal
Publication:5172725
DOI10.1145/1536414.1536458zbMath1304.68218arXiv0811.3244WikidataQ57534951 ScholiaQ57534951MaRDI QIDQ5172725
Warren Schudy, Marek Karpinski
Publication date: 4 February 2015
Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0811.3244
approximation algorithms; dense instances; nearest codeword problem; minimum constraint satisfaction; linear time approximation schemes; correlation and hierarchical clustering; Gale-Berlekamp game
68Q25: Analysis of algorithms and problem complexity
68W25: Approximation algorithms
91A46: Combinatorial games
Related Items
A randomized PTAS for the minimum consensus clustering with a fixed number of clusters, Approximation complexity of metric dimension problem, On the parameterized complexity of consensus clustering, Speeding up Graph Algorithms via Switching Classes, On Approximation Complexity of Metric Dimension Problem, Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems