|
 
|
[BR08] A Deterministic Approximation Algorithm for the Densest k-Subgraph Problem
Revue Internationale avec comité de lecture : Journal International Journal of Operational Research, vol. 3(3), pp. 301-314, 2008, (doi:10.1504/IJOR.2008.017534)Mots clés: Densest k-Subgraph Problem ; Approximation algorithms ; Detreministic ; Linear programming
Résumé:
In the Densest k-Subgraph problem (DSP), we are given an
undirected weighted graph G=(V,E) with n vertices
v1,...,vn. We seek to find a subset of k
vertices (k belonging to {1,...,n}) which maximizes the number
of edges which have their two endpoints in the subset. This problem
is NP-hard even for bipartite graphs, and no polynomial-time
algorithm with a fixed performance guarantee is known for the
general case. Several authors have proposed randomized approximation
algorithms for particular cases (especially when k=n/c,
c>1). But derandomization techniques are not easy to apply here
because of the cardinality constraint, and can have a high
computational cost. In this paper we present a deterministic
max(d,8/9c)-approximation algorithm for the
Densest k-Subgraph Problem (where d is the density of
G). The complexity of our algorithm is only the one of linear
programming. This result is obtained by using particular optimal
solutions of a linear program associated with the classical 0-1
quadratic formulation of DSP.
Equipe:
oc
Collaboration:
LIPN
BibTeX
| @article { | |||
| BR08, | |||
| title | = | "{A Deterministic Approximation Algorithm for the Densest k-Subgraph Problem}", | |
| author | = | "A. Billionnet and F. Roupin", | |
| journal | = | "International Journal of Operational Research", | |
| year | = | 2008, | |
| volume | = | 3, | |
| number | = | 3, | |
| pages | = | "301-314", | |
| doi | = | "10.1504/IJOR.2008.017534", | |
| } | |||
