Improved FPT approximation scheme and approximate kernel for biclique-free max \(k\)-weight SAT: greedy strikes back

DOI10.1016/J.TCS.2024.115033MaRDI QIDQ6664061

Publication date: 16 January 2025

Published in: Theoretical Computer Science (Search for Journal in Brave)

Analysis of algorithms (68W40) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Which problems have strongly exponential complexity?
On weighted vs unweighted versions of combinatorial optimization problems
Pipage rounding: a new method of constructing algorithms with proven performance guarantee
Approximation algorithms for maximization problems arising in graph partitioning
A threshold of ln n for approximating set cover
Intersection Theorems for Systems of Sets
An analysis of approximations for maximizing submodular set functions—I
Chamberlin--Courant Rule with Approval Ballots: Approximating the MaxCover Problem with Bounded Frequencies in FPT Time
Kernelization
Fixed-Parameter Tractability and Completeness I: Basic Results
Better Balance by Being Biased
Lossy kernelization
Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
Parameterized Algorithms
On a problem of K. Zarankiewicz
Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
Algorithms - ESA 2003
On the complexity of \(k\)-SAT
Best possible approximation algorithm for MAX SAT with cardinality constraint.
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems
Parameterized approximation scheme for biclique-free max \(k\)-weight SAT and max coverage
Max-SAT with cardinality constraint parameterized by the number of clauses
A note on max \(k\)-vertex cover: faster FPT-AS, smaller approximate kernel and improved approximation
Parameterized matroid-constrained maximum coverage

This page was built for publication: Improved FPT approximation scheme and approximate kernel for biclique-free max \(k\)-weight SAT: greedy strikes back

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