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