Detecting points in integer cones of polytopes is double-exponentially hard

DOI10.1137/1.9781611977936.25MaRDI QIDQ6545123zbMATH OpenFDO

Authors Łukasz Kowalik, Alexandra Lassota, Konrad Majewski, Michał Pilipczuk, Marek Sokołowski

Publication date 29 May 2024

Full work available at URL https://doi.org/10.1137/1.9781611977936.25

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(4)

• Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover
• Exact and approximate high-multiplicity scheduling on identical machines
• Tight (double) exponential bounds for identification problems: locating-dominating set and test cover
• Tight (double) exponential bounds for identification problems: locating-dominating set and test cover

This page was built for publication: Detecting points in integer cones of polytopes is double-exponentially hard

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