Optimization Online


Fast population game dynamics for dominant sets and other quadratic optimization problems

Samuel Rota-Bul\'o (srotabul***at***dsi.unive.it)
Immanuel M. Bomze (immanuel.bomze***at***univie.ac.at)
Marcello Pelillo (pelillo***at***dsi.unive.it)

Abstract: We propose a fast population game dynamics, motivated by the analogy with infection and immunization processes within a population of ``players,'' for finding dominant sets, a powerful graph-theoretical notion of a cluster. Each step of the proposed dynamics is shown to have a linear time/space complexity and we show that, under the assumption of symmetric affinities, the average population payoff is strictly increasing along any non-constant trajectory, thereby allowing us to prove that dominant sets are asymptotically stable (i.e., attractive) points for the proposed dynamics. The approach is general and can be applied to a large class of quadratic optimization problems arising in computer vision. Experimentally, the proposed dynamics is found to be orders of magnitude faster than and as accurate as standard algorithms.

Keywords: pairwise clustering, linear-time complexity

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Other Topics (Game Theory )

Category 3: Applications -- Science and Engineering (Data-Mining )

Citation: Technical Report TR-ISDS 2010-04, Univ. of Vienna

Download: [PDF]

Entry Submitted: 05/20/2010
Entry Accepted: 05/20/2010
Entry Last Modified: 06/02/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society