Approximation Algorithms

Ask about this topic

Overview

Approximation algorithms study how to solve optimization problems efficiently when finding an exact optimum is computationally infeasible, while measuring how close the result is to the best possible solution. Common tools include greedy methods for set cover and submodular maximization, linear-programming relaxations with rounding for clustering and graph problems, and randomized, streaming, or coreset methods for large or changing inputs. Researchers also develop PTAS and FPTAS schemes for restricted settings and prove hardness bounds that show when stronger guarantees are unlikely, across problems such as fair clustering, facility location, scheduling, allocation, and robot motion planning. A central tension is balancing worst-case guarantees with practical speed, scalability, and constraints such as fairness, online decisions, or imperfect predictions.

Latest papers

CardsList

88 papers14 papers in the last four weeks, up 56% on the four weeks before. 0.1% of all new papers.

  1. Breaking the 1/3 Barrier for Approximate Nash Equilibria in Symmetric Bimatrix Games

    Oct 18, 2026Ashkan Soleymani, Patrick Jaillet, Gabriele FarinaGame TheoryNash Equilibrium Computation

    MIT

  2. When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?

    Oct 18, 2026Qixin Zhang, Shi Fu, Shengminjie Chen +2Greedy OptimizationSubmodular Optimization

    College of Computing and Data Science, Nanyang Technological University, Singapore · Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China

  3. Budgeted Bayesian Bandits for Future Utilization

    Oct 16, 2026Sudipto GuhaMarkovian BanditsMulti-Armed Bandits

  4. FPTAS for Polygonal Multi-Robot Motion Planning

    Oct 14, 2026Sayan Bandyapadhyay, William Lochet, Saket Saurabh +1Multi-Robot Motion PlanningMotion Planning

    Portland State University, OR, USA. · LIRMM, Universit´e de Montpellier, CNRS, Montpellier, France. · Institute of Mathematical Sciences, HBNI, Chennai and Homi Bhabha National Institute, Mumbai, India. +1

  5. Geometric Kernel Diversity: An Axiomatic Diversity Measure in Euclidean Space

    Oct 14, 2026Ditbul Ban, Younghun Roh, Julian Shun +1Approximation Algorithms

    MIT CSAIL

  6. Approximating Optimal Policies in Heterogeneous Asynchronous Multi-player Bandits

    Oct 13, 2026Sacha Arroues-Paykin, Etienne Boursier, Vianney PerchetMulti-Armed BanditsMulti-Agent Bandits

    Ecole Polytechnique · INRIA, LMO, Université Paris-Saclay · CREST, ENSAE

  7. Improving the Bounds on Approximating Weighted Maximin Share for Chores

    Oct 11, 2026Trung Thanh Nguyen, Khaled Elbassioni, Jörg RotheFair Resource AllocationApproximation Algorithms

    Faculty of Data Science and Artificial Intelligence, National Economics University, Hanoi 11616, Vietnam · Khalifa University of Science and Technology, Abu Dhabi 127788, UAE · Institut für Informatik, MNF, Heinrich-Heine-Universität Düsseldorf, 40225, Düsseldorf, Germany

  8. Minimizing Cumulative Envy in Allocating a Sequence of Items

    Oct 7, 2026Paul W. Goldberg, Isaac Robinson, Nicholas TehFair Resource AllocationApproximation Algorithms

    University of Oxford, UK

  9. Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations

    Oct 4, 2026Thi Ngoc Anh Vu, Trung Thanh Nguyen, Khaled Elbassioni +1Submodular OptimizationSocial Choice Theory

    Faculty of Computer Science, Phenikaa University, Hanoi 12116, Vietnam · DataOptLab, National Economics University, Hanoi 11616, Vietnam · Khalifa University of Science and Technology, Abu Dhabi 127788, UAE +1

  10. Maximizing pp-Mean Social Welfare in the High-Multiplicity Setting: Few Agent Types and Few Item Types

    Oct 3, 2026Trung Thanh Nguyen, Khaled ElbassioniSocial Welfare MaximizationFair Resource Allocation

    DataOptLab, National Economics University, Hanoi 11616, Vietnam · Khalifa University of Science and Technology, Abu Dhabi 127788, UAE

  11. Geometry-Dependent Approximation for Non-Monotone kk-Submodular Maximization

    Oct 2, 2026Vaneet AggarwalSubmodular OptimizationApproximation Algorithms

    Purdue University

  12. Streaming algorithms for robust max-min diversification

    Oct 1, 2026Andrea Pietracaprina, Geppino Pucci, Stefano ZanonCoreset SelectionApproximation Algorithms

    Department of Information Engineering, University of Padova, Italy

  13. Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon

    Sep 30, 2026Johannes F. Loevenich, Thies Moehlenhof, Laurin Holz +3Graph Neural NetworksApproximation Algorithms

    cortAIx Labs, Thales Deutschland, Ditzingen, Germany · Department of Mathematics/Computer Science, University of Osnabrück, Osnabrück, Germany

  14. Reverse Sequential Proportional Approval Voting Rule: Proportionality and Approximation Guarantees

    Sep 28, 2026Georgios PapasotiropoulosSocial Choice TheoryApproximation Algorithms

    University of Warsaw

  15. Contingent Exposure Routing for Financial AI: Outage Risk and the Cost of Indivisible Decisions

    Sep 23, 2026Shivam GuptaAdaptive Model RoutingFinance

    Independent Researcher

  16. Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids

    Sep 21, 2026Shi Fu, Youming Qiao, Dacheng Tao +2Submodular OptimizationCombinatorial Optimization

    College of Computing and Data Science, Nanyang Technological University, Singapore · Centre for Quantum Software and Information, University of Technology Sydney, Australia · School of Computing and Information Technology, Great Bay University, China

  17. A Horizon-slicing Approach to Minimum Obstacle Displacement Planning for Robot Navigation

    Sep 19, 2026Antony Thomas, Giulio Ferro, Fulvio Mastrogiovanni +2Motion PlanningRobot Motion Planning

    Robotics Research Center, IIIT Hyderabad, Hyderabad 500032, India. · Department of Informatics, Bioengineering, Robotics, and Systems Engineering, University of Genoa, Via All’Opera Pia 13, 16145 Genoa, Italy.

  18. Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering

    Sep 14, 2026Lars Rohwedder, Rico ZenklusenSubmodular OptimizationMarkov Decision Processes

    University of Southern Denmark, Odense, Denmark · ETH Zurich, Zurich, Switzerland

  19. Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead

    Sep 10, 2026Corentin Pla, Hugo Richard, Marc Abeille +1Reinforcement LearningApproximation Algorithms

    CREST, ENSAE · Criteo AI Lab FairPlay Joint Team

  20. A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over 2−22-\sqrt{2} Entails Exponential Queries or Linear Recourse

    Sep 9, 2026Shi Fu, Qixin Zhang, Dacheng TaoSubmodular OptimizationQuery Complexity

    Nanyang Technological University, Singapore

  21. A Tight 3-Approximation for Fair kk-Means

    Sep 7, 2026Kangke Cheng, Guanlin Mo, Shihong Song +1ClusteringGroup Fairness

    University of Science and Technology of China, Hefei, China · School of Informatics, University of Edinburgh, Edinburgh, UK

  22. Parameterized and Streaming Algorithms for Euclidean Fair kk-Center Clustering

    Sep 6, 2026Zeyu Lin, Chaoqi Jia, Longkun Guo +1ClusteringApproximation Algorithms

    School of Mathematics and Statistics, Fuzhou University, Fuzhou 350116, China · School of Accounting, Information Systems and Supply Chain, RMIT University, VIC 3000, Australia

  23. Variable Selection for Feature-Based Newsvendor

    Sep 1, 2026Zhaoliang Yuan, Jie WangInventory ControlConstrained Optimization

    School of Artificial Intelligence, The Chinese University of Hong Kong, Shenzhen · School of Artificial Intelligence and School of Data Science, The Chinese University of Hong Kong, Shenzhen

  24. Improving Randomized Metric Distortion to 2.1441

    Aug 29, 2026Nisarg ShahSocial Choice TheoryApproximation Algorithms

    University of Toronto

  25. Correlation Clustering with Random Partial Information

    Aug 17, 2026Rajath Rao K. N., Jens Schlöter, Sami Davies +2ClusteringGraph Clustering

    Vrije Universiteit Amsterdam, The Netherlands · CWI Amsterdam, The Netherlands · Department of EECS, UC Berkeley

  26. Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learning

    Aug 12, 2026Vaneet AggarwalSubmodular OptimizationCombinatorial Multi-Armed Bandits

    V. Aggarwal is with Purdue University, West Lafayette IN, USA

  27. Sub-Quadratic Bisimulation Metrics via Approximate Nearest Neighbors: Coverage-Augmented Guarantees and Computable Two-Sided Certificates

    Aug 7, 2026Ibne Farabi Shihab, Joyanta Jyoti MondalMarkov Decision ProcessesApproximation Algorithms

    Department of Computer Science, Iowa State University, USA · Department of Computer and Information Sciences, University of Delaware, USA

  28. The Condition-Number Barrier in Sparse Least Squares

    Aug 3, 2026Honghao Lin, Vahab Mirrokni, David P. WoodruffRecursive Least SquaresSparse Recovery

    Google Research, Carnegie Mellon University / Texas A&M University. · Google Research. · Google Research and Carnegie Mellon University.

  29. Randomizing the Number of Centers in k-means++

    Jul 28, 2026Vaclav RozhonClusteringApproximation Algorithms

  30. Online Fair Division with Budget Constraints

    Jul 25, 2026Saar Cohen, Nicholas Teh, Paul W. Goldberg +1Fair Resource AllocationLearning-Augmented Algorithms

    Department of Computer Science, University of Oxford, UK