Approximation and Online Algorithms

DOI10.1007/11671411MaRDI QIDQ5898461zbMATH OpenOpenAlexFDO

Authors Adi Avidor, Ido Berkovitch, Uri Zwick

Publication date 12 February 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11671411

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Recommendations

• Improved approximation algorithms for MAX SAT
• Publication:4952605
• Improved approximations for max set splitting and max NAE SAT
• Approximation algorithms for the maximum satisfiability problem
• An approximation algorithm for MAX 3-SAT

Cited in

(26)

• Revisiting maximum satisfiability and related problems in data streams
• Locally defined independence systems on graphs
• When polynomial approximation meets exact computation
• Improved approximations for max set splitting and max NAE SAT
• An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT
• A simple rounding scheme for multistage optimization
• Approximating Succinct MaxSat
• scientific article; zbMATH DE number 1979498 (Why is no real title available?)
• Revisiting maximum satisfiability and related problems in data streams
• Simple approximation algorithms for MAXNAESP and hypergraph 2-colorability
• On the mysteries of MAX NAE-SAT
• Local search to approximate MAX NAE-\(k\)-SAT tightly
• An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT.
• Complexity of approximating CSP with balance/hard constraints
• Simple approximation algorithms for balanced MAX~2SAT
• Improved approximation algorithms for MAX SAT
• When polynomial approximation meets exact computation
• Approximating Max NAE-\(k\)-SAT by anonymous local search
• On extensions of the deterministic online model for bipartite matching and max-sat
• Solving the weighted MAX-SAT problem using the dynamic convexized method
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}
• Approximation Algorithms for CSPs
• An approximation algorithm for MAX-2-SAT with cardinality constraint
• Approximating MAX SAT by moderately exponential and parameterized algorithms
• scientific article; zbMATH DE number 1445292 (Why is no real title available?)

This page was built for publication: Approximation and Online Algorithms

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