Publication:2941638
From MaRDI portal
DOI10.4086/toc.2015.v011a007zbMath1335.68097MaRDI QIDQ2941638
Publication date: 21 August 2015
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2015.v011a007
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, Integrated Supply Chain Management via Randomized Rounding, Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics, The Optimal Design of Low-Latency Virtual Backbones, Time-approximation trade-offs for inapproximable problems, A connection between sports and matroids: how many teams can we beat?, A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems, Complexity of minimum irreducible infeasible subsystem covers for flow networks, Easy capacitated facility location problems, with connections to lot-sizing, Domination chain: characterisation, classical complexity, parameterised complexity and approximability, Parameterized orientable deletion, Computing a small agreeable set of indivisible items, Structural parameters, tight bounds, and approximation for \((k, r)\)-center, Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
Cites Work