Parameterized approximation scheme for biclique-free max k-weight SAT and max coverage

DOI10.1137/1.9781611977554.CH143MaRDI QIDQ6538677zbMATH OpenFDO

Authors Pallavi Jain, Lawqueen Kanesh, Fahad Panolan, Souvik Saha, Abhishek Sahu, Saket Saurabh, Anannya Upasana

Publication date 14 May 2024

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Recommendations

• Improved FPT approximation scheme and approximate kernel for biclique-free max \(k\)-weight SAT: greedy strikes back
• On MAX-SAT with cardinality constraint
• On MAX-SAT with cardinality constraint
• Parameterized exact and approximation algorithms for maximum \(k\)-set cover and related satisfiability problems
• scientific article; zbMATH DE number 1979498

Cited in

(4)

• On MAX-SAT with cardinality constraint
• On MAX-SAT with cardinality constraint
• Improved FPT approximation scheme and approximate kernel for biclique-free max \(k\)-weight SAT: greedy strikes back
• Max-SAT with cardinality constraint parameterized by the number of clauses

This page was built for publication: Parameterized approximation scheme for biclique-free max \(k\)-weight SAT and max coverage

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