Advances in Graph Algorithms and Optimization

The field of graph algorithms and optimization is rapidly advancing, with a focus on developing more efficient and effective solutions to complex problems. Recent research has led to the discovery of new algorithms and techniques for solving classic problems, such as the shortest path problem and the traveling salesman problem. Additionally, there has been significant progress in the development of approximation algorithms for NP-hard problems, including the Steiner Forest problem. Furthermore, researchers have made breakthroughs in the study of online algorithms, distributed algorithms, and reconfiguration problems. Notably, the long-standing barrier of 2-approximation for the Steiner Forest problem has been broken, and new results on the hardness of online algorithms for finding large independent sets have been established. Noteworthy papers include: Faster shortest-path algorithms using the acyclic-connected tree, which presents a novel algorithm for the single-source shortest path problem with improved time complexity. Breaking a Long-Standing Barrier: 2-ε Approximation for Steiner Forest, which achieves a 2 - 10^(-11) approximation for the Steiner Forest problem, surpassing the previous barrier of 2. Optimal Hardness of Online Algorithms for Large Independent Sets, which establishes the hardness of online algorithms for finding large independent sets in random graphs.

Sources

Faster shortest-path algorithms using the acyclic-connected tree

Balanced TSP partitioning

Token Sliding Reconfiguration on DAGs

Covering Approximate Shortest Paths with DAGs

Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest

Optimal Hardness of Online Algorithms for Large Independent Sets

Towards Optimal Distributed Edge Coloring with Small Palettes

A Bad Example for Jain's Iterative Rounding Theorem for the Cover Small Cuts Problem

Built with on top of