84 papers
This paper demonstrates that a simple exact method can solve nearly all classical benchmark instances of the Traveling Salesman Problem with Time Windows in under ten seconds, revealing that these datasets are no longer representative for evaluating algorithmic performance or training machine learning models due to their exploitable structure.
This paper improves the running time of -approximation algorithms for -median and -means clustering in low-dimensional Euclidean spaces to $2^{\tilde{O}(1/\varepsilon)^{d-1}} \cdot n \cdot \text{polylog}(n)1/\varepsilond$ is essentially optimal.
This paper introduces a generic sketching scheme for estimating -moments in the turnstile streaming model by hashing indices to Lévy processes, leveraging the Lévy-Khintchine representation theorem to unify existing methods and characterize the tractability of a broad class of functions, including nearly periodic and heterogeneous cases.
This paper investigates the online weighted non-crossing matching problem in the Euclidean plane, establishing that while deterministic algorithms fail to achieve non-trivial competitive ratios, randomization enables constant competitiveness, and further analyzing variants involving revocability, collinear points, and advice complexity.
This paper introduces a novel subgradient definition based on Busemann functions for convex optimization on Hadamard spaces, enabling the generalization of stochastic and incremental subgradient methods with guaranteed complexity bounds to nonpositively curved metric spaces such as BHV tree space.
This paper presents a new -differentially private algorithm for frequent substring mining that achieves near-optimal error guarantees while drastically reducing space and time complexity from to near-linear bounds through refined candidate generation and search space pruning.
This paper presents a polynomial-time approximation scheme (PTAS) for the Weighted Triangle-Free 2-Matching problem, utilizing a local-search algorithm to achieve a -approximation ratio for any constant , thereby significantly improving upon the previous best-known $2/3$-approximation.
This paper presents a one-pass random-order streaming algorithm that achieves an expected approximation factor of 0.7401 for the Unit Interval Selection problem using space linear in the optimal solution size, thereby improving upon the 2/3 bound established for adversarial streams while also providing matching space lower bounds for higher approximation factors.
The paper introduces bsort, a non-comparison-based sorting algorithm that unifies the sorting of signed/unsigned integers and floating-point numbers with an asymptotic time complexity of and auxiliary space of , demonstrating competitive performance against optimized hybrid libraries for small word sizes.
This paper presents and proves the correctness of an algorithm that automates critical pair analysis for string diagram rewriting in symmetric monoidal categories (without Frobenius structure) by enumerating all critical pairs through concrete hypergraph manipulation.
This paper introduces the Elastic Time Warping algorithm, which solves the time series matching problem in arbitrary metric spaces using a Hellinger kernel stretching penalty with cubic computational complexity.
This paper presents an improved distributed protocol for the distributed experts problem that achieves a specific regret bound while significantly reducing communication costs compared to previous work.
This paper investigates the many-to-many bipartite matching problem with ties and lower quotas, proving that while a maximum-size critical relaxed-stable matching is NP-hard to compute, a -approximation can be achieved in polynomial time.
This paper presents a simplified and fully analyzed sublinear-time algorithm that achieves a -approximation of the average degree in bounded arboricity graphs using queries, thereby recovering logarithmic factors lost in previous work and offering a modified version with query complexity.
This paper introduces permutation match puzzles on grids, characterizing their solvability via an acyclic constraint graph condition, providing a hook length formula for counting solutions, offering an algorithm for minimal repairs in the basic case, and proving that generalizing the problem to arbitrary permutations renders minimal repair NP-complete.
This paper provides the first formal specification and comprehensive analysis of the Li-Chao tree, a widely used data structure in competitive programming, by establishing its algorithmic details, proving correctness, and evaluating its theoretical and empirical performance.
This paper proposes a unified, domain-agnostic framework for computing the bus-factor by modeling projects as bipartite graphs, proving the NP-hardness of both redundancy and criticality formulations, and introducing a novel robustness-based measure with efficient linear-time approximations that outperforms existing methods in capturing project risk and fragmentation.
This paper introduces Structured Gossip DNS, a partition-resilient name resolution system for large-scale dynamic networks that leverages DHT finger tables and passive stabilization to achieve eventual consistency with reduced message complexity and without requiring global coordination.
This paper introduces a new deterministic symmetric recursive algorithm designed to solve mean-payoff games.
This paper introduces the first sketching method capable of approximating arbitrary tensor network contractions, including cyclic ones, and proposes a second method for acyclic networks that achieves polynomial time and space complexity, overcoming the exponential limitations of existing approaches.