CS Paper Radar

On the Cyclic Assumption of the Cow-Path Search Algorithm

Yuan Ma, Yiqun Lisa Yin

cs.DS cs.LG ·submitted 2026-10-07 15:32 UTC · v1

Abstract

In the cow-path problem, a cow must find a goal lying at an unknown distance on one of $w$ paths connected only at the origin, and performance is measured by competitive ratio. Kao, Reif and Tate designed an efficient randomized algorithm in which the cow visits the paths in a fixed cyclic order. They proved the algorithm is optimal for $w=2$, and subsequently Kao, Ma, Sipser and Yin proved its optimality for all $w$, with a claim that no algorithm does better than the best cyclic one. This note provides a detailed proof of that claim.

Closest papers

Nearest neighbours by meaning across the whole index.

Strategyproof Mechanisms for Connecting Impassable Regions

cs.GT ·2026-09-08 ·Hau Chan, Jianan Lin, Chenhao Wang
theory similarity 0.54
Abstract

We study strategyproof mechanisms for building a pathway between two regions of a line segment separated by an obstacle. Each of the $n$ agents has a private location within its region and may use either its original route to a facility or the new pathway, whose traversal cost is a fraction $k\in[0,1)$ of its length. We seek strategyproof (SP) and group-strategyproof (GSP) mechanisms that approximately minimize maximum cost or social cost. After characterizing optimal pathways for both objectives, we establish a tight deterministic maximum-cost approximation ratio of $\frac{2}{1+k}$ and a deterministic social-cost upper bound of $\frac{n}{1+k(n-1)}$, together with complementary lower bounds. Both upper bounds are achieved by GSP mechanisms. We then study randomized mechanisms under strategyproofness in expectation. A power-proportional mechanism achieves a social-cost approximation ratio at most $5$, independent of $n$ and $k$, with a tight guarantee of $3$ for this mechanism when $k=0$. We prove randomized lower bounds of $\frac{3+2k}{2+3k}$ for maximum cost and $\max\big\{1,\frac{285}{263+385k}\big\}$ for social cost, the latter for $n\ge7$. Finally, we improve several bounds for the real-line pathway model of [Chan and Wang, AAMAS 2023]. Our deterministic maximum-cost lower bound of $2$ matches the upper bound obtainable from [Qin, Fang, and Liu, COCOA 2024]. We strengthen the deterministic social-cost lower bound from $\frac32$ to $2$ under SP and to $\max\{2,n-1\}$ under GSP. For randomized social cost, we sharpen the guarantee of Chan and Wang's proportional mechanism from $6$ to $3$ and raise their lower bound from $1.02$ to $\frac{285}{263}\approx1.08365$ for $n\ge7$.

0.19

Selecting k Paths with the Minimum Longest Path Length in the Stochastic Semi-Bandit Setting

cs.LG ·2026-09-13 ·Shunsuke Aoki, Atsuyoshi Nakamura
similarity 0.53
Abstract

When performing parallel data transmission through a network using multiple paths, it is practically important to minimize the maximum transmission time among the selected paths. This study addresses an online problem in which $k$ paths from an origin vertex to a destination vertex must be selected at each time step within a network represented as a directed graph. Here, the number of paths going through each edge in each parallel data transmission is limited to its capacity, and the time required for transmission is determined stochastically. We formulate the semi-bandit problem of selecting a set of paths to minimize the maximum traversal time among the selected paths and propose an algorithm to solve it.

0.27

Evacuating from Eventually Emerging Targets on the Line

cs.DM ·2026-11-15 ·Konstantinos Georgiou, Caleb Jones, Liza Krupsky
theory similarity 0.52
Abstract · 52 pages

We introduce and study Eventually Emerging Linear Search, an online evacuation problem on the line that, to the best of our knowledge, has not been studied before. In this problem, $n$ unit-speed agents with wireless communication start at the origin and search for a hidden target at location $x$, where $|x|\geq1$, that becomes detectable at an unknown time $T$. Visiting $x$ before time $T$ reveals nothing, and the search terminates only when all agents have reached the target. We study two competitive measures. In the emergence-aware model, the target location becomes known to the offline algorithm at time $T$, giving cost $T+|x|$. In the fully-informed model, the offline algorithm knows $x$ from the beginning, giving cost $\max\{|x|,T\}$. For one agent, the optimal competitive ratio is $9$ under both measures, as in classical cow-path search. For two agents, we give an algorithm with competitive ratio $3+\sqrt6$ under both measures, and prove it optimal within the class of origin-separated algorithms, in which each agent performs strictly expanding origin-return excursions on a fixed half-line. We also prove the unconditional lower bounds $4.35$ and $4.38$ for the emergence-aware and fully-informed measures, respectively. These bounds are computer-assisted; we derive finite linear programming relaxations for arbitrary algorithms and certify their infeasibility using exact rational Farkas certificates. For three agents, we prove analytically the unconditional lower bounds $3.1014$ and $3.2823$ for the emergence-aware and fully-informed measures, respectively, and introduce a geometric three-peak family. Different parameter choices give the corresponding upper bounds $4.010599$ and $4.340445$. These bounds lie below the corresponding two-agent lower bounds, so a third agent provably improves both measures.

0.36

A Randomized $\frac32$-Approximation for Strategic Facility Location on a Circle

cs.GT ·2026-09-11 ·Hau Chan, Jianan Lin, Chenhao Wang
theory similarity 0.52
Abstract · v1 is finished in June 2026, and v2 is revised with the assistance of GPT Astra-6

