Data Structures and Algorithms Papers@AlgorithmPapers
Nov 12
Online Graph Coloring: Competitive Ratios Separating Randomized and Deterministic Algorithms

Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
arxiv.org/abs/2611.14513 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙳𝙼 πš–πšŠπšπš‘.𝙲𝙾]
We study online coloring, focusing on the competitive ratio. The best previously known results were (1) a lower bound of Ξ©(n / logΒ² n) for both deterministic and randomized algorithms by Halld\'orsson and Szegedy (1994), (2) an upper bound of O(n / log n) for randomized algorithms by Halld\'orsson (1997), and (3) an upper bound of O(n / log log n) for deterministic algorithms by Kawarabayashi, Yoneda, and Yoneda (2025). In this paper, we improve these results as follows: 1. A new lower bound of Ξ©(n / log n) for deterministic algorithms. 2. A new upper bound of O(n (log log n)Β² / logΒ² n) for randomized algorithms. 3. A new upper bound of O(n / (log log n)Β²-Ξ΅) for deterministic algorithms for every fixed Ξ΅>0. For randomized algorithms, we nearly close the gap between the lower and upper bounds; the remaining gap is only O((log log n)Β²). We establish the asymptotic separation between randomized and deterministic online graph coloring. Against an oblivious adversary, a polynomial-time rand
0
0
10
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 12
Directed Singular-Value Sparsifiers with O(n log n/∊²) Arcs

Emile Anand
arxiv.org/abs/2611.14342 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙳𝙼]
Given an unweighted directed graph, a sparsifier is a nonnegative reweighting of original arcs that preserves every in-degree and out-degree exactly. In this work, we study singular-value sparsifiers, which are generalizations of spectral sparsifiers. Singular-value sparsifiers find a number of applications in theoretical computer science, such as maintaining directed cuts and flows, speeding up directed Laplacian solvers, and sparsifying dense weight matrices in neural networks. Strong singular-value (SV) approximation supports sparse representations of directed random walks with guarantees that remain stable under products, and controls bilinear error in the left and right Schur-complement metrics. We prove that every unweighted directed graph on n vertices admits an Ρ-SV sparsifier with O(nlog(2n)/Ρ²) arcs, improving the O(nlog⁡ n/Ρ²) support bound of Lau, Wang, and Zhou. The sparsifier is a nonnegative reweighting of original arcs and preserves every in-degree and out-degree exactl
1
0
5
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 12
Nonadaptive One-Sided Testing of Binary Rank

Nader H. Bshouty
arxiv.org/abs/2611.14163 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙻𝙢]
The binary rank of a binary matrix is the minimum number of disjoint all-one rectangles that partition its one-entries. We study entry-query testing of binary rank at most d, with one-sided error and nonadaptive queries. We give a tester using Γ•(d⁴/∊²) queries, independent of the matrix dimensions and a general lower bound of Ξ©Μƒ(dΒ³/Β²/∊).
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Bounded Weighted Edit Distance with Metric Costs

Jihan Wang
arxiv.org/abs/2611.13984 [𝚌𝚜.π™³πš‚]
We give a deterministic O(n+k²)-time algorithm for bounded weighted edit distance when the input costs form an integer metric on the alphabet extended by a gap symbol. Here n is the total input length and k is the given threshold on the distance. If the distance is at most k, the algorithm returns it with an optimal alignment. Otherwise, it reports that the distance exceeds k. The running time matches the classical unit-cost bound and is independent of the alphabet size and of the largest cost. The algorithm keeps only the farthest-reaching prefix alignment for each cost and each difference between the total gap costs of the aligned prefixes. For real metrics whose nonzero costs are at least one, scaling and upward rounding give a (1+Ρ)-approximation for the bounded problem in Õ(n+(k/Ρ)²) time. If insertions and deletions have integer costs, the running time improves to Õ(n+k²/Ρ).
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
What to Predict for Efficient Scheduling on Parallel Machines

Evripidis Bampis, Bruno Escoffier, Dimitris Fotakis, Giorgos Mitropoulos, Michalis Xefteris
arxiv.org/abs/2611.13980 [𝚌𝚜.π™³πš‚]
We study learning-augmented algorithms for scheduling on multiple parallel machines under the objectives of minimizing the makespan or the total weighted completion time. We assume that the algorithm has access to noisy information (the prediction) about an optimal solution, expressed through a solution encoding that implicitly quantifies both the amount of information provided and the nature of noise (errors in the prediction). Our central question is to determine the maximum level of noise that still allows for efficiently recovering this optimal solution. We observe that information guiding greedy scheduling to optimality or revealing the optimal assignment of tasks to machines is very sensitive to noise, and prove that recovering an optimal solution from solution encodings capturing either is computationally hard, even for a small (non-constant) number of errors. On the positive side, we show that an order-based encoding, which leads to errors that are dispersed locally, is robust
0
0
2
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Real-Time String Indexing in Optimal Time

Gregory Kucherov, Yakov Nekrich
arxiv.org/abs/2611.13950 [𝚌𝚜.π™³πš‚]
In this paper we describe the first fully real-time indexing solution for pattern matching over an arbitrary integer alphabet. Our data structure spends O(1) worst-case time w.h.p. for processing each new letter appended to T and worst-case O(|P|+occ) time for reporting all occurrences of P, where T and P are strings over an integer alphabet. The main idea of our solution is a novel representation of the suffix tree, the path-decomposed suffix tree, which does not store the full topology of the suffix tree but instead decomposes it into paths, each stored in a dictionary that encodes parent–child relationships indirectly.
0
0
2
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Online Network Design with Maximum Delay and Stochastic Arrivals

Tianhang Lu
arxiv.org/abs/2611.13865 [𝚌𝚜.π™³πš‚]
We study online network services that combine pending requests into batches. Each batch pays for its spatial service and for the waiting time of its oldest request. The objective is the sum of these costs over all batches. Thus requests can share both a spatial purchase and one maximum-delay charge. We assume independent Poisson arrivals of known rates, while actual requests are revealed only upon arrival. For stateless services, suppose that each type has an attainable minimum cost when served alone, that every batch costs at least the stand-alone minimum of each type it contains, and that one finite-cost action can serve any batch, regardless of its request multiplicities. We give a deterministic algorithm with long-run ratio of expectations e/(e-1) against an unrestricted offline optimum. This factor is optimal, even allowing randomization, already at one request location. The key comparison measures the union of time intervals associated with requests. The theorem applies directly
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Online Network Design with Additive Delays and Poisson Arrivals

