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

DOI10.1145/1536414.1536458zbMath1304.68218arXiv0811.3244OpenAlexW2117654132WikidataQ57534951 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

zbMATH Keywords

approximation algorithmsdense instancesnearest codeword problemminimum constraint satisfactionlinear time approximation schemescorrelation and hierarchical clusteringGale-Berlekamp game

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial games (91A46)

Related Items (6)

Speeding up Graph Algorithms via Switching Classes ⋮ A randomized PTAS for the minimum consensus clustering with a fixed number of clusters ⋮ Approximation complexity of metric dimension problem ⋮ On Approximation Complexity of Metric Dimension Problem ⋮ On the parameterized complexity of consensus clustering ⋮ Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems

This page was built for publication: Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems