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. TRAM: Training Approximate Multiplier Structures for Low-Power AI Accelerators

    May 6, 2026Chang Meng, Hanyu Wang, Yuyang Ye +3AI Accelerator InferenceEnergy-Efficient ML

    Eindhoven University of Technology Eindhoven, The Netherlands · University of California, Los Angeles Los Angeles, USA · Chinese University of Hong Kong Hong Kong, China +2

  2. On Computing Total Variation Distance Between Mixtures of Product Distributions

    May 5, 2026Weiming Feng, Yucheng Fu, Minji Yang +1Distribution MatchingApproximation Algorithms

    School of Computing and Data Science, The University of Hong Kong. · The Institute for Interdisciplinary Information Sciences, Tsinghua University.

  3. Exact and Approximate Algorithms for Polytree Learning

    May 5, 2026Juha Harviainen, Frank Sommer, Manuel SorgeGraph Structure LearningBayesian Networks

    Department of Computer Science, University of Helsinki, Helsinki, Finland · Institute of Computer Science, Friedrich-Schiller Universität Jena, Jena, Germany · Institute of Logic and Computation, TU Wien, Vienna, Austria

  4. Matroid Algorithms Under Size-Sensitive Independence Oracles

    Apr 30, 2026Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz +1Query ComplexityOracle Complexity

    *Equal contribution 1Department of Computer Science, University of Maryland, College Park, USA.

  5. Nearly Optimal Subdata Selection

    Apr 27, 2026Min Yang, Wei Zheng, John Stufken +3Data SelectionTraining Data Selection

    Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago · Department of Business Analytics and Statistics, University of Tennessee · Department of Statistics, George Mason University[stat.ME] +3

  6. Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means

    Apr 17, 2026Nicole Funk, Annika Hennes, Johanna Hillebrand +1ClusteringGroup Fairness

    Department of Informatics, University of Cologne, Germany · Heinrich Heine University Düsseldorf, Faculty of Mathematics and Natural Sciences, Germany · Department of Informatics, University of Bonn, Germany

  7. Why Colors Make Clustering Harder:Global Integrality Gaps, the Price of Fairness, and Color-Coupled Algorithms in Chromatic Correlation Clustering

    Apr 17, 2026Ibne Farabi Shihab, Sanjeda Akter, Anuj SharmaClusteringApproximation Algorithms

    Department of Computer Science, Iowa State University · Department of Civil, Construction & Environmental Engineering, Iowa State University

  8. A Residual-Shell-Based Lower Bound for Ollivier-Ricci Curvature

    Apr 14, 2026Xiang Gu, Huichun Zhang, Jian SunOllivier-Ricci CurvatureApproximation Algorithms

    School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, 710049, Shaanxi, China · School of Mathematics, Sun Yat-sen University, Guangzhou, 510275, Guangdong, China

  9. Simpler Logarithmic Approximation Algorithms for the Optimal Decision Tree and Adaptive Set Cover

    Apr 13, 2026Michał SzyfelbeinApproximation AlgorithmsCombinatorial Optimization

  10. A Ray Intersection Algorithm for Fast Growth Distance Computation Between Convex Sets

    Apr 11, 2026Akshay Thirugnanam, Koushil SreenathApproximation Algorithms

    Department of Mechanical Engineering, UC Berkeley, CA 94720, USA.

  11. Adalina: Adaptive Linear Approximation for the Shapley Value and Beyond

    Apr 9, 2026Weida Li, Yaoliang Yu, Bryan Kian Hsiang LowShapley Value AttributionApproximation Algorithms

    Department of Computer Science, National University of Singapore, Republic of Singapore · School of Computer Science, University of Waterloo, Canada · Vector Institute, Canada

  12. Adaptive Threshold-Driven Continuous Greedy Method for Scalable Submodular Optimization

    Apr 3, 2026Mohammadreza Rostami, Solmaz S. KiaSubmodular OptimizationApproximation Algorithms

    Department of Mechanical and Aerospace Engineering, University of California Irvine, Irvine, CA 92697

  13. Approximating Pareto Frontiers in Stochastic Multi-Objective Optimization via Hashing and Randomization

    Apr 1, 2026Jinzhao Li, Nan Jiang, Yexiang XueMulti-Objective OptimizationPareto Optimization

    Department of Computer Science, Purdue University, 610 Purdue Mall, West Lafayette, 47907, IN, United States. · Department of Computer Science, University of Texas at El Paso, 500 W University Ave, El Paso, 79968, TX, United States.

  14. Multi-LLM Query Optimization

    Mar 24, 2026Arlen Dean, Zijin Zhang, Stefanus Jasin +1Multi-LLM CollaborationApproximation Algorithms

    Washington University in St. Louis, Olin Business School · Boston College, Carroll School of Management · University of Michigan, Stephen M. Ross School of Business +1

  15. Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs

    Mar 19, 2026Tsuri Farhana, Omrit Filtser, Shalev GoldshteinMulti-Robot Motion PlanningApproximation Algorithms

    Department of Computer Science, Ben Gurion University, Beer Sheva, Israel. · Department of Mathematics and Computer Science, The Open University of Israel, Ra’anana, Israel

  16. Can LLMs Prove Robotic Path Planning Optimality? A Benchmark for Research-Level Algorithm Verification

    Mar 19, 2026Zhengbang Yang, Md. Tasin Tazwar, Minghan Wei +1Mathematical Reasoning BenchmarksAutomated Theorem Proving

    George Mason University · Florida Atlantic University

  17. A New Lower Bound for the Random Offerer Mechanism in Bilateral Trade using AI-Guided Evolutionary Search

    Mar 9, 2026Yang Cai, Vineet Gupta, Zun Li +1Mechanism DesignApproximation Algorithms

    Yale University

  18. Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion

    Feb 27, 2026Nate Veldt, Thomas Stanley, Benjamin W. Priest +5Learning-Augmented AlgorithmsApproximation Algorithms

    Texas A&M University · Lawrence Livermore National Laboratory

  19. Precedence-Constrained Decision Trees and Coverings

    Feb 24, 2026Michał Szyfelbein, Dariusz DereniowskiCombinatorial OptimizationConstrained Optimization

    Gdańsk University of Technology, 80-233 Gdańsk, Poland

  20. On the Hardness of Approximation of the Fair k-Center Problem

    Feb 18, 2026Suhas ThejaswiApproximation AlgorithmsClustering

    Department of Computer Science, Aalto University, Finland

  21. Learning to Approximate Uniform Facility Location via Graph Neural Networks

    Feb 13, 2026Chendi Qian, Christopher Morris, Stefanie Jegelka +1Graph Neural NetworksCombinatorial Optimization

    RWTH Aachen University, Germany · Technical University of Munich, Germany · Massachusetts Institute of Technology, USA +1

  22. Incremental (k, z)-Clustering on Graphs

    Feb 9, 2026Emilio Cruciani, Sebastian Forster, Antonis SkarlatosClusteringGraph Clustering

    European University of Rome, Italy. · Department of Computer Science, University of Salzburg, Salzburg, Austria. · Department of Computer Science, University of Warwick, Coventry, England.

  23. Exact and Approximate Range Queries in Ball Mapper

    Jan 4, 2026Jay-Anne Bulauan, John Rick ManzanaresApproximation AlgorithmsTopological Data Analysis

    Independent Researcher · Dioscuri Centre in Topological Data Analysis, Institute of Mathematics of the Polish Academy of Sciences International Environmental Doctoral School of the University of Silesia in Katowice

  24. Fair Minimum Labeling: Efficient Temporal Network Activations for Reachability and Equity

    Oct 4, 2025Lutz Oettershagen, Othon MichailFair Resource AllocationCombinatorial Optimization

    University of Liverpool

  25. Faster and Simpler Greedy Algorithm for kk-Median and kk-Means

    Jul 15, 2024Max Dupré la Tour, David SaulpicClusteringApproximation Algorithms

  26. Measuring Model-Induced Discrimination via Efficient Fairness Approximation

    May 15, 2024Yijun Bian, Yujie LuoAlgorithmic FairnessGroup Fairness

    Department of Computer Science, University of Copenhagen, 2100 Copenhagen, Denmark · Department of Mathematics, National University of Singapore, Singapore 117543, Singapore

  27. Supermodular Rank: Set Function Decomposition and Optimization

    May 24, 2023Rishi Sonthalia, Anna Seigal, Guido MontufarSubmodular OptimizationApproximation Algorithms

    UCLA · Harvard University · UCLA and MPI MiS

  28. Proportionally Representative Clustering

    Apr 27, 2023Haris Aziz, Barton E. Lee, Sean Morota Chu +1ClusteringAlgorithmic Fairness

    UNSW Sydney · ETH Zürich · Northwestern University