85 papers
This paper presents the first approximation algorithms for two generalizations of the Maximum Quadratic Assignment Problem—Maximum List-Restricted Quadratic Assignment and Maximum Quadratic -Matching Assignment—achieving and approximation factors respectively, which asymptotically match the best known bounds for the standard MaxQAP under specific conditions.
This paper proposes a novel algebraic framework for the Reconfiguration CSP that utilizes partial operations to extend complexity dichotomy results from Boolean domains to more general settings, offering a versatile approach to identifying tractable instances.
This paper presents a novel hybrid dynamic programming algorithm that improves upon the previous state-of-the-art for solving the single-item lot sizing problem with a one-breakpoint all-units discount and non-increasing prices by leveraging new optimal solution properties to maintain a compact solution space.
This paper proposes a novel, instance-specific Differentially Private framework based on the Propose-Test-Release mechanism that enables scalable and accurate estimation of network principal components on large real-world graphs, achieving a 180-fold runtime improvement over existing baselines while also providing the first DP solution for the Densest--subgraph problem.
This paper proves that the Maximum Partial List H-Coloring problem is solvable in polynomial time on P_5-free graphs for any fixed graph H, thereby resolving an open question from SODA 2024 and improving upon a previous algorithm by Chudnovsky et al.
This paper presents the design, analysis, and performance evaluation of a concurrent deterministic skiplist alongside lock-free queue and hash table implementations on many-core NUMA systems, introducing memory management strategies and hierarchical usage patterns to reduce page faults, cache misses, and remote memory access latencies.
This paper investigates the parameterized complexity of the NP-complete Shortest Path problem with positive disjunctive constraints, establishing fixed-parameter tractability and providing polynomial kernelizations of size and based on the solution size and specific structural properties of the forcing graph.
This paper resolves two major open problems by proving that computing shortest monotone paths on simple polytopes and determining their diameters are NP-hard, while also demonstrating that polynomial-time linear paths can be found on specific small extended formulations of any polytope.
This paper resolves the open question regarding the parameterized complexity of the Optimal Morse Matching problem by presenting a $2^{O(k \log k)} n$-time algorithm for bounded-treewidth complexes and proving its optimality under the Exponential Time Hypothesis.
This paper demonstrates that the robust permutation flowshop problem under budgeted uncertainty can be solved by reducing it to polynomially many nominal instances, thereby establishing polynomial-time solvability for two machines and polynomial-time approximability for any fixed number of machines.
This paper introduces a novel matrix-based framework for deriving upper and lower bounds for the Permutation Flowshop Scheduling Problem, demonstrating significant improvements on standard benchmarks and providing new theoretical insights into makespan value estimates and asymptotic approximation ratios.
This paper introduces a graph-matching decoding framework for general two-dimensional topological translationally-invariant codes that coarse-grains syndromes into effective toric code excitations, proving it corrects errors up to a constant fraction of the code distance and achieves non-zero thresholds while demonstrating performance comparable to state-of-the-art decoders for bivariate bicycle codes.
This paper presents and validates quantum algorithms based on Grover's search that solve the NP-complete Network Signal Coordination (NSC) problem and its robust variants, achieving quadratic speedups and maintaining efficiency even when the solution space fraction decays polynomially with network size.
This paper presents efficient classical algorithms for the and Constrained Integer Solution problems previously solved by an efficient quantum algorithm, thereby demonstrating that no exponential quantum speedup exists for these tasks.
This paper introduces a length-capping splitting strategy for move structures that achieves optimal average query time, reduces space complexity by bits, and enables faster, -space construction of RLBWT permutations for efficient BWT inversion and suffix array enumeration.
This paper demonstrates that the previously established additive error lower bound for differentially private continual release of distinct elements and moments in turnstile streams can be circumvented by allowing algorithms to output estimates with both polylogarithmic multiplicative and additive errors while using only polylogarithmic space.
This paper presents the first multiplicative improvement over the greedy algorithm's approximation ratio for maximizing non-negative monotone submodular functions subject to -matroid intersection constraints, achieving a ratio of approximately $0.819kk$.
This paper presents two generalized algorithms for efficiently computing modular inverses modulo and for any integer , extending previous prime-power methods to leverage computer architecture and improve computational performance.
This paper introduces a relaxed definition of highway dimension that incorporates natural metric spaces like grids and the Euclidean plane, enabling the construction of a PTAS for TSP and a comprehensive toolkit of metric decompositions for such spaces.
This paper introduces a novel, symmetric objective improvement approach for solving discounted payoff games by constructing a constraint system that minimizes the sum of errors from non-sharp inequalities, thereby challenging the conventional dichotomy between strategy improvement and value iteration methods.