scientific article
From MaRDI portal
Publication:2941638
DOI10.4086/toc.2015.v011a007zbMath1335.68097OpenAlexW1586797185MaRDI 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
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (29)
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm ⋮ The complexity of flow expansion and electrical flow expansion ⋮ Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ Unnamed Item ⋮ Time-approximation trade-offs for inapproximable problems ⋮ New Results on Directed Edge Dominating Set ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ Parameterized orientable deletion ⋮ Spy game: FPT-algorithm, hardness and graph products ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ Justifying groups in multiwinner approval voting ⋮ Unnamed Item ⋮ Observation routes and external watchman routes ⋮ Capacity-preserving subgraphs of directed flow networks ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ A connection between sports and matroids: how many teams can we beat? ⋮ Integrated Supply Chain Management via Randomized Rounding ⋮ A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems ⋮ Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics ⋮ The Optimal Design of Low-Latency Virtual Backbones ⋮ Easy capacitated facility location problems, with connections to lot-sizing ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ Complexity of minimum irreducible infeasible subsystem covers for flow networks ⋮ Optimal matroid partitioning problems ⋮ Distributed set cover approximation: Primal-dual with optimal locality ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computing a small agreeable set of indivisible items ⋮ Tight bounds on subexponential time approximation of set cover and related problems
Cites Work
This page was built for publication:
