CS Paper Radar

A 1.764-competitive algorithm for online fractional vertex cover on forests

Marcin Bienkowski

cs.DS ·submitted 2026-11-09 11:28 UTC · v1
hot direction

Abstract

We study online fractional vertex cover on forests under edge arrival. We give a deterministic algorithm with competitive ratio at most $4 - \sqrt{5} \approx 1.764$, which simultaneously produces an online fractional matching with competitive ratio of at least $1/(4 - \sqrt{5}) \approx 0.566$. This improves on the previous best competitive ratios of $11/6 \approx 1.833$ and $5/9 \approx 0.555$, respectively.

Closest papers

Nearest neighbours by meaning across the whole index.

Tight Competitive Bounds for Online Matching on Forests

cs.DS ·2026-11-09 ·Bartłomiej Bosek, Grzegorz Gutowski, Paweł Putra, Anna Zych-Pawlewicz
theory similarity 0.87
Abstract

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.40

Online and Incremental Fractional Vertex Cover on Trees

cs.DS ·2026-08-25 ·Júlia Baligács, Bartłomiej Bosek, Yann Disser, Andreas Emil Feldmann, Grzegorz Gutowski +3 more
publishedtheory similarity 0.82
Abstract

In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori and the edges arrive one at a time. The goal is to maintain a fractional vertex cover of the tree, i.e., an assignment of fractional weights from [0,1] to the vertices such that the weights of endpoints of every edge sum up to at least one. After each edge arrival, we need to modify the fractional vertex cover to cover the new edge as well. However, we can only increase the values assigned to vertices. The problem was studied before (in the vertex arrival model) by Wang and Wong, who motivated it as a generalization of the ski-rental problem, but also (more importantly) by its close connection to the dual online matching problem. They presented a 1.901-competitive algorithm for general graphs in the vertex arrival model. We present an $\frac{11}{6} \approx 1.83$-competitive algorithm for trees in the more general edge arrival model. In addition, we study the fractional vertex cover problem in an incremental model, where we again seek a fractional vertex cover after every update, but all the updates to the tree are known to the algorithm a priori. In this model, we give a 1.5-competitive algorithm and provide a matching lower bound.

0.46

Asymptotically Tight Fractional Online Matching Under Edge Arrivals

cs.DS ·2026-08-24 ·David Wajc
theory similarity 0.72
Abstract · Note. See Section 3 (Reflections) for broader discussion on the impact of LLMs on mathematical research

In this brief note, we close the asymptotic gap between known upper and lower bounds for fractional online matching under edge arrivals. We prove that the optimal competitive ratio for this problem is $1/2+Θ(1/n)$. The algorithm was suggested and analyzed by OpenAI's ChatGPT Sol based on a single prompt. The presentation was streamlined over a few hours, based on a back and forth discussion with the author, who assumes responsibility for any errors.

0.14

A New Lower Bound for Online Vertex Cover under Vertex Arrivals

cs.DS cs.GTmath.OC ·2026-08-10 ·Tianhang Lu
theory similarity 0.62
Abstract

We prove that no randomized integral or fractional algorithm for online vertex cover under general vertex arrivals achieves a competitive ratio strictly below $1+\sqrt{e}/2\approx1.824360635$, even on bipartite graphs and against an oblivious adversary. This improves the previous lower bound of approximately $1.753$. Our proof extends the complete-bipartite alternating construction of Wang and Wong to an arbitrary number of alternations. The resulting adversary is described by a monotone integral recurrence. If the recurrence never violates the competitive budget, its iterates converge to an integrable fixed point; classifying all such fixed points forces the excess ratio to be at least $\sqrt{e}/2$. A truncated discrete recurrence and a Riemann-sum argument convert every strict continuous violation into a finite, algorithm-dependent but realization-oblivious input. We also exhibit a critical fixed point showing that $1+\sqrt{e}/2$ is the exact limit of this homogeneous complete-bipartite recurrence, rather than a numerical artifact.

0.04

Sublogarithmic Online Graph Exploration

cs.DS cs.DM ·2026-11-10 ·Julia Baligacs
similarity 0.58
Abstract

We study the online graph exploration problem, in which an agent must visit every vertex of an initially unknown weighted graph on $n$ vertices and return to its starting vertex. In this model, a vertex's incident edges and their weights are revealed when it is first visited. Despite extensive research, the best known competitive guarantee for general graphs had remained $\mathcal{O}(\log n)$, a bound already established in 1977 for the greedy TSP heuristic Nearest Neighbor. Subsequent approaches, including hierarchical depth-first search (hDFS) and Blocking, achieve better guarantees on restricted graph classes but have logarithmic or worse competitive ratios on general graphs. This raises the question of whether the logarithmic barrier is inherent and Nearest Neighbor is asymptotically optimal. We answer this question in the negative by giving an $\mathcal{O}(\log n/\log \log n)$-competitive algorithm. Our algorithm is a slight modification of hDFS, and we establish its competitive guarantee with a surprisingly short proof.

