Approximation and Online Algorithms

DOI10.1007/11671411zbMATH Open1125.68426OpenAlexW4210634114MaRDI QIDQ5898461FDOQ5898461

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

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

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Cited In (26)

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

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)