On solving the densestk-subgraph problem on large graphs
From MaRDI portal
Publication:5859000
DOI10.1080/10556788.2019.1595620zbMath1464.90086arXiv1901.06344OpenAlexW2962753098MaRDI QIDQ5859000
Publication date: 15 April 2021
Published in: Optimization Methods and Software (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1901.06344
Large-scale problems in mathematical programming (90C06) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Combinatorial optimization (90C27)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- PTAS for densest \(k\)-subgraph in interval graphs
- Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster
- Subgradient methods for huge-scale optimization problems
- Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
- Good solutions to discrete noxious location problems via metaheuristics
- Nuclear norm minimization for the planted clique and biclique problems
- A new polynomial-time algorithm for linear programming
- Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
- Variable neighborhood search for the heaviest \(k\)-subgraph
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- Clustering and domination in perfect graphs
- A polynomial-time algorithm for a class of linear complementarity problems
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- \(k\)-edge subgraph problems
- Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
- Approximation of dense-\(n/2\)-subgraph and the complement of min-bisection
- An application of tabu search heuristic for the maximum edge-weighted subgraph problem
- Solving \(k\)-cluster problems to optimality with semidefinite programming
- Random block coordinate descent methods for linearly constrained optimization over networks
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
- An \(O(n^ 3L)\) primal interior point algorithm for convex quadratic programming
- Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
- Detecting high log-densities
- Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
- Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
- Finding Dense Subgraphs with Size Bounds
- Heuristic and Special Case Algorithms for Dispersion Problems
- Linear Programming in O([n3/ln nL) Operations]
- Using a Conic Bundle Method to Accelerate Both Phases of a Quadratic Convex Reformulation
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Semidefinite relaxations for partitioning, assignment and ordering problems
- The dense \(k\)-subgraph problem
- Different Formulations for Solving the HeaviestK-Subgraph Problem
