Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
From MaRDI portal
Publication:4978037
DOI10.1145/3055399.3055412zbMath1370.68110arXiv1611.05991OpenAlexW2552383377MaRDI QIDQ4978037
Publication date: 17 August 2017
Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1611.05991
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (44)
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm ⋮ Dual domination problems in graphs ⋮ Maximizing Convergence Time in Network Averaging Dynamics Subject to Edge Removal ⋮ The Densest $k$-Subhypergraph Problem ⋮ Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ Election control through social influence with voters' uncertainty ⋮ Complexity and approximability of the happy set problem ⋮ Orienteering for electioneering ⋮ Additive stabilizers for unstable graphs ⋮ A note on hardness of computing recursive teaching dimension ⋮ Computing densest \(k\)-subgraph with structural parameters ⋮ An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs ⋮ An \(O(\sqrt{k})\)-approximation algorithm for minimum power \(k\) edge disjoint \(st\)-paths ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Unnamed Item ⋮ Unnamed Item ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ Approximate Clustering with Same-Cluster Queries ⋮ Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds ⋮ Hypergraph \(k\)-cut in randomized polynomial time ⋮ Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder ⋮ LP Relaxation and Tree Packing for Minimum $k$-Cut ⋮ Approximation and hardness of shift-Bribery ⋮ Election Manipulation on Social Networks: Seeding, Edge Removal, Edge Addition ⋮ In search of the densest subgraph ⋮ Approximation algorithm for the partial set multi-cover problem ⋮ Graph classes and approximability of the happy set problem ⋮ Election control through social influence with unknown preferences ⋮ The ordered covering problem ⋮ A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks ⋮ Jointly low-rank and bisparse recovery: Questions and partial answers ⋮ Multitasking Capacity: Hardness Results and Improved Constructions ⋮ A primal-dual algorithm for the minimum partial set multi-cover problem ⋮ On the complexity of fair house allocation ⋮ Partitioning a graph into small pieces with applications to path transversal ⋮ Computing the \(k\) densest subgraphs of a graph ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time ⋮ Approximation algorithm for minimum partial multi-cover under a geometric setting ⋮ New approximations and hardness results for submodular partitioning problems
This page was built for publication: Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
