TL;DR
It is shown that predictions enable an algorithm that is simultaneously O (1)-consistent and O (log n )-robust for online sorting with predictions, and this result is extended to the setting of multiple predictions.
We give a deterministic algorithm for online inverse linear optimization with regret $O(d)$, uniform in the horizon and $O(d^{2})$ time per round. A bound of this order was obtained recently by Dewasurendra, settling a question of Gollapudi et al.\ and of Oki and Sakaue, but by an improper rule that enumerates covers at every scale and costs $T^{\Theta(d)}$ a round; ours is the first efficient such bound and the first proper one. We build on the variable-metric framework of Sakaue et al., adding a self-normalized rank-one update, and we replace the $\log\det$ potential by the trace power $\tr(H^{-1/2})$, which is bounded outright and removes the $\ln T$. The bound also holds against an expert that does not optimize, and we give corruption-robust and rank-adaptive variants, and an application to convex minimization.
This paper studies fractional matching on general graphs in the fully online model of Huang et al. (JACM 2020), in which all vertices arrive online and remain available for only a limited time, and extends the classic Water-Filling algorithm to the fully online setting, establishing that Water-Filling is not optimal in the fully online setting.
Competitive analysis is central to the study of online algorithms, but upper bounds are often highly problem-specific. We develop a more unifying methodology via the minimax viewpoint. Guided by Yao's principle, we reduce worst-case competitive analysis to Bayesian online design under an arbitrary correlated prior over arrival sequences. For such a prior, let $X^*$ be the hindsight-optimal fractional solution for the realized instance, and let $X^{(t)}=\mathbb E[X^*\mid \mathcal F_t]$ be its posterior process. Our guiding rule is posterior matching: at each time $t$, choose the feasible online action that tracks the current posterior $X^{(t)}$ as closely as the online constraints permit. We show that this single principle yields optimal or near-optimal guarantees for several classical online fractional problems, including set cover, load balancing, matching and more general resource-allocation problems, recovering or improving state-of-the-art bounds in these settings with norm/concave objectives. Via known rounding reductions, it also yields randomized integral guarantees for weighted paging, MTS on star metrics, and ski-rental. At a technical level, our analysis reduces competitive guarantees to key probabilistic inequalities for the vector martingales generated by the posterior of the offline optimum. The resulting framework gives a reusable route from Bayesian online design under arbitrary correlated priors to information-theoretic worst-case competitive guarantees.
Consider the following problem of learning an unknown linear order on $n$ items. In each round, the learner guesses a complete ordering of the items and receives either confirmation that the guess is correct or a counterexample: a pair of items in the wrong order. The goal is to identify the unknown order using as few queries as possible. We study this problem when up to $k$ of the returned counterexamples may be untruthful, where $k$ is not known in advance. We determine the optimal query complexity up to constant factors: \[ \Theta(n\log n + nk). \] Thus, while the noiseless complexity matches the classical complexity of sorting, each untruthful counterexample incurs an additional cost of order $n$. The upper bound is based on a geometric representation of permutations and Gr\"unbaum's theorem, while the lower bound combines sorting arguments with a Condorcet-type construction. We also study the case where the target ranking has a low-dimensional geometric representation: each item is represented by a point in $\mathbb{R}^d$, and the ranking is obtained by projecting the points onto an unknown direction. For these classes we give an upper bound of $O(d^2\log n+dk)$ and a lower bound of $\Omega(d\log n+dk)$, leaving a factor of $d$ gap in the noiseless term.
We consider the problem of online packing of convex polygons into a strip by translations. While online algorithms with a constant competitive ratio have been known for rectangles for decades [Baker and Schwarz, SICOMP 1983], the current best algorithm for convex polygons has competitive ratio $O(n^{\log_2 3-1}\log n) = O(n^{0.59})$, where $n$ is the number of polygons. This algorithm was described by Aamand, Abrahamsen, Beretta, and Kleist [SODA 2023], who also proved a lower bound of $\Omega(\sqrt{\log n/\log\log n})$ on the competitive ratio of any algorithm. Their lower bound is obtained via a reduction from \emph{online sorting}, a problem introduced in the same paper, for which they established a lower bound on the competitive ratio. We introduce a new, natural online problem that we call online TSP scheduling. Here, points $x_1,\ldots,x_n$ arrive online from a metric space $(M,d)$, and upon arrival each $x_i$ must be assigned a visit time $p_i\in[0,\infty)$ satisfying $|p_i-p_j|\ge d(x_i,x_j)$ for all $j<i$. The cost of the schedule is $\max_i p_i$. We present an $O(\log^2 n)$-competitive algorithm for online TSP scheduling, and show how this implies an $O(\log^2 n)$-competitive algorithm for online translational strip packing of convex polygons. We also prove that the same competitive ratio is achievable for other translational packing problems, including online packing of $d$-dimensional unit hyperdisks in $\mathbb R^{d+1}$, whose offline version was studied by Alt, Cabello, Cheong, Park, and Seiferth [Comp. Geom. 2026]. Our algorithm for online TSP scheduling builds on a recent breakthrough for online sorting by Azar, Panigrahi, and Vardi [SODA 2026]. We thus show that the connection between packing and online sorting can be used not only for lower bounds, but also for algorithms.
We present a new online algorithm for the well-known Multi-Level Aggregation Problem (MLAP) with arbitrary delay functions, achieving a $2D$-competitive ratio, where $D$ is the depth of the underlying tree. This result improves the current best-known competitive ratio of $O(D^2)$ and asymptotically matches the $D$-competitive bound previously known only for the deadline variant, thereby closing the asymptotic gap between the two settings. Our key technical contribution is a novel dual fitting framework that provides a unified analysis for both settings; in particular, it also establishes a $D$-competitive ratio for MLAP with deadlines. Our analysis is built upon two new ideas: a hindsight dual construction, which resolves the infeasibility issues in traditional online primal-dual methods, and a time-dependent dual packing that maintains feasibility over dynamic request sets.
We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.
