Detecting high log-densities
From MaRDI portal
Publication:2875146
DOI10.1145/1806689.1806719zbMath1293.05200MaRDI QIDQ2875146
Aditya Bhaskara, Eden Chlamtáč, Uriel Feige, Aravindan Vijayaraghavan, Moses Charikar
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1806689.1806719
05C80: Random graphs (graph-theoretic aspects)
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
05C42: Density (toughness, etc.)
Related Items
Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem, Graph Stabilization: A Survey, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Breaking thermaxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem, Unnamed Item, Maximizing Convergence Time in Network Averaging Dynamics Subject to Edge Removal, Finding Cliques in Social Networks: A New Distribution-Free Model, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, Convex Optimization for Group Feature Selection in Networked Data, Testing for Dense Subsets in a Graph via the Partition Function, Unnamed Item, Unnamed Item, Approximating \(k\)-forest with resource augmentation: a primal-dual approach, Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph, 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, On solving the densestk-subgraph problem on large graphs, The Maximum Exposure Problem., Unnamed Item, New algorithms for a simple measure of network partitioning, Vertex downgrading to minimize connectivity, A lifted-space dynamic programming algorithm for the quadratic knapsack problem, An \(O(\sqrt{k})\)-approximation algorithm for minimum power \(k\) edge disjoint \(st\)-paths, Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs, The hospitals/residents problem with lower quotas, PTAS for densest \(k\)-subgraph in interval graphs, Projection algorithms for nonconvex minimization with application to sparse principal component analysis, Asymptotic behavior of the quadratic knapsack problem, Finding a collective set of items: from proportional multirepresentation to group recommendation, Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster, Survivable network activation problems, On approximating string selection problems with outliers, Improved approximation algorithms for directed Steiner forest, An approximation algorithm for the generalized \(k\)-multicut problem, On the approximability of some degree-constrained subgraph problems, On set expansion problems and the small set expansion conjecture, Improved approximation algorithms for label cover problems, The ordered covering problem, Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs, Strengthening ties towards a highly-connected world, Computing the partition function for graph homomorphisms with multiplicities, On size-constrained minimum \(s\mathrm{-}t\) cut problems and size-constrained dense subgraph problems, Approximation and hardness results for the max \(k\)-uncut problem, On the approximability of the minimum rainbow subgraph problem and other related problems, Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem, Approximation of the quadratic knapsack problem, Parameterized and approximation complexity of \textsc{Partial VC Dimension}, Improving man-optimal stable matchings by minimum change of preference lists, Using shortcut edges to maximize the number of triangles in graphs, The densest subgraph problem with a convex/concave size function, In search of the densest subgraph, Graph classes and approximability of the happy set problem, New approximations and hardness results for submodular partitioning problems, The maximum exposure problem, Computational barriers to estimation from low-degree polynomials, Hypergraph \(k\)-cut in randomized polynomial time, Finding densest \(k\)-connected subgraphs, Parameterized approximability of maximizing the spread of influence in networks, A primal-dual algorithm for the minimum partial set multi-cover problem, Partitioning a graph into small pieces with applications to path transversal, Finding connected \(k\)-subgraphs with high density, Additive stabilizers for unstable graphs, Euclidean prize-collecting Steiner forest, On the generalized multiway cut in trees problem, On the \(k\)-edge-incident subgraph problem and its variants, Threshold-based preprocessing for approximating the weighted dense \(k\)-subgraph problem, Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis, Complexity and approximability of the happy set problem, Finding dense subgraphs with maximum weighted triangle density, Computing densest \(k\)-subgraph with structural parameters, New algorithms for a simple measure of network partitioning, Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem, Finding Connected Dense $$k$$-Subgraphs, Approximation and Hardness Results for the Max k-Uncut Problem, A Dynamic Programming Heuristic for the Quadratic Knapsack Problem, Bin Packing with Colocations, The Densest $k$-Subhypergraph Problem, Approximation of the Quadratic Knapsack Problem, Polynomial-Time Algorithms for Multiple-Arm Identification with Full-Bandit Feedback
