Overview

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

CardsList

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

  1. Beyond 4: Improved Competitive Traveling Repairperson

    Nov 16, 2026Bibek Maharjan, Gokarna SharmaVehicle RoutingCompetitive Analysis

  2. Optimal Competitive Ratios for Chasing Convex Functions with Quadratic Growth

    Nov 5, 2026Linzhe He, Sifan Yang, Wei Jiang +1Competitive AnalysisOnline Convex Optimization

  3. Leveraging Recourse and Size Bounds for OnlineKnapsack with Removable Items

    Oct 29, 2026Dimitris Fotakis, Laurent Gourvès, Aris Pagourtzis +1Combinatorial OptimizationOnline Resource Allocation

  4. 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 AnalysisOnline Convex Optimization

  5. HoopMind: A Real-Time Neural Game-Tree System for Opponent-Aware Possession Planning

    Aug 30, 2026Yibo Gong, Cong Guo, Jiacheng DingSports AnalyticsSequential Decision Making

  6. Online Algorithms via Minimax and Posterior Matching

    Aug 3, 2026Thomas Kesselheim, Marco Molinaro, Kalen Patton +1Competitive AnalysisOnline Resource Allocation

  7. Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays

    Jul 30, 2026Tianhang Lu, Runtian Ren, Shengcai Liu +1Competitive AnalysisLearning-Augmented Algorithms

  8. Learning-Augmented Algorithms for Online Vertex Cover

    Jun 22, 2026Tianhang Lu, Runtian Ren, Shengcai LiuCompetitive AnalysisCombinatorial Optimization

  9. Towards Optimal Robustness in Learning-Augmented Paging

    May 31, 2026Peng Chen, Hailiang Zhao, Xueyan Tang +2Competitive AnalysisLearning-Augmented Algorithms

  10. Online Packet Scheduling with Deadlines and Learning

    May 30, 2026Gianmarco Genalti, Achraf Azize, Vianney PerchetCompetitive AnalysisMulti-Armed Bandits

  11. 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 ControlCompetitive Analysis

  12. Results and Retrospective Analysis of the CODS 2025 AssetOpsBench Challenge

    May 8, 2026Dhaval Patel, Chathurangi Shyalika, Suryanarayana Reddy Yarrabothula +4Competitive AnalysisMulti-Agent Orchestration

  13. Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management

    Apr 29, 2026Wen-Han Hsieh, Ya-Chun LiangCompetitive AnalysisLearning-Augmented Algorithms

  14. Robust and Consistent Ski Rental with Distributional Advice

    Mar 31, 2026Jihwan Kim, Chenglin FanLearning-Augmented AlgorithmsCompetitive Analysis

  15. Competition-Aware CPC Forecasting with Near-Market Coverage

    Mar 13, 2026Sebastian Frey, Edoardo Beccari, Maximilian Kranz +4Competitive AnalysisOnline Advertising