Random sampling and approximation of MAX-CSPs

DOI10.1016/S0022-0000(03)00008-4MaRDI QIDQ1886453zbMATH OpenFDO

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

Publication date 18 November 2004

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

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 1263204 (Why is no real title available?)
• scientific article; zbMATH DE number 1301970 (Why is no real title available?)
• scientific article; zbMATH DE number 1754615 (Why is no real title available?)
• scientific article; zbMATH DE number 2119722 (Why is no real title available?)
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• MAX-CUT has a randomized approximation scheme in dense graphs
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the best constants in the Khinchin inequality
• On the discrepancy of combinatorial rectangles
• Probability Inequalities for Sums of Bounded Random Variables
• Property testers for dense constraint satisfaction programs on finite domains
• Property testing and its connection to learning and approximation
• Quick approximation to matrices and applications
• Random sampling and approximation of MAX-CSP problems

Cited in

(20)

• Testing Odd-Cycle-Freeness in Boolean Functions
• Optimal cuts and partitions in tree metrics in polynomial time
• Hypergraph regularity and random sampling
• Sublinear-time Algorithms
• Co-clustering separately exchangeable network data
• The cut metric for probability distributions
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Grothendieck-type inequalities in combinatorial optimization
• Testing odd-cycle-freeness in Boolean functions
• Local and global expansion in random geometric graphs
• Moments of two-variable functions and the uniqueness of graph limits
• Numerical multilinear algebra and its applications
• Optimal graphon estimation in cut distance
• Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1.
• Streaming Euclidean \textsc{Max-Cut}: dimension vs data reduction
• Approximating sparse binary matrices in the cut-norm
• Amplification and Derandomization without Slowdown
• Bounds for graph regularity and removal lemmas
• A dichotomy for minimum cost graph homomorphisms
• Sublinear algorithms for MAXCUT and correlation clustering

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

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