Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Payoff-monotonic game dynamics and the maximum clique problem.

Marcello Pelillo1, Andrea Torsello

  • 1Dipartimento di Informatica, Università Ca' Foscari di Venezia 30172 Venezia Mestre, Italy. pelillo@dsi.unive.it

Neural Computation
|April 6, 2006
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Vector Flows That Compute the Capacity of Discrete Memoryless Channels.

Entropy (Basel, Switzerland)·2025
Same author

Graph Kernel Neural Networks.

IEEE transactions on neural networks and learning systems·2024
Same author

The Group Loss++: A Deeper Look Into Group Loss for Deep Metric Learning.

IEEE transactions on pattern analysis and machine intelligence·2022
Same author

Deep Demosaicing for Polarimetric Filter Array Cameras.

IEEE transactions on image processing : a publication of the IEEE Signal Processing Society·2022
Same author

Object Detection in Aerial Images: A Large-Scale Benchmark and Challenges.

IEEE transactions on pattern analysis and machine intelligence·2021
Same author

You Can't See Me: Anonymizing Graphs Using the Szemerédi Regularity Lemma.

Frontiers in big data·2021

New evolutionary game dynamics offer faster and more accurate solutions for the maximum clique problem. An annealing approach helps avoid local optima, outperforming current methods.

Area of Science:

  • Computational Mathematics
  • Graph Theory
  • Evolutionary Game Theory

Background:

  • Replicator equations, a tool from evolutionary game theory, are effective for solving the maximum clique problem.
  • The maximum clique problem can be framed as a continuous quadratic program, leveraging dynamical system properties.

Purpose of the Study:

  • Generalize existing evolutionary game dynamics for solving quadratic programs and the maximum clique problem.
  • Introduce and analyze a novel class of payoff-monotonic dynamics.
  • Develop an annealed imitation heuristic to overcome local optima in these models.

Main Methods:

  • Introduced a family of payoff-monotonic dynamics, generalizing replicator equations.
  • Analyzed the dynamical properties and Lyapunov functions of these dynamics.

Related Experiment Videos

  • Investigated annealed imitation heuristics by varying a regularization parameter.

    • Main Results:

    • Payoff-monotonic dynamics share beneficial properties with replicator equations, offering faster and equally accurate solutions.
    • The proposed annealed imitation heuristics effectively avoid poor local optima.
    • New models outperform state-of-the-art neural network algorithms for maximum clique.

    Conclusions:

    • Payoff-monotonic dynamics provide a powerful and flexible framework for tackling the maximum clique problem.
    • Annealing strategies significantly enhance the performance of evolutionary dynamics by escaping local optima.
    • This research presents a promising new direction for combinatorial optimization using game-theoretic approaches.