The maximum ratio clique problem
- Additional Document Info
- View All
© 2013, Springer-Verlag Berlin Heidelberg. This paper introduces a fractional version of the classical maximum weight clique problem, the maximum ratio clique problem, which is to find a maximal clique that has the largest ratio of benefit and cost weights associated with the clique’s vertices. NP-completeness of the decision version of the problem is established, and three solution methods are proposed. The results of numerical experiments with standard graph instances, as well as with real-life instances arising in finance and energy systems, are reported.
author list (cited authors)
Sethuraman, S., & Butenko, S.