Tianhang Lu, Runtian Ren, Shengcai Liu
arxiv.org/abs/2611.13859 [𝚌𝚜.π™³πš‚]
We study online service systems in which requests arrive at locations in a network. A service may open a facility and connect customers, buy a subtree linking them to a root, or send a mobile server to visit them. Combining requests can save opening, network, or travel costs, but each request pays its own waiting time. The objective is the sum of these spatial costs and individual delays. We assume independent Poisson arrivals of known rates. The algorithms know how often requests occur, but observe them only upon arrival. We show that these rates suffice to make fixed spatial choices that compete with an offline optimum free to adapt to the realized input. We obtain long-run ratios of expectations below 27.249 for facility location in finite metrics, 94.415 for multi-root aggregation on trees, and 24.326 for online service on trees. All three algorithms are deterministic; the multi-root algorithm also has polynomial-time preprocessing on rational inputs. The proofs connect rate-based
0
0
4
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Stochastic Aggregation with Prescribed Resources and Additive Delay

Tianhang Lu, Runtian Ren, Shengcai Liu
arxiv.org/abs/2611.13757 [𝚌𝚜.π™³πš‚]
We study online aggregation with prescribed resources and additive delay. In this problem, we are given a finite set of resources with purchase costs and a collection of request types, each specifying the resources it requires. Requests arrive over time, and each request can be served immediately or postponed to a later time. A service may serve several pending requests together by purchasing every resource required by at least one of them, paying for each purchased resource only once. These purchases serve only the current batch; resources needed in a later service must be purchased again. A request served t units of time after its arrival incurs delay cost t. The objective is to serve all requests while minimizing the sum of resource purchase costs and individual delay costs. We consider a stochastic version of this problem in which requests of each type follow an independent Poisson process of known rate. An online algorithm knows these rates but observes requests only upon arrival.
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
List Update with Per-Page Maximum Delay

Tianhang Lu, Runtian Ren, Shengcai Liu
arxiv.org/abs/2611.13750 [𝚌𝚜.π™³πš‚]
We study list update with per-page maximum delay. Requests may wait, and one access clears all pending requests of a page at its current list rank, paying their maximum waiting penalty. Each service can change the permutation and therefore the cost of later accesses. We give a strictly 5-competitive deterministic algorithm: serve a page when the oldest waiting time reaches two thirds of its current rank, then move it to the front. Our main tool is an asynchronous marked-rank coupling that compares different list orders and different service histories. A temporal transfer principle separates this permutation argument from two waiting-cost inequalities. It gives factor 5 for page-specific superadditive penalties, common calendar rates, and additional hard deadlines; deadlines alone admit factor 3. Two structural conditions on request-specific penalties give factor 3+2ΞΊ. In particular, nonincreasing request severity retains factor 5 even with unbounded weight ratios. For linear delay, off
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Min-CSPs on Complete Instances III: Nearly Optimal Characterizations of Approximation for Symmetric CSPs

Yihwan Chae, Chenglin Fan, Donghyeon Lee, Euiwoong Lee
arxiv.org/abs/2611.13635 [𝚌𝚜.π™³πš‚]
This paper studies complete Min-k-CSPs: an instance on n variables has one nontrivial constraint for every k-set of variables (so binomnk constraints in total), and the goal is to find an assignment that minimizes the number of unsatisfied constraints. They are motivated by the connections to machine learning and data science, as well as the possibility of being testbeds for new algorithmic techniques. Previous recent results presented polynomial-time algorithms for the decision version of every complete Boolean k-CSP, which is a necessary condition for any multiplicative approximations for the minimization version, but nontrivial approximation results have been limited to fragile CSPs, 2-SAT, and NAE-3-SAT, leaving the approximability of most complete Boolean Min-CSPs open, including complete Min-k-SAT. In this paper, we resolve this question, up to nearly matching factors, for the natural class of symmetric Boolean predicates. Given A βŠ† {0, …, k}, Min-CSP(A) is a Min-k-CSP where each
1
0
2
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Approximating graphic TSP by b-matchings

Swati Gupta, Mehrdad Sohrabi, Levent Tunçel
arxiv.org/abs/2611.13585 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙳𝙼 πš–πšŠπšπš‘.𝙲𝙾 πš–πšŠπšπš‘.𝙾𝙲]
We give a polynomial-time algorithm for graphic TSP that returns a tour of length at most ⁸⁹⁄₆₄=⁷⁄₅-³⁄₃₂₀ times the value of the subtour relaxation. This improves the long-standing ratio ⁷⁄₅ of SebΕ‘ and Vygen and shows that the integrality gap of the subtour LP on graphic instances is at most βΈβΉβ„β‚†β‚„β‰ˆ 1.3906. We optimize a non-linear objective function over an odd-join polytope, which uses (i) a new removable system of edges, and (ii) reconnection of subtours if the graph is disconnected. This approach gives a ¹³⁄₁₀-approximation algorithm for 4-regular 4-vertex-connected graphs, improving the ⁴⁄₃ of Newman, and a ⁴⁄₃-approximation for k-vertex-connected graphs of maximum degree at most k+1, for every kβ‰₯ 3. For the general graphic TSP, we construct a feasible point in the odd-join polytope, using an optimal vertex from the Subtour linear programming relaxation of TSP, which helps us bound the approximation factor by 89/64.
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Greedy+Singleton for knapsack-constrained monotone submodular maximization has approximation ratio exactly β⋆ β‰ˆ 0.42944

Kundan Baliga, Aiden Xie, Aditya Byju
arxiv.org/abs/2611.13575 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙳𝙼]
Greedy+Singleton is the textbook heuristic for monotone submodular maximization under a knapsack constraint: it returns the better of the cost-benefit greedy set and the best single item. Its worst-case approximation ratio, known only to lie in [0.427, 0.42945] (Feldman-Nutov-Shoham; Kulik-Schwartz-Shachnai), is exactly an explicit constant Ξ²β‹†β‰ˆ 0.42944. In the extremal instances, many cheap "filler" items wear down the value of two large optimal items while greedy spends the budget, until neither fits. This picture gives a sharper factor-revealing relaxation; we bound it analytically near the extremal parameters, up to finitely many interval-arithmetic checks, and certify it elsewhere by an exact branch-and-bound. The matching bad instances are tie-free and checkable by hand. For the version that stops at the first item that does not fit, Wolsey's bound 1-e⁻ᡝ_α΅‚β‰ˆ 0.35780, where eᡝ_α΅‚=2-Ξ²_W, is tight; Wolsey stated this for his variant without giving the instances, and we give an explicit
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Improved Bounds for Online Matching with Random Edge Arrivals

