Finding large set covers faster via the representation method

DOI10.4230/LIPICS.ESA.2016.69zbMATH Open1397.68107arXiv1608.03439MaRDI QIDQ4606341FDOQ4606341

Authors: Jesper Nederlof 

Publication date: 2 March 2018

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

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

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)

Cited In (3)

• Title not available (Why is that?)
• Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
• A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics

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)