0.22

Online Timely Bin Packing Revisited: A Simpler Algorithm with Optimality in Special Cases

cs.DS ·2026-11-06 ·Pei-Lin Chiang, Wing-Kai Hon, Ying-Chia Huang, Li-Tzu Yang
theory similarity 0.57
Abstract · 17 pages, 1 figure

Online Timely Bin Packing is a variant of classical online bin packing in which items arrive over time with sizes and deadlines. Packing an item may be deferred until its deadline, but once a collection of items is packed into a bin, the bin is closed and cannot be used again. The objective is to minimize the total number of bins used. The problem was introduced by Khattar in 2023. In 2025, Aminian proposed Discrete-Greedy, a deterministic online algorithm with a competitive ratio of exactly $2$, which remains the best-known upper bound. Its analysis is particularly simple; however, the algorithm requires maintaining a fractional simulation internally and may leave usable space in some bins unfilled. We propose Thrifty-Greedy, a simple deterministic online algorithm that does not require a fractional simulation. We prove that its competitive ratio is exactly $2$, matching the best-known upper bound. At the same time, the algorithm automatically achieves the optimal competitive ratio on two natural classes of inputs: it is $1$-competitive when all items have the same size, and $1.5$-competitive when every item has size in $\{1/3,2/3\}$. In contrast, Discrete-Greedy has a competitive ratio of at least $2$ on both classes.

0.19

Consistency-Robustness Tradeoffs for Online Bipartite Allocation with Multiple Stages

cs.DS ·2026-09-14 ·Alexander Lindermayr, Nicole Megow, Lauren Paul
similarity 0.57
Abstract

We study learning-augmented online bipartite allocation with multiple stages. In the $k$-stage vertex-weighted fractional bipartite matching problem, demand vertices arrive in $k$ stages, and the algorithm receives possibly inaccurate predictions of the allocation in each stage. While tight consistency-robustness tradeoffs were known for the two-stage case, no nontrivial tradeoff was known for an arbitrary number of stages. Our main result is the first consistency-robustness tradeoff for $k$-stage vertex-weighted fractional bipartite matching with predictions, for every $k\ge2$. Let $R_k=1-(1-1/k)^k$. For every $R\in[0,R_k]$, our algorithm is $R$-robust and $C_k(R)$-consistent, where $C_k(R)=k(1-R)^{1/k}+R-(k-1)$. This simultaneously recovers the known tight two-stage tradeoff and the optimal prediction-free $k$-stage competitive guarantee $R_k = C_k(R_k)$, while strictly dominating the natural randomized coin-flip baseline between these endpoints. We also present an algorithm for the classical online setting, where demands arrive one by one and the number of demands is unknown in advance. It has a consistency ratio of at least $C_\infty(R)=1+R+\ln(1-R)$ for a given robustness $R\in[0,1-1/e]$, improving the best previously known tradeoff for this problem. Finally, we extend the framework to fractional AdWords and fractional predictions. Our algorithms are based on stage-wise convex programs with carefully calibrated vertex-dependent penalties. The penalties maintain a dynamic safety reserve for each supply vertex, balancing protection against adversarial future arrivals with the ability to exploit the predicted allocation.

0.21

A Sublogarithmic Competitive Algorithm for Online Graph Exploration

cs.DS ·2026-11-10 ·Max Klimm
similarity 0.57
Abstract

In online graph exploration, an agent must visit every vertex of an unknown weighted graph and return to its start, learning the incident edges at each vertex it visits. On $n$-vertex graphs, the best known competitive ratio has been $O(\log n)$, achieved by several algorithms, among them the hierarchical depth-first search of Megow, Mehlhorn, and Schweitzer. We give an algorithm with competitive ratio ${(2+o(1))}\ln n/\ln\ln n$ for known~$n$. Like hierarchical depth-first search, it groups the edges into geometric weight classes and searches depth-first between components of lighter edges. Unlike it, the agent tours each component along a minimum spanning tree for the original weights, so only crossings between components pay for rounding, and the base $b$ of the weight class can grow with~$n$. The leading constant $2$ is tight for our choice of base. Without knowing $n$, restarts with increasing size guesses give upper bounds with leading constant $4$ for a fixed schedule and $2$ in expectation for a randomly shifted schedule. If the weights lie in a known range $[1,2^k]$ with $k\ge4$, choosing $b=k/\log_2 k$ gives a competitive ratio of $O(k/\log k)$ without knowing $n$.

0.25