Yilong Feng, Haolong Li, Zonghan Yang
arxiv.org/abs/2611.13571 [𝚌𝚜.π™³πš‚]
We study the unweighted online matching problem with random edge arrivals, where each edge arrives at an independent time drawn uniformly from [0,1], and the algorithm must immediately and irrevocably accept or reject it while maintaining a matching. Guruganesh and Singla (IPCO, 2017) first broke the 1/2 barrier of the naive Greedy algorithm by giving a (1/2+Ξ΅)-competitive algorithm for a small constant Ξ΅>0, a guarantee that has remained the best known for nearly a decade. We give a simple three-phase algorithm that achieves a competitive ratio of 0.5445 by deliberately rejecting selected early edges to reserve their endpoints for later matching opportunities. With a different choice of parameters, the same algorithm is 0.5535-competitive on triangle-free graphs, including bipartite graphs. We also establish competitive ratio upper bounds below 0.6964 for general graphs and 0.7043 for bipartite graphs via exact rational evaluation of an optimal-policy recurrence on fixed graphs, even w
1
0
2
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Pair-Merge Tokenisation Is Hard to Approximate on Binary Strings and Strongly NP-Hard on Unary Datasets

Kundan Baliga, Aiden Xie, Aditya Byju
arxiv.org/abs/2611.13568 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙲𝙲 𝚌𝚜.𝙲𝙻]
Tokenisers such as Byte-Pair Encoding (BPE) shorten text by repeatedly merging an adjacent pair of symbols into a new one; fewer tokens mean less computation. We ask whether an efficient algorithm can choose k merges that leave a string of length n almost as short as possible; doing nothing is already within a factor n. We prove that, unless P = NP, no polynomial-time algorithm comes within a factor c n/log n, for some constant c>0, already for one binary string and for BPE-style merges that replace every occurrence. The key idea is that k merges form a grammar with k rules: a vertex-cover gap becomes a grammar-size gap, which we amplify with relabelled copies, encode in binary and realise with explicit merges. For merges that may skip occurrences, a simple algorithm achieves O(n/loglog n), and no Karp reduction can prove hardness beyond order n/log n unless coNP βŠ† NP/poly. Over a one-letter alphabet, both tokenisation problems left open by Kastreva et al. are strongly NP-complete on d
0
0
1
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Minimum Membership Dominating Set and Its Generalization: Leafage vs. Asteroidal Number

Yuma Tamura, Daichi Wakayama, Akira Suzuki, Xiao Zhou
arxiv.org/abs/2611.13392 [𝚌𝚜.π™³πš‚]
The Dominating Set problem is known to be fixed-parameter tractable when parameterized by leafage, a structural graph parameter defined on chordal graphs. We investigate whether this tractability extends to its variants with natural constraints. Specifically, we study the Minimum Membership Dominating Set problem and its generalization, the Min. (Οƒ, ρ)-Dominating Set problem. Given a graph G and a positive integer β„“, Minimum Membership Dominating Set asks whether there is a dominating set D such that every vertex in G is dominated by at most β„“ vertices in D. We first show a negative result: Minimum Membership Dominating Set parameterized by leafage plus β„“ is W[1]-hard, demonstrating that even this natural constraint serves as a severe barrier to designing FPT algorithms. To complement this, we present an XP algorithm for the Min. (Οƒ, ρ)-Dominating Set problem parameterized by asteroidal number plus ΞΌ, where Οƒ and ρ are finite sets of non-negative integers and ΞΌ is the maximum value in
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Function Inversion Reporting

Itai Dinur, Alexander Golovnev, Chao Yan, Yiding Zhu
arxiv.org/abs/2611.13294 [𝚌𝚜.π™³πš‚]
In the Function Inversion problem, the goal is to invert a function f:[N] β†’ [N] in two phases. In the preprocessing phase, the offline algorithm computes an advice string of length S bits. In the online phase, the online algorithm receives the advice and a challenge y ∈ [N], and the goal is to find a preimage x ∈ [N] such that f(x) = y in time T. The problem was initially studied in cryptography, but in recent years it has found various applications to data structure problems. Yet, several of the applications require a variant of Function Inversion, known as Function Inversion Reporting, where the goal is to output all preimages of the challenge y. In this paper, we study the Function Inversion Reporting problem in a systematic way by unifying and improving existing algorithms. As a result, we obtain improved data structures for several problems including 3SUM-Indexing Reporting, Range Reporting, Approximate Nearest Neighbor, Jumbled Indexing Reporting, and Gapped String Indexing Repor
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
An Improved (1+2e)-Approximation Algorithm for Metric Data Placement

S. Rasoul Etesami
arxiv.org/abs/2611.13224 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙳𝙼 𝚌𝚜.π™Άπšƒ 𝚌𝚜.𝙽𝙸 πš–πšŠπšπš‘.𝙾𝙲]
We study the metric data placement problem with site-capacity constraints and fixed installation costs, aiming to minimize the total cost of placing data (resources) and accessing their nearest copies. We develop a deterministic polynomial-time approximation algorithm based on a natural linear programming relaxation of the problem. Starting from an optimal fractional solution, we construct multiscale metric-ball partitions independently for each resource and connect overlapping balls at consecutive levels to form a flow network. The resource layers are then coupled through shared site-capacity arcs, allowing us to obtain an integral placement by minimizing a surrogate cost over a single min-cost circulation. By optimizing the choice of ball radii, we establish an approximation factor of 1+2eβ‰ˆ 6.44. To our knowledge, this is the best approximation guarantee for the metric data placement problem since its introduction by Baev and Rajaraman in 2001.
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
A Fast Algorithm for Subspace Convolution

Shlomo A. Perles, Omri Weinstein
arxiv.org/abs/2611.13134 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙲𝙲]
A cornerstone result in Boolean lattice theory is the subset-zeta transform, which computes the f-weighted subset summation problem (Z f)(B)=\sum_AβŠ†Bf(A) for all BβŠ†[n] in O(N log N) additions instead of the na\"ive O(3^n) = O(N^logβ‚‚3), where N=2^n. This paper studies the algebraic analogue of this problem–the subspace summation problem–where subsets are replaced by linear subspaces in Fq^n. Surprisingly, we show that this problem admits a similar Θq(Nq log Nq)-time algorithm, where Nq is the number of subspaces. This improves substantially (in both theory and practice) over lattice-based algorithms ([BHK+16, KKW16]), which are known to be optimal for addition-only algorithms over mathbbR. We prove similar runtimes for inversion, rank-constrained sums and span convolution. We describe two main applications: Fast linear algebra on Grassmann graphs: Matrix–vector multiplication for arbitrary distance-invariant kernels on N-vertex Grassmann graphs in Oq(Nlog N) arithmetic operations, toget
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Combinatorial optimization with bounded subdeterminants

