On solving the densest k-subgraph problem on large graphs
From MaRDI portal
Publication:5859000
Abstract: The densest -subgraph problem is the problem of finding a -vertex subgraph of a graph with the maximum number of edges. In order to solve large instances of the densest -subgraph problem, we introduce two algorithms that are based on the random coordinate descent approach. Although it is common use to update at most two random coordinates simultaneously in each iteration of an algorithm, our algorithms may simultaneously update many coordinates. We show the benefit of updating more than two coordinates simultaneously for solving the densest -subgraph problem, and solve large problem instances with up to vertices.
Recommendations
- The dense \(k\)-subgraph problem
- A deterministic approximation algorithm for the densest \(k\)-subgraph problem
- Finding Dense Subgraphs with Size Bounds
- Exact and approximation algorithms for densest \(k\)-subgraph (extended abstract)
- Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
Cites work
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- scientific article; zbMATH DE number 3677572 (Why is no real title available?)
- scientific article; zbMATH DE number 26490 (Why is no real title available?)
- scientific article; zbMATH DE number 3637614 (Why is no real title available?)
- A new polynomial-time algorithm for linear programming
- A polynomial-time algorithm for a class of linear complementarity problems
- An \(O(n^ 3L)\) primal interior point algorithm for convex quadratic programming
- An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
- An application of tabu search heuristic for the maximum edge-weighted subgraph problem
- Approximation algorithms for maximization problems arising in graph partitioning
- Approximation of dense-n/2-subgraph and the complement of min-bisection
- Clustering and domination in perfect graphs
- Computational results of a semidefinite branch-and-bound algorithm for k-cluster
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- Different Formulations for Solving the HeaviestK-Subgraph Problem
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
- Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
- Finding Dense Subgraphs with Size Bounds
- Good solutions to discrete noxious location problems via metaheuristics
- Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
- Heuristic and Special Case Algorithms for Dispersion Problems
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Linear Programming in O([n3/ln n]L) Operations
- Nuclear norm minimization for the planted clique and biclique problems
- PTAS for densest \(k\)-subgraph in interval graphs
- Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Random block coordinate descent methods for linearly constrained optimization over networks
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Solving \(k\)-cluster problems to optimality with semidefinite programming
- Subgradient methods for huge-scale optimization problems
- The dense \(k\)-subgraph problem
- Using a conic bundle method to accelerate both phases of a quadratic convex reformulation
- Variable neighborhood search for the heaviest \(k\)-subgraph
- \(k\)-edge subgraph problems
Cited in
(10)- scientific article; zbMATH DE number 7626720 (Why is no real title available?)
- A note on the approximability of the dense subgraph problem.
- A deterministic approximation algorithm for the densest \(k\)-subgraph problem
- In search of dense subgraphs: How good is greedy peeling?
- On convergence of a \(q\)-random coordinate constrained algorithm for non-convex problems
- Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
- Convex optimization for the densest subgraph and densest submatrix problems
- An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
- Computing the \(k\) densest subgraphs of a graph
- Practical parallel algorithms for near-optimal densest subgraphs on massive graphs
This page was built for publication: On solving the densest \(k\)-subgraph problem on large graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5859000)
