Random sampling and approximation of MAX-CSPs

DOI10.1016/S0022-0000(03)00008-4zbMath1160.68537MaRDI QIDQ1886453

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

Publication date: 18 November 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

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

Related Items

Sublinear-time Algorithms, Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing, Moments of two-variable functions and the uniqueness of graph limits, A dichotomy for minimum cost graph homomorphisms, Numerical multilinear algebra and its applications, Grothendieck-Type Inequalities in Combinatorial Optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quick approximation to matrices and applications
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• Property testers for dense constraint satisfaction programs on finite domains
• Property testing and its connection to learning and approximation
• Random sampling and approximation of MAX-CSP problems
• On the best constants in the Khinchin inequality
• On the discrepancy of combinatorial rectangles
• Probability Inequalities for Sums of Bounded Random Variables
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities