New Tools and Connections for Exponential-Time Approximation

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.