Jove
Visualize
Contact Us

Related Experiment Videos

Approximation algorithms

A S Schulz1, D B Shmoys, D P Williamson

  • 1Fachbereich Mathematik, Technische Universitat Berlin, Strasse des 17. Juni 136, 10623 Berlin, Germany.

Proceedings of the National Academy of Sciences of the United States of America
|December 5, 1997
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

Diagnosis and severity criteria for sinusoidal obstruction syndrome/veno-occlusive disease in pediatric patients: a new classification from the European society for blood and marrow transplantation.

Bone marrow transplantation·2017
Same author

Successful second haploidentical SCT in osteopetrosis.

Bone marrow transplantation·2010
Same author

Osteopetrosis due to homozygous chloride channel ClCN7 mutation mimicking metabolic disease with haematological and neurological impairment.

Klinische Padiatrie·2009
Same author

Successful hematopoietic stem-cell transplantation in a patient with chronic granulomatous disease and McLeod phenotype sensitized to Kx and K antigens.

Bone marrow transplantation·2009
Same author

Patients with early relapse of primary hemophagocytic syndromes or with persistent CNS involvement may benefit from immediate hematopoietic stem cell transplantation.

Bone marrow transplantation·2009
Same author

Stem cell transplantation in children with infantile osteopetrosis is associated with a high incidence of VOD, which could be prevented with defibrotide.

Bone marrow transplantation·2006
Same journal

Chemotactic self-organization captures the dynamics of mammalian hair follicle patterning.

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

Tomographic imaging of superconducting order using particle-hole interference.

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

Inhibitory potential of autologous neutralizing antibodies sets quantitative limits on the rebound-competent HIV-1 reservoir.

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

Inferring epidemiological parameters under an infectious phylogeography model with visitor dynamics.

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

Analytical modeling for suction cup designs for skin-interfaced wearable devices.

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

Improving cell-free metabolism through direct integration of artificial respiratory chains.

Proceedings of the National Academy of Sciences of the United States of America·2026
See all related articles
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

Industries use large-scale optimization problems for efficiency. Breakthroughs in approximation algorithms now provide provably near-optimal solutions quickly, improving upon ad hoc methods.

Area of Science:

  • Theoretical Computer Science
  • Discrete Mathematics
  • Operations Research

Background:

  • Global competition and market changes necessitate increased corporate efficiency.
  • Industries model operational aspects using large-scale optimization problems with millions of binary decisions.
  • Finding exact solutions for these problems is computationally infeasible.

Purpose of the Study:

  • To address the challenge of solving large-scale optimization problems efficiently.
  • To highlight the advancements in approximation algorithms for optimization.
  • To discuss the theoretical underpinnings and performance guarantees of these algorithms.

Main Methods:

  • Review of recent breakthroughs in approximation algorithm design.
  • Analysis of the theoretical limits for obtaining performance guarantees.

Related Experiment Videos

  • Focus on algorithms that provide provably near-optimal solutions.

    • Main Results:

    • Significant progress has been made in the design of approximation algorithms over the last six years.
    • Understanding of the limits to performance guarantees has also advanced.
    • These algorithms offer a practical alternative to ad hoc methods for industry.

    Conclusions:

    • Approximation algorithms offer a viable approach to solving complex optimization problems in industry.
    • Recent theoretical advancements enhance the reliability and efficiency of these methods.
    • This field represents a flourishing area of research in computer science and mathematics.