Name
Title | ||
|---|---|---|
Fast population game dynamics for dominant sets and other quadratic optimization problems |
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-14980-1_26 | SSPR/SPR |
Keywords | Field | DocType |
fast population game dynamic,average population payoff,large class,asymptotically stable,dominant set,computer vision,quadratic optimization problem,linear time,proposed dynamic,non-constant trajectory,immunization process,dominating set,space complexity,quadratic optimization | Population,Mathematical optimization,Standard algorithms,Strategy,Quadratic programming,Time complexity,Nash equilibrium,Mathematics,Stability theory,Stochastic game | Conference |
Volume | ISSN | ISBN |
6218 | 0302-9743 | 3-642-14979-0 |
Citations | PageRank | References |
3 | 0.40 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samuel Rota Bulò | 1 | 564 | 33.69 |
| Immanuel M. Bomze | 2 | 922 | 87.13 |
| Marcello Pelillo | 3 | 1888 | 150.33 |