Detecting high log-densities, an O(n^1/4) approximation for densest k-subgraph
From MaRDI portal
Publication:2875146
Recommendations
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- The dense \(k\)-subgraph problem
- Finding Dense Subgraphs with Size Bounds
- A deterministic approximation algorithm for the densest \(k\)-subgraph problem
- Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph
Cited in
(only showing first 100 items - show all)- 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
- 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
- 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
- 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
- Projection algorithms for nonconvex minimization with application to sparse principal component analysis
- The densest k-subhypergraph problem
- Approximation of the quadratic knapsack problem
- Asymptotic behavior of the quadratic knapsack problem
- Finding a collective set of items: from proportional multirepresentation to group recommendation
- Polynomial-Time Algorithms for Multiple-Arm Identification with Full-Bandit Feedback
- 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
- Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory's theorem
- ETH hardness for densest-k-subgraph with perfect completeness
- Graph stabilization: a survey
- On set expansion problems and the small set expansion conjecture
- Breaking thermaxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem
- Finding cliques in social networks: a new distribution-free model
- Low rank approximation in the presence of outliers
- Sherali-Adams integrality gaps matching the log-density threshold
- Maximizing convergence time in network averaging dynamics subject to edge removal
- The norms of graph spanners
- 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
- On the hardness of approximating the \(k\)-\textsc{Way Hypergraph Cut} problem
- Almost polynomial hardness of node-disjoint paths in grids
- Testing for dense subsets in a graph via the partition function
- Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph
- Approximation algorithms and hardness of the \(k\)-route cut problem
- On solving the densest \(k\)-subgraph problem on large graphs
- The Maximum Exposure 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
- 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
- Vertex downgrading to minimize connectivity
- A lifted-space dynamic programming algorithm for the quadratic knapsack problem
- scientific article; zbMATH DE number 7758340 (Why is no real title available?)
- New algorithms for a simple measure of network partitioning
- 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
- Improved approximation algorithms for label cover problems
- Sum-of-squares lower bounds for densest k-subgraph
- Cluster before you hallucinate: node-capacitated network design and energy efficient routing
- A (B + 1)-approximation for network flow interdiction with unit costs
- The sparse sequences of graphs
- A \(2\sqrt{2k}\)-approximation algorithm for minimum power \(k\) edge disjoint \(st\)-paths
- The low-degree hardness of finding large independent sets in sparse random hypergraphs
- Planted models for the densest k-subgraph problem
- On the hardness and approximation of the densest k-subgraph problem in parameterized metric graphs
- Approximation algorithms for two extensions of min-k-union
- The ground-set-cost budgeted maximum coverage problem
- Approximation algorithm for extracting densest subgraph over matching-like constraints
- Optirefine: densest subgraphs and maximum cuts with k refinements
- On the generalized mean densest subgraph problem: complexity and algorithms
- The quadratic knapsack problem
- On extensions of min-k-union
- Solving the multiobjective quasi-clique problem
- Dense graph partitioning on sparse and dense graphs
- Approximation algorithm for the minimum interval partial multi-cover problem
- Detection of dense subhypergraphs by low-degree polynomials
- The ordered covering problem
- The strongish planted clique hypothesis and its consequences
This page was built for publication: Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875146)