Samuel Fiorini, J. Pascal Gollin, Tony Huynh, Simon Keil, O-joung Kwon, Sang-il Oum, Roohani Sharma, Stefan Weltge
arxiv.org/abs/2611.13065 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙳𝙼 πš–πšŠπšπš‘.𝙲𝙾 πš–πšŠπšπš‘.𝙾𝙲]
We take a first step toward a broader study of classical combinatorial optimization problems through the maximum subdeterminants of their standard integer programming formulations, yielding new positive results for several famous (NP-hard) problems. An integer matrix is totally Ξ”-modular if every square submatrix has determinant of absolute value at most Ξ”. For every fixed Ξ”, it has been known that maximum clique, maximum stable set, and minimum vertex cover can be solved in polynomial time on instances for which the coefficient matrix of the natural formulation is totally Ξ”-modular. We extend this list by showing that the same holds for many other problems, including the weighted versions of maximum cut, the traveling salesman problem, feedback vertex set, odd cycle transversal, dominating set, max 2-sat, induced matching, and cluster vertex deletion, as well as for k-colorability and graph isomorphism. Our proofs reveal several new ways in which bounded subdeterminants impose combina
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Optimal Injectivity of the SparseStack

Lorenzo Beretta, Simone Bombari, Margalit Glasgow, Raphael Arkady Meyer, Kijun Shin, David P. Woodruff
arxiv.org/abs/2611.12867 [𝚌𝚜.π™³πš‚]
An Oblivious Subspace Injection (OSI) is a random sketching matrix that reliably preserves the minimum singular value of any fixed subspace with high constant probability, requiring only a one-sided spectral lower bound without controlling upper singular values. While classical Oblivious Subspace Embeddings (OSEs) fundamentally require row sparsity Ω(log r) at linear sketch dimension k = O(r), we show that one-sided injectivity permits strictly sparser sketches, establishing matching (up to loglog r factors) upper and lower bounds of tildeΘ(√(log r)). First, we prove that the SparseStack sketch achieves constant injectivity at linear dimension k = Θ(r) with row sparsity only ΢ = O(√(log r)), well below the Θ(log r) barrier where standard operator-norm concentration fails. Second, we establish a matching lower bound: any isotropic random sketching matrix satisfying a mild row-overlap condition requires row sparsity ΢ = Ω(√(log r / log log r)) to achieve linear-dimension injectivity, con
1
0
4
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Flows in High Degree Places: Sublinear Spanning Tree Congestion

D Ellis Hershkowitz, Richard Z Huang
arxiv.org/abs/2611.12827 [𝚌𝚜.π™³πš‚]
The congestion of a spanning tree T of graph G is the maximum congestion of an edge of T if each edge of G is routed on T. Prior work showed that obtaining a minimum congestion spanning tree is NP-hard to approximate within 6/5, yet the only known approximation algorithm is a trivial n/2-approximation from returning any spanning tree of the graph. We give a simple poly-time Γ•(n⁢/⁷)-approximation for minimum congestion spanning tree on n-vertex graphs. We obtain this result via a Γ•(mΒ²/Β³)-approximation, where m is the number of edges. Our algorithm is based on a new flow-or-degree decomposition which deletes a small number of edges so that each remaining component either has low degree or admits a low congestion flow. We also show that, assuming the Small Set Expansion Hypothesis, it is NP-hard to O(1)-approximate this problem, even on graphs of constant maximum degree.
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Polynomial-Space Quantum Algorithms from Classical Branching: Colouring, Domination and Monotone Local Search

