An exact semidefinite programming approach for the max-mean dispersion problem

Michele Garraffa (), Federico Della Croce and Fabio Salassa
Additional contact information
Michele Garraffa: DAUIN, Politecnico di Torino
Federico Della Croce: DAUIN, Politecnico di Torino
Fabio Salassa: DAUIN, Politecnico di Torino

Journal of Combinatorial Optimization, 2017, vol. 34, issue 1, No 5, 93 pages

Abstract: Abstract This paper proposes an exact algorithm for the Max-Mean dispersion problem ( $$Max-Mean DP$$ M a x - M e a n D P ), 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$$ M a x - M e a n D P 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.

Keywords: Max-Mean dispersion problem; Semidefinite programming relaxation; Fractional combinatorial optimization (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0065-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:34:y:2017:i:1:d:10.1007_s10878-016-0065-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-0065-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().