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
433
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
223
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
80
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
101
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
125
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
118
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
65
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
174
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
69
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
72
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
193
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
71
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
61
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
77
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
128
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
59
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
66
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
61
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
91
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
71
Load more