Sebastian Senge
arxiv.org/abs/2611.12714 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙲𝙲 πššπšžπšŠπš—πš-πš™πš‘]
We give quantum algorithms for exponential-time problems on n vertices or elements, with bounded error, polynomial space and no quantum random access memory. Our results are these. (1) 4-Colouring in quantum time O(1.3032ⁿ), from a polynomial-space branching algorithm with polynomial-space terminal algorithms; with the branching algorithm alone, O(1.3100ⁿ). The previous best bound in this model, to our knowledge, is O(1.3231ⁿ). (2) k-Colouring below the previous best bound for k ∈ {5, 7, 8, 9, 10, 11} and 13 ≀ k ≀ 18, from O(1.4518ⁿ) for k = 5 to O(1.9233ⁿ) for k = 18. (3) Dominating Set in O(1.2235ⁿ), against the previous O(2ⁿ/Β²), Independent Dominating Set in O(1.1583ⁿ), and Edge Dominating Set and Minimum Maximal Matching in O(1.1501ⁿ). (4) A quantum form of monotone local search: if the extension problem has a backtracking tree with cᡏ nodes up to polynomial factors, the problem is solved in quantum time (2 - 1/c)ⁿ/Β² up to polynomial factors. This gives Feedback Vertex Set in O(1.3
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Better Bounds For Graph Reconstruction

Antoni Buraczewski, PaweΕ‚ Gawrychowski
arxiv.org/abs/2611.12619 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙳𝙼]
The goal in graph reconstruction problems is to learn an initially unknown graph using only a few queries of a specific type. Possibly the most natural query type is retrieving the distance between any two vertices of a connected, undirected, and unweighted graph. For a bounded-degree graph on n vertices, Kannan, Mathieu, and Zhou [TALG 2018] showed a randomized algorithm that uses only Γ•(nΒ³/Β²) such queries. On the lower bound side, it is only known that any randomized algorithm needs Ξ©(nlog n) queries. We make a significant step forward to bridging these bounds by designing a randomized algorithm that uses n⁴/³⁺ᡒ⁽¹) queries. This requires extending the original approach based on Voronoi diagrams into a recursive procedure that partitions a cell into smaller cells. While such a recursive approach has been used in the related graph verification problem, in the more general graph reconstruction problem we need to operate without knowing the graph, which requires a new (and more technical
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Optimizing the Steady-State Travel Time of Nash Flows over Time with Capacity Increases

Niklas Dahlmeier, Paul Paschmanns, Laura Ritter, Ruben Skorupinski
arxiv.org/abs/2611.12486 [𝚌𝚜.π™³πš‚]
We study budgeted capacity augmentation for single-source single-sink NFOTs under constant inflow uβ‚€. The goal is to increase capacities on arcs subject to a global budget constraint in order to minimize the steady-state travel time in the network. We show that this problem is weakly NP-hard on series-parallel networks and provide an exact pseudopolynomial algorithm as well as a fully polynomial algorithm that attains the optimum travel time for budget B while spending at most B + Ξ΅β‹…max{B,uβ‚€}. On general networks the problem becomes strongly NP-hard. Moreover, unless P = NP, for every fixed Ξ΅ ∈ (0,1), no polynomial-time algorithm can achieve the optimal steady-state travel time while exceeding the budget by at most a factor of nΒΉ-Ξ΅. Lastly, we give structural properties about steady-state travel time under varying arc capacities. We identify capacity thresholds determined by subsets of s-t-cuts and show that the travel time is constant in the interior of the cells resulting from the co
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
How Hard Is Tokenisation? Algorithms and Complexity Beyond NP-Hardness

Andrei Robert Ion, Rares Mateiu, Adrian Miclaus, Alexandru Popa
arxiv.org/abs/2611.12348 [𝚌𝚜.π™³πš‚]
Given a collection of strings and a vocabulary budget, how well can we minimize its total token count, and how does the answer change with the tokenisation model? For binary direct tokenisation, previous work proved APX-hardness but left constant-factor approximability unresolved. We rule out every polynomial-time MΒΉ-Ξ΅ approximation, for fixed Ξ΅>0, unless P=NP, even on distinct equal-length strings with K=m-1. Here M is the total input length and m is the number of input strings. We complement this lower bound with a deterministic polynomial-time O(M/log M) approximation algorithm and stronger bounds for selected vocabulary budgets. For the different objective of maximizing compression savings, GreedTok was shown to attain a constant fraction of the optimum on unrestricted alphabets; we establish a deterministic EPTAS for direct savings on every fixed alphabet and analyze greedy selection by true marginal gains. For exact optimization, we give a binary direct algorithm running in 2^O(n
1
0
4
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Strong Backdoor to Forests is FPT: Tight Linear-Time FPT for Essentially General SAT

Olesia Bilyk, Aidar Munduzbaev, Roohani Sharma, Mamnoon Siam
arxiv.org/abs/2611.12321 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙲𝙲]
In a seminal work, Gaspers and Szeider [FOCS 2013] gave a fixed-parameter tractable (FPT) approximate algorithm for finding a strong backdoor of size at most k to incidence treewidth at most t, for a given CNF-formula Ο†. In particular, their algorithm runs in f(k,t) |Ο†|Β³ time, and finds a strong backdoor to treewidth at most t, of Ο†, of size at most 2ᡏ whenever there exists one of size at most k. Determining whether the detection of strong backdoors to bounded incidence treewidth is FPT parameterized by k+t was left open in their work and this has been repeatedly posed as an open question by Gaspers and Szeider, for example in [The Multivariate Algorithmic Revolution and Beyond 2012] and more recently in [Computer Science Reviews 2025], even for incidence forests and when the input is a 3-CNF formula. We answer this question affirmatively. We show that strong backdoors to forests can be found in linear-FPT time on arbitrary non-tautological CNF formulas (not just on 3-CNF formulas). Gi
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
A 1.764-competitive algorithm for online fractional vertex cover on forests

Marcin Bienkowski
arxiv.org/abs/2611.12237 [𝚌𝚜.π™³πš‚]
We study online fractional vertex cover on forests under edge arrival. We give a deterministic algorithm with competitive ratio at most 4 - √5 β‰ˆ 1.764, which simultaneously produces an online fractional matching with competitive ratio of at least 1/(4 - √5) β‰ˆ 0.566. This improves on the previous best competitive ratios of 11/6 β‰ˆ 1.833 and 5/9 β‰ˆ 0.555, respectively.
1
0
3
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Tight Competitive Bounds for Online Matching on Forests

BartΕ‚omiej Bosek, Grzegorz Gutowski, PaweΕ‚ Putra, Anna Zych-Pawlewicz
arxiv.org/abs/2611.12210 [𝚌𝚜.π™³πš‚]
We study the online matching problem, its fractional relaxation, and the fractional online vertex cover problem on forests whose edges arrive one at a time in an arbitrary order. Matching decisions are irrevocable, and vertex-cover weights can only increase over time. For online matching, we present a randomized algorithm with expected competitive ratio 4/7 against an oblivious adversary, improving the previous 5/9 guarantee. We also present a deterministic algorithm that simultaneously maintains a 4/7-competitive fractional matching and a 7/4-competitive fractional vertex cover. This deterministic algorithm improves the previous 5/9 guarantee for fractional matching and the 11/6 guarantee for fractional vertex cover. We prove that 4/7 is optimal for both randomized and fractional matching, even on growing trees of maximum degree four.
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Instance-Optimality of Single-Pair Personalized PageRank

Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup, Hanzhi Wang, Shuyi Yan
arxiv.org/abs/2611.12198 [𝚌𝚜.π™³πš‚]
We consider discounted random walks in a directed simple graph G=(V,E). Such a walk terminates at each step with a constant probability α∈ (0,1) and otherwise continues to a uniform random out-neighbor. Given a pair (s,t)∈ VΒ², we denote by Ο€(s,t) the probability of such a discounted random walk starting at s terminates at t. This probability is referred to as the Personalized PageRank (PPR) of t with respect to s. The problem of estimating Ο€(s,t) within a constant multiplicative factor with constant success probability for a given vertex pair (s,t) is called the single-pair PPR estimation problem. We investigate the instance-optimality of single-pair PPR estimation in directed graphs. We present a new algorithm that aims at instance-optimal running time up to polylogarithmic factors. In other words, no correct algorithm can run faster than our algorithm on any valid graph by more than a polylogarithmic factor. We show that our algorithm is instance-optimal in the standard adjacency-lis
0
0
1
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Longest Unbordered Factors in Linear Time

Takuya Mieno
arxiv.org/abs/2611.12146 [𝚌𝚜.π™³πš‚]
A border of a string is a nonempty proper prefix that is also a suffix. A string is unbordered if it has no border. The length of a longest unbordered factor is closely related to the smallest period of the string. While the smallest period can be computed in linear time, the best previously known algorithm for computing a longest unbordered factor takes O(n log n) worst-case time for a string of length n. Whether this computational problem can be solved in worst-case linear time has remained open. In this paper, we resolve this open problem for integer alphabets of size nᴼ⁽¹⁾ by presenting an algorithm that computes all occurrences of longest unbordered factors in O(n) worst-case time. Our algorithm uses a combinatorial property of longest unbordered factors and scans the input string in both directions to capture all occurrences achieving the global maximum without computing the local maximum at every starting position.
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
The Power of Migration on Identical Machines is Two

Nicole Megow, Bart Zondervan
arxiv.org/abs/2611.12034 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙳𝙼]
We study the power of migration in preemptive scheduling on identical parallel machines with time windows. If an instance admits a migratory schedule on m machines, how many machines are needed to schedule it without migration? Kalyanasundaram and Pruhs (2001) showed that 6m-5 machines suffice and gave a polynomial-time construction using 12m-5 machines, whereas 2m-1 machines may be necessary. We close this gap, which has been open for more than 25 years: 2m-1 machines always suffice, and a corresponding non-migratory schedule can be computed in strongly polynomial time. Our proof has two main technical ingredients. First, we introduce supercanonical schedules and prove that the conflict graph of every such schedule on m machines is (2m-1)-colorable. The key property is that whenever a job pauses, the jobs running alongside it just before and just after the pause separate the jobs processed entirely during the pause from the rest of the conflict graph. We use these separators and Kempe
0
0
1
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Tight Bounds for Sublinear Metric Steiner Tree

Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, Ali Vakilian
arxiv.org/abs/2611.11986 [𝚌𝚜.π™³πš‚]
In the metric Steiner tree problem we are given an n-point metric space (V,w) and a set TβŠ† V of terminals, and we seek the smallest weight OPT of a tree that spans T and may use points of Vβˆ– T. We study sublinear algorithms in the distance-oracle model, where the algorithm knows V and T upfront and can query the distance function w. The objective is to estimate OPT while querying significantly fewer than nΒ² distances. The minimum spanning tree on T estimates OPT within a factor 2, and its weight can be approximated with OΜƒ(n) queries. The natural question that has been studied is therefore the query complexity of estimating OPT within a factor strictly below 2. Chen, Khanna, and Tan [SODA 2023] gave such an algorithm using OΜƒ(nΒΉΒ³/⁷) queries, and a lower bound of Ξ©Μƒ(n⁢/⁡). Later Mahabadi, Roghani, Tarnawski, and Vakilian [ITCS 2025] improved the algorithm to OΜƒ(n⁡/Β³), and Mahabadi, Tarnawski, and Vakilian [ITCS 2027] improved the lower bound to Ξ©Μƒ(n⁷/⁡). In this work we settle the above
0
0
4
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
How Far Must a Test Explore? Certifying Composable Read-Write Interfaces from Their Own Random Edits

Jiaxuan Guo, Xingyu Ren, Jingxin Yang, Youran Sun, Haizhao Yang
arxiv.org/abs/2611.11899 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙻𝙢 𝚌𝚜.𝙿𝙻 𝚌𝚜.πš‚π™΄]
Random tests of stateful code check laws, like reading back a written value, at states that random writes reach. The laws hold at every state exactly when the code behaves like a record with hidden data, so a pass is taken as evidence. This can fail: the laws can hold at every sample while the code is far from any record. The laws are local, but behaving like a record is global. Self-testing and stability theorems bridge this gap when the query distribution is controlled by the tester or preserved by the tested maps, but here it is generated by the tested writes, which need not be invertible. We ask how far a test must explore. An interface has m binary variables, each with a read and two writes; in a record, reads return their bits and writes set only their bits. Samples are the ends of geometric runs of mean β„“ of uniformly random writes from a start distribution; a tester adds its own write chains of depth d. The distance is the least, over records with hidden data, of the largest pr
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Internal Queries for Maximal Closed Substrings

Simone Faro, Francesco Pio Marino, Arianna Pavone
arxiv.org/abs/2611.11552 [𝚌𝚜.π™³πš‚]
Searching for repetitions inside a selected part of a text raises a subtle boundary problem: removing neighbouring characters can create new maximal answers. We study this effect for maximal closed substrings (MCSs). A string is closed if it is a single letter or has a nonempty proper prefix occurring exactly twice, as its prefix and suffix; a closed occurrence is maximal if neither available one-character extension is closed. Previous work established O(nlog n) bounds on the global MCS families of a length-n text and developed enumeration algorithms. Internal queries instead ask for the MCSs of a chosen substring, with maximality evaluated inside that substring. Separating boundary occurrences from interior ones gives an O(nlog n)-word index that reports the c answers in O(log n+c) time and supports counting and longest queries in O(log n) time. Our main result reduces reporting space to O(n) words, with O((c+1)logΒΉ+Ξ΅ n) query time and O(nlogΒΉ+Ξ΅ n) construction time for any fixed Ξ΅>0.
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Induced-Minor-Free Graphs Admit a Star-Based Separator of Size Γ•(√n)

Arnold Filtser, Nikolai Karol, Hung Le, Florian Lehner
arxiv.org/abs/2611.11513 [𝚌𝚜.π™³πš‚ πš–πšŠπšπš‘.𝙲𝙾]
Given an H-induced-minor-free graph G with n vertices, we construct a balanced separator of G consisting of Γ•(|V(H)|√n) star subgraphs. Our result is an induced-minor-free analog of the famous separator theorem for H-minor-free graphs by Alon, Seymour, and Thomas [J. Amer. Math. Soc., 1990]. A key idea in our construction is a new decomposition of H-induced-minor-free graphs, analogous to the cop decomposition for H-minor-free graphs by Andreae [J. Combin. Theory Ser. B, 1986]. We also discuss several algorithmic applications of our result.
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Amortized Cell-Probe Lower Bounds for Dynamic Boolean Problems

Young Kun Ko
arxiv.org/abs/2611.11508 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙲𝙲]
We prove the first unconditional amortized Ξ©((log N/loglog N)Β²) cell-probe lower bound for a Boolean dynamic problem. For insert-only multiphase Disjointness with N query sets over [N] and word size w=Θ(log N), a fixed distribution of interleaved insertions and queries forces this expected average cost per operation, excluding preprocessing. The bound allows sufficiently small constant error for each query of every fixed legal sequence and imposes no restriction on individual operation costs. It transfers to incremental directed reachability, incremental subgraph connectivity, and fully dynamic triangle detection. We also prove tq=Ξ©((log N/log(t_uw))Β²) for amortized insertion time 1≀ t_u=N^o(1) and expected query time tq, when the number of insertions before the final query is not announced in advance. We reach the quadratic-logarithmic scale with bounded error by combining interleaving with the 2.5-round communication framework [Ko26a, Ko26b] and controlling errors among accepted simu
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Γ•ptimal Facial Distance Labeling in Planar Graph

Noy Rotbart, Oren Weimann
arxiv.org/abs/2611.11479 [𝚌𝚜.π™³πš‚]
We show how to assign labels of size Γ•(nΒΉ/Β³) to the vertices of a face F in an n-vertex unweighted undirected planar graph G s.t one can deduce the distance between any two vertices of F given their labels alone. This matches (up to log factors) the Ξ©(nΒΉ/Β³) lower bound of Gavoille, Peleg, PΓ©rennes, Raz from 2004. Prior to our work, the smallest labels were of size O(nΒΉ/Β²).
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Tight B-Trees for Adjacency Labeling