We study strategyproof mechanisms for locating a single facility on a circle so as to serve a set of strategic agents under the utilitarian social cost objective. We analyze a simple parity-dependent mechanism that randomizes between the Random Dictator (RD) mechanism and the Proportional Circle Distance (PCD) mechanism. For an odd number \(n\) of agents, this mechanism mixes RD and PCD with equal probability, as originally proposed by Rogowski and Dziubi{ń}ski (IJCAI 2025). For even \(n\), it mixes RD with a random-deletion extension of PCD, in which one agent is removed uniformly at random before PCD is applied to the remaining agents. Our main result shows that this mechanism is strategyproof and achieves an approximation ratio of \(\frac32\) for every \(n\ge 3\). This improves the \(\frac74\) upper bound of Rogowski and Dziubi{ń}ski, which applied only to odd \(n\), and extends the guarantee to even numbers of agents. Finally, we establish a computer-assisted lower bound of \(1.088187\ldots\) on the approximation ratio of any randomized strategyproof mechanism, improving on the previous lower bound of \(1.0456\) due to Meir (SAGT 2019).

0.34

Faster Algorithms for Disjoint Paths in DAGs and Two Disjoint Shortest Paths

cs.DS ·2026-11-01 ·Yang Cao, Haoran Qi, Hanzhi Wang
similarity 0.52
Abstract

For $k$ vertex-disjoint paths with prescribed endpoints in a directed acyclic graph (DAG), the $O(mn^{k-1})$-time pebbling algorithm of Fortune, Hopcroft, and Wyllie [TCS 1980] has remained the fastest for every $k\geq3$ for over four decades, even when the paths must be shortest. We break this bound for every $k\geq3$ with randomized algorithms running in expected $O_k(m+n^{k-3+ω+\varepsilon})$ time for every $\varepsilon>0$, where $ω<2.372$ is the matrix multiplication exponent; this is $O_k(m+n^{k-0.62})$. For two disjoint shortest paths, we find the paths as fast as we detect them: in expected linear time on DAGs and on undirected graphs with polynomially bounded integer weights, and in expected $O(\min\{mn,n^{ω+\varepsilon}\})$ time on directed graphs whose cycles have positive weight, which on dense graphs is $o(mn)$ even for detection. All algorithms evaluate a polynomial whose monomials are the solutions: a new first-collision circuit speeds up the evaluation in DAGs, and a correlated extraction step at cuts crossed once by every path finds a solution at the cost of a constant number of evaluations.

0.20

Online Treasure Hunt in Vertex-Permuted Dynamic Rings

cs.DC cs.CC ·2026-09-10 ·Kamran Ayoubi, Bernard Mans, Lata Narayanan
similarity 0.51
Abstract · 21 pages, 3 figures

We study the problem of treasure hunt by a group of $k \geq 1$ agents in vertex-permuted dynamic rings (VP). In this model, the $n$ vertices remain on a ring but are permuted at each time step. We first show that treasure hunt is impossible for any $k \leq n-3$ agents, if there are no restrictions on the sequence of permutations used in the dynamic ring. We then study the $VP(δ)$ setting, in which for every pair $i, j$ of vertices, the edge $(i, j)$ is guaranteed to appear within $δ$ steps. We show that the class $VP(δ)$ is feasible only for $δ\geq \left\lceil \frac{n-1}{2}\right\rceil$. For the one-agent case, we show a tight bound of $Θ(δn)$ on the worst-case search time as well as competitive ratio of any online algorithm for treasure hunt, provided $δ\geq 2n$. We then give an optimal algorithm for $k$ agents, thereby showing that $k$ agents can obtain a speedup of $k$ on the worst-case search time. Finally, in the R-VP setting, in which in every step, the vertices are arranged as a ring according to a random permutation, we show that treasure hunt takes expected $Θ(n)$ steps against an oblivious adversary and $Θ(n \log n)$ steps against an adaptive adversary.

0.34

The Matroid Secretary Conjecture is True

cs.DS cs.GT ·2026-09-13 ·Sahil Singla
highly cited similarity 0.50
Abstract

We resolve the matroid secretary conjecture, giving an online algorithm that accepts each element of the offline optimum with probability at least $1/4$. The algorithm only needs the number of elements in advance and independence-oracle access to subsets of already-arrived elements; it does not need to know the matroid upfront.

0.30

Linear-Time Transformations Between Connectivity Maintenance and Points Spreading on Linear and Cyclic Domains

cs.CG ·2026-08-23 ·Nicolás Honorato-Droguett
similarity 0.50
Abstract

Given $n$ points on a line or closed cycle and a threshold $r>0$, the connectivity-maintenance problem is to move the points so that every gap between consecutive points is at most $r$, whereas the points-spreading problem requires every gap to be at least $r$. Li and Wang [CCCG 2015; CGT 2025] and Chen, Gu, Li, and Wang [SWAT 2012; DCG 2013] gave $O(n)$-time algorithms for the cyclic versions of min-max points-spreading and min-max connectivity-maintenance, respectively. Ghadiri and Yazdanbod [CCCG 2016] gave an $O(n\log n)$-time algorithm for the linear version of min-sum points-spreading. In this paper, we show that the two problems can be reduced in linear time to each other for both objectives and on both linear and cyclic domains. As an implication, min-sum connectivity-maintenance is solvable in $O(n\log n)$ time on both domains. Finally, we extend the reduction to points on a line with individual thresholds when their initial order is preserved.

0.20