Submodular Max-SAT

DOI10.1007/978-3-642-23719-5_28MaRDI QIDQ3092241zbMATH OpenOpenAlexFDO

Authors Iftah Gamzu, Ran Roth, Yossi Azar

Publication date 16 September 2011

Published in Algorithms – ESA 2011 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-23719-5_28

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Recommendations

• Maximizing Non-monotone Submodular Functions
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• Submodular maximization by simulated annealing
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Maximizing a monotone submodular function subject to a matroid constraint

Cited in

(9)

• On extensions of the deterministic online model for bipartite matching and max-sat
• Online BP functions maximization
• Online algorithms for BP functions maximization
• Improved inapproximability for submodular maximization
• Online submodular maximization with preemption
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
• Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid
• Two-stage submodular maximization problem beyond nonnegative and monotone

This page was built for publication: Submodular Max-SAT

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