Noy Rotbart
arxiv.org/abs/2611.11444 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙳𝙼]
We show that planar graphs admit adjacency labels of size log n+O(loglog n): every vertex gets a label of this many bits, and the adjacency of two vertices is decided from their labels alone, in constant time. This improves the log n+O(√(log nloglog n)) of Dujmovi\'c et al. (J. ACM 2021) and the log n+O(√(log n)) of Gawrychowski and Janczewski (SOSA 2022). Equivalently, n-vertex planar graphs have an induced-universal graph with n(log n)^O(1) vertices, down from n2^O(√(logn)). The same holds for graphs of bounded genus, apex-minor-free graphs and k-planar graphs. For every proper minor-closed class we get log n+O(√(log nloglog n)), down from the log n+O((log n)³/4) of Dujmovi\'c et al. (2026). Both results come from tight B-trees: nodes are split into parts of nearly equal size, so every node but the topmost stays within a factor 1± O(1/log n) of its target size, and a root-to-leaf path loses only O(loglog n) bits.
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Linear Set Reconciliation with O(d) Additive Redundancy

Tianren Liu, Rui Xu, Tong Yang, Kangyang Zhou
arxiv.org/abs/2611.11409 [𝚌𝚜.π™³πš‚ 𝚌𝚜.π™Έπšƒ πš–πšŠπšπš‘.π™Έπšƒ]
In set reconciliation, two parties holding sets A, B βŠ† [n] with |A triangle B| ≀ d seek to recover their symmetric difference from short Fβ‚‚-linear sketches, which is equivalent to recovering a d-sparse vector x = 1_AtriangleB ∈ Fβ‚‚^n from its syndrome Hx ∈ Fβ‚‚^m. While the information-theoretic counting bound requires L(n,d):=log \sum_i=0^d binomni = dlog(n/d) + Θ(d) bits, existing polynomial-time schemes either use at least d⌈log(n+1)βŒ‰ bits (algebraic sketches, leaving an Ξ©(dlog d)-bit gap) or incur a multiplicative (1+Ξ΄)L(n,d) overhead (peeling-based sketches), raising the question of whether L(n,d) + O(d) bits is achievable with fast updates and decoding. We construct a public-coin randomized Fβ‚‚-linear sketch of length L(n,d) + O(d) + Ξ»log^O(1) n that recovers each fixed input of weight at most d with probability at least 1 - 2^-Ξ», with log^O(1) n update time and dexp(O((loglog n)Β²)) = dn^o(1) worst-case decoding time. In particular, for n ≀ 2^polylog(d) and Ξ» ≀ dΒΉ-Ξ©(1), this achieves
1
0
2
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Algorithms for Soft Tree Containment on Tree-Child Networks

Erdem Ugurlu, Louxin Zhang
arxiv.org/abs/2611.11236 [𝚌𝚜.π™³πš‚ 𝚚-πš‹πš’πš˜.𝙿𝙴]
Phylogenetic networks generalize evolutionary trees by allowing lineages to merge. The Tree Containment problem asks whether a network N displays a tree T on the same taxa. When the polytomies of T reflect uncertainty rather than simultaneous divergence, the relevant notion is soft display, in which N may refine the polytomies of T. We take it in its asymmetric reading. Soft Tree Containment is NP-hard on reticulation-visible networks even at reticulation indegree three, and it was open for a non-binary tree and a tree-child network with multifurcating tree nodes or reticulations of indegree above two. We solve this case. A cluster characterization reduces soft display to realizing all clusters of T by one switching, and in a tree-child network the vertices that can realize a cluster lie on a single chain. The per-cluster requirements then form a constraint network of width one, which arc consistency decides without search, and a 2-SAT instance when N is binary. This yields, to our kno
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Fast Approximate β„“β‚š Chamfer Distance via Lopsided Embeddings and Structured JL

Ying Feng, David P. Woodruff
arxiv.org/abs/2611.11151 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙻𝙢]
For two d-dimensional point sets A, B of size n, the Chamfer distance from A to B is defined as CH(A,B)=\sum_a∈A min_b∈B dist(a, b), where dist is some underlying distance measure. We present efficient algorithms for approximating the Chamfer distance under the \ell_p norm for 1 < p ≀ 2. For the general case 1 < p < 2, we utilize lopsided \ell_p to \ell₁ embeddings with weak guarantees. We show that they are sufficient for preserving the Chamfer distance. In the high-dimensional regime, we use Fast Matrix Multiplication techniques to speed up the lopsided embeddings. These lead to O(ndβ‹… poly(log log n, log(1/Ξ΅))/Ρ²) total time. For the specific Euclidean case (p=2), we leverage the Fast Johnson-Lindenstrauss Transform based on Toeplitz matrices and re-analyze the previous \ell₁-specific Chamfer algorithm in \ellβ‚‚. These achieve a runtime matching the recent state-of-the-art \ell₁ result of O(nd(log log n + log (1/Ξ΅))/Ρ²), improving upon the previous O(nd log n/Ρ²) bound for \ellβ‚‚. We a
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Online Correlated Exponential Clocks

Zhiyi Huang, Kalen Patton, Peilin Yang, Jiahao Zhao
arxiv.org/abs/2611.11133 [𝚌𝚜.π™³πš‚]
In online resource allocation, we seek to allocate an incoming sequence of requests j ∈ J among a set of offline resources i ∈ I, where decisions must be made immediately without knowledge of the future. State-of-the-art results typically follow from relax-and-round methods. For many problems, recent advances have come from improved methods of online rounding with negative correlations. However, such rounding schemes have largely been implemented on a case-by-case basis, making it difficult to transfer improvements and new ideas between problem settings. This leads us to ask the question: Can we develop unified methods of online rounding with negative correlations which can obtain state-of-the-art guarantees across different resource allocation settings? We answer this question affirmatively by introducing the framework of Online Correlated Exponential Clocks (OCEC). In this framework, fractional allocations xᡒⱼ are assigned exponential clocks Yᡒⱼ ∼ Exp(xᡒⱼ), and each request j is allo
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Optimal Polynomial-Query Approximation for Consistent Submodular Maximization with Short Lookahead

