Random sampling and approximation of MAX-CSP problems

DOI10.1145/509907.509945zbMath1192.68865OpenAlexW1976779334MaRDI QIDQ3579226

Noga Alon, Ravindran Kannan, Marek Karpinski, Wenceslas Fernandez de la Vega

Publication date: 5 August 2010

Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/509907.509945

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Related Items

Random sampling and approximation of MAX-CSPs, Hardness of fully dense problems, Additive approximation for edge-deletion problems, Approximation algorithms for discrete polynomial optimization, Note on upper density of quasi-random hypergraphs, Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing, Testing hypergraph colorability, On random sampling in uniform hypergraphs, Testing subgraphs in directed graphs, Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems