Search research articles

ABOUT JoVE

Overview Leadership Blog JoVE Help Center

AUTHORS

Publishing Process Editorial Board Scope & Policies Peer Review FAQ Submit

LIBRARIANS

Testimonials Subscriptions Access Resources Library Advisory Board FAQ

RESEARCH

JoVE Journal Methods Collections JoVE Encyclopedia of Experiments Archive

EDUCATION

JoVE Core JoVE Business JoVE Science Education JoVE Lab Manual Faculty Resource Center Faculty Site

Terms & Conditions of Use

Related Concept Videos

Linear Approximation in Time Domain

Linear Approximation in Time Domain

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,...

Approximate Number Sense Test

Approximate Number Sense Test

Source: Laboratory of Jonathan Flombaum—Johns Hopkins University

Exponential Growth

Exponential Growth

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...

Linearization and Approximation

Linearization and Approximation

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...

Exponential and Sinusoidal Signals

Exponential and Sinusoidal Signals

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,

Application of Linearization and Approximation

Application of Linearization and Approximation

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...

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

Search research articles

Related Experiment Video

Updated: Jan 19, 2026

Linear Approximation in Time Domain

Linear Approximation in Time Domain

New Tools and Connections for Exponential-Time Approximation.

Nikhil Bansal¹, Parinya Chalermsook², Bundit Laekhanukit³

¹1Eindhoven University of Technology, Eindhoven, The Netherlands.

|September 10, 2019

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 algorithms Exponential time algorithms PCP’s

More Related Videos

Approximate Number Sense Test

Approximate Number Sense Test

Published on: April 30, 2023

Exponential Growth

Exponential Growth

Published on: January 12, 2026

Related Experiment Videos

Last Updated: Jan 19, 2026

Linear Approximation in Time Domain

Linear Approximation in Time Domain

Approximate Number Sense Test

Approximate Number Sense Test

Published on: April 30, 2023

Exponential Growth

Exponential Growth

Published on: January 12, 2026

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.