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 Concept Videos

Linear Approximation in Time Domain01:21

Linear Approximation in Time Domain

347
Nonlinear systems often require sophisticated approaches for accurate modeling and analysis, with state-space representation being particularly effective. This method is especially useful for systems where variables and parameters vary with time or operating conditions, such as in a simple pendulum or a translational mechanical system with nonlinear springs.
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length,...
347
Approximate Number Sense Test04:17

Approximate Number Sense Test

8.0K
Source: Laboratory of Jonathan Flombaum—Johns Hopkins University
8.0K
Exponential Growth01:29

Exponential Growth

24
Bacterial populations exhibit exponential growth when conditions such as nutrient availability and temperature are favorable. In this phase, cells reproduce through binary fission, where each cell divides into two identical daughter cells. This process causes the population to double at regular intervals, resulting in a growth rate that is directly proportional to the current number of cells. As the population increases, the number of new cells formed during each generation also grows, creating...
24
Linearization and Approximation01:26

Linearization and Approximation

24
Linearization is a mathematical technique used to approximate complex, nonlinear functions with simpler linear models in the vicinity of a chosen reference point. The method is based on the idea that, although a function may be difficult to evaluate exactly, its behavior near a specific input value can often be closely approximated by the tangent line at that point. This approach is particularly useful when small deviations from a known value are involved.Consider the square root function, for...
24
Exponential and Sinusoidal Signals01:18

Exponential and Sinusoidal Signals

693
The exponential function is crucial for characterizing waveforms that rise and decay rapidly. This continuous-time exponential function is defined using exponential terms with constants α and A. When both constants are real, the function is represented as,
693
Application of Linearization and Approximation01:29

Application of Linearization and Approximation

67
A drone flying through complex terrain often relies on more than one sensing method to estimate small changes in altitude. Along with direct measurements, air pressure provides a useful indirect indicator of vertical movement. Atmospheric pressure decreases as altitude increases, and this relationship is commonly described using an exponential model. Although accurate, converting pressure measurements into altitude values requires calculations that are too complex to perform repeatedly during...
67

You might also read

Related Articles

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

Sort by
Same author

Early Diagnosis of Gall Bladder Cancer: An Appeal.

South Asian journal of cancer·2025
Same author

Successful Postpartum Outcome of Placenta In Situ in a Case of Placenta Percreta: A Case Study.

Journal of obstetrics and gynaecology of India·2022
Same author

On the Fine-grained Parameterized Complexity of Partial Scheduling to Minimize the Makespan.

Algorithmica·2022
Same author

Neonatal ascending aorta thrombosis: A rare and lethal entity.

Annals of pediatric cardiology·2022
Same author

Equivalence classes and conditional hardness in massively parallel computations.

Distributed computing·2022
Same author

Mitral valve repair in children with rheumatic heart disease.

Indian journal of thoracic and cardiovascular surgery·2021
Same journal

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity.

Algorithmica·2026
Same journal

A General Upper Bound for the Runtime of a Coevolutionary Algorithm on Impartial Combinatorial Games.

Algorithmica·2026
Same journal

Fully Characterizing Lossy Catalytic Computation.

Algorithmica·2026
Same journal

Parameterized Complexities of Dominating and Independent Set Reconfiguration.

Algorithmica·2026
Same journal

The SLO Hierarchy of Pseudo-Boolean Functions and Runtime of Evolutionary Algorithms.

Algorithmica·2026
Same journal

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem.

Algorithmica·2025
See all related articles

Related Experiment Video

Updated: Jan 19, 2026

Linear Approximation in Time Domain
01:21

Linear Approximation in Time Domain

347

New Tools and Connections for Exponential-Time Approximation.

Nikhil Bansal1, Parinya Chalermsook2, Bundit Laekhanukit3

  • 11Eindhoven University of Technology, Eindhoven, The Netherlands.

Algorithmica
|September 10, 2019
PubMed
Summary
This summary is machine-generated.

This study introduces faster exponential time approximation algorithms for maximum independent set and chromatic number, improving upon existing bounds. These advancements utilize sparsification and randomized branching, impacting the Exponential Time Hypothesis (ETH) and PCP research.

Keywords:
Approximation algorithmsExponential time algorithmsPCP’s

More Related Videos

Approximate Number Sense Test
04:17

Approximate Number Sense Test

Published on: April 30, 2023

8.0K
Exponential Growth
01:29

Exponential Growth

Published on: January 12, 2026

24

Related Experiment Videos

Last Updated: Jan 19, 2026

Linear Approximation in Time Domain
01:21

Linear Approximation in Time Domain

347
Approximate Number Sense Test
04:17

Approximate Number Sense Test

Published on: April 30, 2023

8.0K
Exponential Growth
01:29

Exponential Growth

Published on: January 12, 2026

24

Area of Science:

  • Theoretical Computer Science
  • Algorithm Design and Analysis
  • Computational Complexity

Background:

  • Exponential time approximation algorithms aim to find solutions for NP-hard problems within the fastest possible running times.
  • Existing approximation algorithms for problems like maximum independent set and chromatic number had known time bounds and lower bounds under the Exponential Time Hypothesis (ETH).
  • Previous best-known time bounds for these problems were and respectively.

Purpose of the Study:

  • To develop novel tools and establish new connections for exponential time approximation.
  • To design approximation algorithms with significantly faster running times for several NP-hard problems.
  • To investigate the tightness of existing bounds and their implications for computational complexity.

Main Methods:

  • Development of new randomized algorithms for exponential time approximation.
  • Introduction of a sparsification procedure to reduce problems to bounded-degree variants.
  • Implementation of a new randomized branching rule for specific problem instances.

Main Results:

  • Achieved randomized approximation algorithms with improved time bounds: for maximum independent set, for chromatic number, for minimum vertex cover, and for minimum k-hypergraph vertex cover.
  • Demonstrated that the previously assumed bounds are not tight for all considered problems.
  • Established a connection between PCP parameters and exponential-time approximation algorithms, refuting possibilities for reducing Chan's PCP size.

Conclusions:

  • The developed algorithms provide significant improvements in running times for key combinatorial problems.
  • The findings challenge the tightness of existing time bounds and have implications for the Exponential Time Hypothesis (ETH).
  • The connection to PCP parameters suggests future research directions and refutes certain complexity assumptions.