The maximum ratio clique problem Academic Article uri icon

abstract

  • © 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.

citation count

  • 7

publication date

  • January 2015