Approximation Algorithms

Follow this topic Ask about this topic

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

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

When Is Heterogeneous Distance-Decay Facility Location Tractable? A Structural Classification, Exact Methods, and a Real-World Study
Jul 18, 2026Zhou He, T. C. E. Cheng, Jichang DongMetaheuristic Optimization Combinatorial Optimization
School of Economics and Management, University of Chinese Academy of Sciences, N606-3, #3 Zhongguancun Nanyitiao, Haidian District, Beijing 100190, China · Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, 11 Yuk Choi Rd, Hung Hom, Hong Kong, China
CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees
Jul 16, 2026Haifeng Li, Mo HaiCombinatorial Optimization Learning-Augmented Algorithms
School of Information, Central University of Finance and Economics Beijing 102206, China
Graph Partitioning with Demands: Generalized Conductance and its Applications
Jul 14, 2026Michał Szyfelbein, Dariusz DereniowskiHierarchical Clustering Approximation Algorithms
Gdańsk University of Technology
Hierarchical $\mathcal{F}$ -Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs
Jul 14, 2026Michał Szyfelbein, Dariusz DereniowskiHierarchical Clustering Graph Clustering
Gda´nsk University of Technology
Exact and Certified Data Shapley for Weighted k-Nearest-Neighbor Regression and Soft-Label Prediction
Jul 12, 2026Zongye LyuShapley Value Attribution k-Nearest Neighbors
Faculty of Information Technology, Monash University, Melbourne, VIC 3800, Australia
The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression
Jul 7, 2026Stephen MussmannActive Learning Linear Regression
School of Computer Science Georgia Institute of Technology
Data-dependent Evaluations for Budgeted Submodular Maximization
Jul 7, 2026Lejian Zhang, Xueyan Tang, Jing TangSubmodular Optimization Approximation Algorithms
College of Computing and Data Science, Nanyang Technological University, Singapore · Data Science and Analytics Thrust, The Hong Kong University of Science and Technology (Guangzhou), China
TSP with Predictions: Heatmap to Tour with Provable Guarantees
Jul 4, 2026Marek Eliáš, Fabrizio Grandoni, Adam Polak +1Traveling Salesperson Problem Combinatorial Optimization
Three-Objective Integral R2 Subset Selection: NP-Hardness and Submodular Approximation
Jun 25, 2026Michael T. M. EmmerichSubmodular Optimization Approximation Algorithms
Simultaneously Efficient Allocation of Indivisible Items Across Multiple Dimensions
Jun 19, 2026Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin SanpuiCombinatorial Optimization Approximation Algorithms
Chuo University, Tokyo, Japan · Indian Institute of Technology Kharagpur, Kharagpur, India
PolyMerge: Compressing 3D Gaussian Splats with Polytope Coverings for Provably Safe Resource-Constrained Navigation
Jun 15, 2026Jihoon Hong, Chih-Yuan Chiu, Sara Fridovich-Keil +13DGS Compression Constrained Motion Planning
1Georgia Institute of Technology.
Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling
Jun 11, 2026Kaito Baba, Evripidis Bampis, Giorgos MitropoulosCombinatorial Optimization Learning-Augmented Algorithms
The University of Tokyo, Tokyo, Japan · Sorbonne Université, CNRS, LIP6, F-75005 Paris, France
Multi-Objective Coevolution of Prompts and Templates for Circuit Approximation
Jun 11, 2026Martin Tomasovic, Lukas SekaninaMulti-Objective Evolutionary Optimization Large Language Model-Guided Optimization
Brno University of Technology, Faculty of Information Technology Brno, Czech Republic
A General Framework for Dynamic Consistent Submodular Maximization
Jun 3, 2026Paul Dütting, Federico Fusco, Silvio Lattanzi +3Submodular Optimization Approximation Algorithms
1Google Research · 2Dept. of Computer, Control and Management Engineering, Sapienza University of Rome · 3EPFL
Prediction Under Imperfect Compression: A Theory of Approximate MDL
Jun 3, 2026Qian Li, Xinyu Mao, Shang-Hua Teng +1Minimum Description Length Approximation Algorithms
Shenzhen Research Institute of Big Data · University of Southern California
Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications
May 24, 2026Samuel B. Hopkins, Stefan TiegelRobust Regression Robust Mean Estimation
MIT
Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
May 19, 2026Peter Matthew Jacobs, Jeff M. PhillipsRandomized Sketching Approximation Algorithms
Department of Statistics University of Wisconsin-Madison Madison, WI 53706 · Kahlert School of Computing University of Utah Salt Lake City, UT 84101
Nash Welfare in Additively Separable Hedonic Games
May 18, 2026Marta Pagano, Alexander SchlengaCooperative Game Theory Game Theory
Sapienza University of Rome, Italy · Technical University of Munich, Germany
An Approximation Algorithm for Graph Label Selection
May 18, 2026Josia John, Simon Meierhans, Maximilian Probst GutenbergSemi-Supervised Learning Approximation Algorithms
Department of Computer Science, ETH Zurich, Zurich, Switzerland.
Optimizing Line Segment Inspection with Limited-Range Drones
May 15, 2026José-Miguel Díaz-Báñez, José-Manuel Higes, Alina Kasiuk +1Aerial Robotics Combinatorial Optimization
Department of Applied Mathematics, University of Seville, Spain
Stochastic Matching via Local Sparsification
May 13, 2026Sara Ahmadian, Edith Cohen, Mohammad RoghaniApproximation Algorithms
Google Research · Tel Aviv University
Decision Tree Learning on Product Spaces
May 13, 2026Arshia Soltani Moakhar, Faraz Ghahremani, Kiarash Banihashem +1Decision Tree Learning Approximation Algorithms
Department of Computer Science, University of Maryland, College Park, USA.
Time and Supply Fairness in Electricity Distribution using $k$ -times bin packing
May 12, 2026Dinesh Kumar Baghel, Alex Ravsky, Erel Segal-HaleviFair Resource Allocation Combinatorial Optimization
Ariel University, Ariel 40700, Israel · UPES, Dehradun, Uttarakhand, India · Pidstryhach Institute for Applied Problems of Mechanics and Mathematics of National Academy of Sciences of Ukraine, Lviv, Ukraine
On the Approximation Complexity of Matrix Product Operator (MPO) Born Machines
May 12, 2026Chao Li, Zerui Tao, Yuchen Cong +2Tensor Networks Approximation Algorithms
RIKEN-AIP · Jutentedo University
Network-Based Interventions for HIV Prevention via Cascade-Aware Suppression of Transmission
May 11, 2026Akseli Kangaslahti, Davin Choo, Milind Tambe +2Healthcare Combinatorial Optimization
Harvard University · University of Witwatersrand · Wits Health Consortium +1
A Reconfigurable Multiplier Architecture for Error-Resilient Applications in RISC-V Core
May 9, 2026Pragun Jaswal, L. Hemanth Krishna, B. SrinivasuEfficient Neural Network Inference Energy-Efficient ML
Indian Institute of Technology Mandi, Mandi–175005, India
Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
May 8, 2026Yixin Chen, Alan KuhnleSubmodular Optimization Approximation Algorithms
Department of Computer Science & Engineering, Texas A&M University
Online Allocation with Unknown Shared Supply
May 8, 2026Tzeh Yuan Neoh, Davin Choo, Mengchu Yue +1Online Resource Allocation Sequential Decision Making
Harvard University
Accelerated Relax-and-Round for Concave Coverage Problems
May 7, 2026Matthew Fahrbach, Mehraneh Liaee, Morteza ZadimoghaddamSubmodular Optimization Approximation Algorithms
Google Research
Convex-Geometric Error Bounds for Positive-Weight Kernel Quadrature
May 7, 2026Satoshi HayakawaConstrained Optimization Kernel Methods
The University of Tokyo

