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

Scaling and universality in continuous length combinatorial optimization.

David Aldous1, Allon G Percus

  • 1Department of Statistics, University of California, Berkeley, CA 94720-3860, USA.

Proceedings of the National Academy of Sciences of the United States of America
|September 25, 2003
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

How out-group animosity can shape partisan divisions: A model of affective polarization.

PNAS nexus·2025
Same author

Addressing quantum's "fine print" with efficient state preparation and information extraction for quantum algorithms and geologic fracture networks.

Scientific reports·2024
Same author

Clique densification in networks.

Physical review. E·2023
Same author

The transsortative structure of networks.

Proceedings. Mathematical, physical, and engineering sciences·2020
Same author

Optimal geometry of transportation networks.

Physical review. E·2019
Same author

Author Correction: Neighbor-Neighbor Correlations Explain Measurement Bias in Networks.

Scientific reports·2018
Same journal

Tau protein as a regulator of mitochondrial function and dynamics.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

A scalable, dividing cell model for the robust propagation and quantification of human sporadic Creutzfeldt-Jakob disease prions.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Epigenetic regulation of mesenchymal BMP signaling directs postnatal organ innervation.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Single-shot wide-field biochemical imaging at 1 kHz frame rate.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Morphogenesis and topological evolution of a frustrated nematic liquid crystal under confinement.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

B cell-intrinsic CXCR3 drives efficient generation of ectopic pulmonary germinal center responses to influenza A virus infection.

Proceedings of the National Academy of Sciences of the United States of America·2026
See all related articles

We studied how solution costs change in combinatorial optimization problems when optimal solutions are slightly perturbed. For minimum spanning trees, cost increases as delta squared; for matching and traveling salesman problems, it increases as delta cubed.

Area of Science:

  • Computational complexity
  • Statistical physics
  • Combinatorial optimization

Background:

  • Combinatorial optimization problems are fundamental in computer science and operations research.
  • Understanding solution landscape sensitivity is crucial for algorithm design and analysis.
  • Random ensembles provide a framework to study generic properties of these problems.

Purpose of the Study:

  • To investigate the scaling of solution cost increase under small perturbations.
  • To analyze the behavior of minimum spanning tree, minimum matching, and traveling salesman problems.
  • To explore potential classification of optimization problems based on cost-perturbation scaling.

Main Methods:

  • Analysis of random ensembles of combinatorial optimization problems.

Related Experiment Videos

  • Mathematical derivation of cost increase scaling for minimum spanning tree.
  • Monte Carlo simulations and mean-field model analysis for minimum matching and traveling salesman problems.
  • Perturbation analysis of optimal solutions with a small parameter delta.

    • Main Results:

    • The cost increase for minimum spanning tree scales as delta^2.
    • The cost increase for minimum matching and traveling salesman problems scales as delta^3 in dimensions d >= 2.
    • Observed scaling exponents in simulations for dimensions 2, 3, and 4.
    • Theoretical confirmation of delta^3 scaling via mean-field analysis.

    Conclusions:

    • The scaling exponent of cost increase provides a quantitative measure of solution sensitivity.
    • Different combinatorial optimization problems exhibit distinct scaling behaviors.
    • These scaling exponents may classify problems into universality classes, analogous to statistical physics.