Name
Abstract | ||
|---|---|---|
This paper proposes an exact algorithm for the Max-Mean dispersion problem ($$Max-Mean DP$$Max-MeanDP), an NP-Hard combinatorial optimization problem whose aim is to select the subset of a set such that the average distance between elements is maximized. The problem admits a natural non-convex quadratic fractional formulation from which a semidefinite programming (SDP) relaxation can be derived. This relaxation can be tightened by means of a cutting plane algorithm which iteratively adds the most violated triangular inequalities. The proposed approach embeds the SDP relaxation and the cutting plane algorithm into a branch and bound framework to solve $$Max-Mean DP$$Max-MeanDP instances to optimality. Computational experiments show that the proposed method is able to solve to optimality in reasonable time instances with up to 100 elements, outperforming other alternative approaches. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s10878-016-0065-1 | J. Comb. Optim. |
Keywords | Field | DocType |
Max-Mean dispersion problem,Semidefinite programming relaxation,Fractional combinatorial optimization | Dispersion (optics),Mathematical optimization,Combinatorics,Branch and bound,Combinatorial optimization problem,Exact algorithm,Quadratic equation,Cutting plane algorithm,Lagrangian relaxation,Mathematics,Semidefinite programming | Journal |
Volume | Issue | ISSN |
34 | 1 | 1382-6905 |
Citations | PageRank | References |
0 | 0.34 | 25 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michele Garraffa | 1 | 14 | 3.03 |
| Federico Della Croce | 2 | 399 | 41.60 |
| Fabio Salassa | 3 | 56 | 9.79 |