Random sampling and approximation of MAX-CSP problems

DOI10.1145/509907.509945MaRDI QIDQ3579226zbMATH OpenOpenAlexFDO

Authors Noga Alon, W. Fernandez de la Vega, R. Kannan, Marek Karpinski

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)

Cited in

(10)

• Testing hypergraph colorability
• Random sampling and approximation of MAX-CSPs
• Additive approximation for edge-deletion problems
• Hardness of fully dense problems
• Approximation schemes for the betweenness problem in tournaments and related ranking problems
• Approximation algorithms for discrete polynomial optimization
• Note on upper density of quasi-random hypergraphs
• On random sampling in uniform hypergraphs
• Testing subgraphs in directed graphs
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing

This page was built for publication: Random sampling and approximation of MAX-CSP problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3579226)