Jul 18, 2026J/K move · Enter open · S save

When Is Heterogeneous Distance-Decay Facility Location Tractable? A Structural Classification, Exact Methods, and a Real-World Study

Zhou He, T. C. E. Cheng, Jichang Dong

School of Economics and Management, University of Chinese Academy of Sciences, N606-3, #3 Zhongguancun Nanyitiao, Haidian District, Beijing 100190, China · Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, 11 Yuk Choi Rd, Hung Hom, Hong Kong, China

Metaheuristic Optimization Combinatorial Optimization Approximation Algorithms Large Neighborhood Search

Open paper AskPDF arXiv

We study continuous planar facility location in which a demand point's captured value decays with distance, with the per-point decay scale varying across points. This heterogeneity is ubiquitous yet underexploited, and one nearest-facility objective unifies decay, clustering, and median goals, containing k-means, the Weber/p-median problem, and maximum covering as special cases. We make four contributions. (i) A tractability classification: the discrete objective is always monotone submodular, so the (1-1/e) greedy guarantee holds regardless of decay shape or heterogeneity, and the continuous cooperative objective is concave if and only if the decay is concave in distance; the clip max(0,d) in common coverage specifications is what destroys concavity, and the classification is tight. (ii) An exact discrete method: the candidate-discretized maximum-cover MIP has an empirically tight LP relaxation (~0% gap) and is solved by branch-and-bound in seconds for n <= 500. (iii) A force-as-gradient / large-neighborhood-search heuristic, within 0.5% of the discrete optimum, that outperforms the (1-1/e) greedy, Cooper-style alternating location-allocation, particle swarm optimization, and weighted k-means (30/30 per-instance wins at K=30, p<10^-9) and is competitive with bespoke solvers on k-means, Weber/p-median, and shape-demand instances. (iv) A real-world study: on 592,667 urban-delivery orders, ignoring the calibrated decay variation loses up to 9.7% of captured demand and relocates facilities by up to 37% of the map; a retail dataset calibrates the decay as exponential with scale R ~ 1.4 km.