Vaneet Aggarwal
arxiv.org/abs/2611.11124 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙻𝙢 πš–πšŠπšπš‘.𝙾𝙲]
Elements arrive one at a time, and after each arrival an algorithm holds a set of at most k arrived elements. Its goal is a held set whose value under a monotone submodular function is close to the best value that k arrived elements can achieve. The recourse of an update is the number of elements inserted into or removed from the held set, and we require it to be bounded independently of k and of the number n of arrivals. With evaluations only on sets of arrived elements and polynomially many of them, the best ratio a randomized algorithm can achieve is 2-√2β‰ˆ0.5858. We show that seeing future arrivals raises the best ratio for polynomially many evaluations to 1-1/eβ‰ˆ0.6321, for deterministic and for randomized algorithms; no algorithm with polynomially many evaluations exceeds 1-1/e, even when all elements are available at once. For every Ξ΅>0, a deterministic algorithm that sees the next ⌈Ρ k/3βŒ‰ arrivals keeps a set of value at least 1-1/e-Ξ΅ times the optimum at every time, changes O(Ρ⁻
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Solving Large Rubik's Cubes within a Factor of 2.37+o(1) of Optimal

Jeremy Mrzyglocki, Tomas Rokicki, Maxine Perroni-Scharf, Erik D. Demaine
arxiv.org/abs/2611.11018 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙲𝙲]
We design optimized algorithms to solve the n Γ— n Γ— n Rubik's Cube within 30.5 nΒ² / \lg n + o(nΒ² / \lg n) moves. This upper bound is asymptotically within a factor of 2.37 of the known lower bound, which applies to almost all instances. The constant 30.5 is also the first explicit constant factor for the known upper bound of O(nΒ² / \lg n), where the implicit constant of the previous algorithm was 1.01 β‹… 10⁴⁰ (ten duodecillion). Thus we improve the upper-bound constant by a factor of more than 3.30 β‹… 10³⁸ (330 undecillion). Our algorithm runs in time linear in the input size N = Θ(nΒ²), and uses O(√N \lg N) extra space (beyond the state of the cube). Our implementation is the first practical cube solver to generate solutions of length O(nΒ²/\lg n). Our latest solver outperforms existing solvers for n as small as 840.
1
0
5
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
Tunnels: Compressing the Solution Subgraph of Regular Path Queries

AdriΓ‘n GΓ³mez-BrandΓ³n, Gonzalo Navarro
arxiv.org/abs/2611.10736 [𝚌𝚜.π™³πš‚]
Regular path queries (RPQs) are increasingly expected to return the paths that match them, not only their endpoints. Since the number of matching paths can be exponential or infinite, a standard way to deliver them (PMR) is the subgraph \Hs of the product between the graph and the query automaton that contains exactly the nodes lying on some solution path. We show that \Hs can be compressed much further when the graph is available to the decoder: most of \Hs can be regenerated by re-running small parts of the traversal, and only the places where the traversal would waste significant effort on dead branches need to be stored. We formalize this as tunnels: regions of \Hs that are re-expanded from a stored entry point with a bounded amount of extra work, either an absolute budget or one proportional to the output produced. We handle the three classes of RPQs: constant-to-variable, constant-to-constant, and variable-to-variable. In the latter, we study the combination of tunnels with cutti
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 11
An Improved Algorithm for Quantified Boolean Formulas

Zhiyang Chen, Hailong Yao
arxiv.org/abs/2611.10633 [𝚌𝚜.π™³πš‚ 𝚌𝚜.𝙰𝙸]
Quantified Boolean formula (QBF), the quantified version of Boolean satisfiability (SAT), is a fundamental problem in constraint solving. Due to the PSPACE-complete nature of QBF, designing theoretically efficient QBF algorithms is much harder and receives less attention in academia. In this work, we present a new algorithm based on memoized search, which solves QBF with n variables and m clauses in 1.685ᡐ⋅poly(n) time and space. This is the first improvement over the 1.709ᡐ⋅poly(n) bound by Williams in over 20 years. Our technique is based on the minimum vertex cover of the conflict graphs, which was proposed to study the parameterized complexity of SAT. We extend this idea to QBF and further show that QBF is slicewise polynomial-time solvable using this parameter.
0
1
5
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 10
Close and Sort: Exact Maximum-Likelihood Aggregation of Cyclic Rank-Two Preferences

Kehan Liu, Zhaoyun Chen, Xianquan Yan
arxiv.org/abs/2611.10538 [𝚌𝚜.π™³πš‚ 𝚌𝚜.π™Έπš 𝚌𝚜.𝙻𝙢 𝚜𝚝𝚊𝚝.𝙼𝙻]
Pairwise probabilities arise in rank aggregation, recommendation, and human or LLM evaluation, yet converting them into a maximum-likelihood list is a weighted Kemeny problem and is NP-hard in general. Known exact algorithms for rank-two tournaments use only comparison signs and do not optimize this likelihood. We show that the weighted problem is exactly solvable when the skew-symmetric log-odds matrix Wα΅’β±Ό=log(pα΅’β±Ό/pβ±Όα΅’) has rank two, including when the induced preferences contain cycles. Writing Wα΅’β±Ό=det(hα΅’,hβ±Ό) and adding the closing vector hβ‚€=-βˆ‘α΅’ hα΅’ turns the objective into twice the signed area of a closed polygon. This geometry yields CloseSort, which polar-sorts the n+1 edge vectors, cuts after hβ‚€, and returns a global maximum-likelihood order in O(nlog n) time from the factors. The same geometry identifies the runner-up and gives a stability certificate beyond exact rank two. When the smallest determinant Ξ΄ of two consecutive edges in the closed angular cycle is positive, it is exa
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 10
Lower Bounds Above √3 for Online Makespan Minimization on Four Identical Machines

Maximilian Janke
arxiv.org/abs/2611.10440 [𝚌𝚜.π™³πš‚ πš–πšŠπšπš‘.𝙾𝙲]
For deterministic online makespan minimization, m = 4 identical machines is the smallest case whose optimal competitive ratio is open: it is known only to lie between √3 β‰ˆ 1.73205 and 26/15 β‰ˆ 1.73333. We prove a lower bound of 14383/8304 β‰ˆ 1.73206 using a single branching layer, and refine the construction with a second, mirrored branching layer to obtain 14350/8283 β‰ˆ 1.73246, closing about a third of the gap. Our constructions are the first branching adversaries for m = 4 machines, and the first explicit lower bounds for online makespan minimization in which the adversary presents jobs in non-monotone order of size.
0
0
0
Data Structures and Algorithms Papers@AlgorithmPapers
Nov 10
Randomized Greedy MIS Is Fast at Every Node of a Tree

Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović, Srikkanth Ramachandran
arxiv.org/abs/2611.10215 [𝚌𝚜.π™³πš‚]
The Randomized Greedy MIS (RGMIS) algorithm computes a maximal independent set (MIS) by processing the vertices in a uniformly random order and greedily adding each vertex to the independent set whenever possible. Despite its simplicity, this algorithm has proved effective in a range of parallel, distributed, and dynamic settings. For sufficiently small maximum degree, Nguyen and Onak (FOCS '08) and Yoshida, Yamamoto, and Ito (STOC '09) showed that a recursive simulation of RGMIS can be used to estimate the sizes of matching and vertex cover in sublinear time. The key subroutine in their approach is the following local query procedure: given a vertex v, to determine whether v belongs to the MIS, recursively evaluate the neighbors of v that precede v in the random order. If any such neighbor is found to belong to the MIS, the procedure immediately concludes that v is not in the MIS; otherwise, it concludes that v is in the MIS. For graphs of maximum degree Ξ”, Nguyen and Onak showed that
0
0
4
Load more