Competitive Analysis

Follow this topic Ask about this topic

Competitive analysis studies how well an algorithm makes decisions as information arrives, often comparing its cost with that of a clairvoyant offline optimum. Researchers develop deterministic and randomized methods for problems such as paging, scheduling, search, routing, and resource allocation, using tools including adversarial analysis, minimax design, and primal-dual reasoning. Learning-augmented methods add predictions or partial feedback, with guarantees that balance performance when advice is accurate against protection when it is wrong. A central tension is how to improve practical performance without weakening worst-case guarantees, especially when predictions are noisy or the input distribution is unknown.

Latest papers

17 papers2 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Revisiting Smoothed Online Learning: Competitive Ratio, Dynamic Regret with Switching Cost, and Best of Both Worlds
Oct 17, 2026Lijun Zhang, Linzhe He, Wei Jiang +1Competitive Analysis Online Convex Optimization
State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing 210023, China · School of Artificial Intelligence, Nanjing University, Nanjing 210023, China · School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China +1
On the Cyclic Assumption of the Cow-Path Search Algorithm
Oct 7, 2026Yuan Ma, Yiqun Lisa YinCompetitive Analysis
MIT
Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise
Sep 12, 2026Xuan LiMulti-Armed Bandits Competitive Analysis
University of New South Wales, Sydney, Australia
HoopMind: A Real-Time Neural Game-Tree System for Opponent-Aware Possession Planning
Aug 30, 2026Yibo Gong, Cong Guo, Jiacheng DingSports Analytics Sequential Decision Making
University of Memphis Memphis, TN, USA
Online Algorithms via Minimax and Posterior Matching
Aug 3, 2026Thomas Kesselheim, Marco Molinaro, Kalen Patton +1Competitive Analysis Online Resource Allocation
Institute of Computer Science, University of Bonn. · Microsoft Research and PUC-Rio. · School of Mathematics, Georgia Tech. +1
Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays
Jul 30, 2026Tianhang Lu, Runtian Ren, Shengcai Liu +1Competitive Analysis Learning-Augmented Algorithms
Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China
Learning-Augmented Algorithms for Online Vertex Cover
Jun 22, 2026Tianhang Lu, Runtian Ren, Shengcai LiuCompetitive Analysis Combinatorial Optimization
Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China
Towards Optimal Robustness in Learning-Augmented Paging
May 31, 2026Peng Chen, Hailiang Zhao, Xueyan Tang +2Competitive Analysis Learning-Augmented Algorithms
Zhejiang University, Hangzhou, China · Nanyang Technological University, Singapore · Nanjing University of Aeronautics and Astronautics, Nanjing, China
Online Packet Scheduling with Deadlines and Learning
May 30, 2026Gianmarco Genalti, Achraf Azize, Vianney PerchetCompetitive Analysis Multi-Armed Bandits
Politecnico di Milano · FairPlay Joint Team, CREST, ENSAE, IP Paris · FairPlay Joint Team, CREST, ENSAE, IP Paris, CRITEO AI Team
Optimal and Order-optimal Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment
May 25, 2026Xi Chen, Yuze Chen, Ziyi Chen +1Inventory Control Competitive Analysis
Leonard N. Stern School of Business, New York University, New York, NY 10012, USA · Qiuzhen College, Tsinghua University, Beijing 100084, China · Yau Mathematical Sciences Center & Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China
Results and Retrospective Analysis of the CODS 2025 AssetOpsBench Challenge
May 8, 2026Dhaval Patel, Chathurangi Shyalika, Suryanarayana Reddy Yarrabothula +4Competitive Analysis Multi-Agent Orchestration
1IBM · 2Artificial Intelligence Institute at University of South Carolina · 3Steel Authority of India Limited +2
Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management
Apr 29, 2026Wen-Han Hsieh, Ya-Chun LiangCompetitive Analysis Learning-Augmented Algorithms
Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan
Optimal UGV-UAV Cooperative Partitioning and Inspection of Shortest Paths
Apr 28, 2026Ninh Nguyen, Srinivas AkellaCompetitive Analysis UAV Navigation
$k$ -server-bench: Automating Potential Discovery for the $k$ -Server Conjecture
Apr 8, 2026Kirill Brilliantov, Etienne Bamas, Emmanuel AbbéAI-Assisted Mathematical Discovery Autonomous Scientific Discovery
MDS Lab, EPFL
Robust and Consistent Ski Rental with Distributional Advice
Mar 31, 2026Jihwan Kim, Chenglin FanLearning-Augmented Algorithms Competitive Analysis
Seoul National University, Seoul 08826, South Korea.
Competition-Aware CPC Forecasting with Near-Market Coverage
Mar 13, 2026Sebastian Frey, Edoardo Beccari, Maximilian Kranz +4Competitive Analysis Online Advertising
*Nova School of Business and Economics, Portugal · †University of Hamburg, Germany
The AI Transformation Gap Index (AITG): An Empirical Framework for Measuring AI Transformation Opportunity, Disruption Risk, and Value Creation at the Industry and Firm Level
Feb 27, 2026Dean BarrCompetitive Analysis AI Risk Management
Applied AI Researcher

Oct 17, 2026J/K move · Enter open · S save

Revisiting Smoothed Online Learning: Competitive Ratio, Dynamic Regret with Switching Cost, and Best of Both Worlds

Lijun Zhang, Linzhe He, Wei Jiang, Shiyin Lu

State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing 210023, China · School of Artificial Intelligence, Nanjing University, Nanjing 210023, China · School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China+1

Competitive Analysis Online Convex Optimization Dynamic Regret Minimization

Open paper AskPDF arXiv

We revisit smoothed online learning and develop algorithms with improved competitive ratios, optimal dynamic regret with switching cost, and best-of-both-worlds guarantees. Surprisingly, minimizing the hitting cost alone is

\max(1,\frac{2}α)

-competitive for

α

-polyhedral functions under the

\ell_2

-norm switching cost and

1+\frac{4}λ

-competitive for

λ

-quadratic growth functions under the squared

\ell_2

-norm switching cost, significantly improving existing guarantees. The polyhedral bound is tight for this naive algorithm, and we establish a matching lower bound for

α\geq1

. For convex

λ

-quadratic growth hitting costs, minimizing a suitably weighted sum of hitting and squared

\ell_2

-norm switching costs yields a competitive ratio of

1+\frac{2}{\sqrtλ}

. For dynamic regret with the

\ell_2

-norm switching cost, we develop Smoothed Ader (SAder), which achieves the optimal

O(\sqrt{T(1+P_T)})

rate in the standard online convex optimization setting, where

P_T

is the comparator's path-length. Its lookahead version removes the bounded-gradient assumption, and a matching lower bound establishes optimality in this setting. Finally, for convex hitting costs on a bounded convex domain, we develop UDNP to aggregate any two experts in the lookahead setting under both switching costs. Its additional cumulative cost is at most

O(1)

relative to the first expert and

O(\sqrt{T\log T})

relative to the second, yielding best-of-both-worlds guarantees without bounded gradients.