Finding large set covers faster via the representation method

DOI10.4230/LIPICS.ESA.2016.69MaRDI QIDQ4606341zbMATH OpenFDO

Authors Jesper Nederlof

Publication date 2 March 2018

Full work available at URL https://arxiv.org/abs/1608.03439

zbMATH Keywords

exact exponential algorithmsset coverfine-grained complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Combinatorial optimization (90C27) Dynamic programming (90C39)

Recommendations

• Covering and Packing in Linear Space
• Covering and packing in linear space
• Set partitioning via inclusion-exclusion
• Exponential-time approximation of weighted set cover
• Approximating \(k\)-set cover and complementary graph coloring

Cited in

(3)

• A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
• scientific article; zbMATH DE number 7559154 (Why is no real title available?)
• Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.

This page was built for publication: Finding large set covers faster via the representation method

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