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

102 papers13 papers in the last four weeks, down 19% on the four weeks before. 0.1% of all new papers.

Feb 27, 2026

Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion

We present improved learning-augmented algorithms for finding an approximate minimum spanning tree (MST) for points in an arbitrary metric space. Our work follows a recent framework called metric forest completion (MFC), where the learned input is a forest that must be given additional edges to form a full spanning tree. Veldt et al. (2025) showed that optimally completing the forest takes Ω(n2)Ω(n^2) time, but designed a 2.62-approximation for MFC with subquadratic complexity. The same method is a (2γ+1)(2γ+ 1)-approximation for the original MST problem, where γ≥1γ\geq 1 is a quality parameter for the initial forest. We introduce a generalized method that interpolates between this prior algorithm and an optimal Ω(n2)Ω(n^2)-time MFC algorithm. Our approach considers only edges incident to a growing number of strategically chosen ``representative'' points. One corollary of our analysis is to improve the approximation factor of the previous algorithm from 2.62 for MFC and (2γ+1)(2γ+1) for metric MST to 2 and 2γ2γ respectively. We prove this is tight for worst-case instances, but we still obtain better instance-specific approximations using our generalized method. We complement our theoretical results with a thorough experimental evaluation.
Feb 24, 2026

Precedence-Constrained Decision Trees and Coverings

This work considers a number of optimization problems and reductive relations between them. The two main problems we are interested in are the Optimal Decision Tree and Set Cover. We study these two fundamental tasks under precedence constraints, that is, if a test (or set) XX is a predecessor of YY, then in any feasible decision tree XX needs to be an ancestor of YY (or respectively, if YY is added to set cover, then so must be XX). For the Optimal Decision Tree we consider two optimization criteria: worst case identification time (height of the tree) or the average identification time. Similarly, for the Set Cover we study two cost measures: the size of the cover or the average cover time. Our approach is to develop a number of algorithmic reductions, where an approximation algorithm for one problem provides an approximation for another via a black-box usage of a procedure for the former. En route we introduce other optimization problems either to complete the `reduction landscape' or because they hold the essence of combinatorial structure of our problems. The latter is brought by a problem of finding a Maximum Density Precedence-Closed Subfamily, where the density is defined as the ratio of the number of items the family covers to its size. We provide O∗(m)\mathcal{O}^*(\sqrt{m})-approximation polynomial-time algorithms for all aforementioned problems. The picture is complemented by a number of hardness reductions that provide O(m1/12−ε)\mathcal{O}(m^{1/12-ε})-inapproximability results for the decision tree and covering problems. Besides giving a complete set of results for general precedence constraints, we also provide polylogarithmic approximation guarantees for two most typically studied and applicable graph types, outforests and inforests. By providing corresponding hardness results, we show most of these results to be tight.
Feb 18, 2026

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

In this work, we study the hardness of approximation of the fair kk-center problem. In this problem, we are given a set of data points in a metric space that is partitioned into groups and the task is to choose a subset of kk-data points, called centers, such that a prescribed number of data points from each group are chosen while minimizing the maximum distance from any point to its closest center. Although a polynomial-time 33-approximation is known for fair kk-center in general metrics, it has remained open whether this approximation guarantee is tight or could be further improved, especially since the classical unconstrained kk-center problem admits a polynomial-time factor-22 approximation. We resolve this open question by proving that, assuming P≠NP\mathsf{P} \neq \mathsf{NP}, for any ε>0ε>0, no polynomial-time algorithm can approximate fair kk-center to (3−ε)(3-ε)-factor. Our inapproximability results hold even when only two disjoint groups are present and at least one center must be chosen from each group. Further, it extends to the canonical one-per-group setting with kk-groups (for arbitrary kk), where exactly one center must be selected from each group. Consequently, the factor-33 barrier for fair kk-center in general metric spaces is inherent, and existing 33-approximation algorithms are optimal up to lower-order terms even in these restricted regimes. This result stands in sharp contrast to the kk-supplier formulation, where both the unconstrained and fair variants admit factor-33 approximation in polynomial time.
Feb 13, 2026

Learning to Approximate Uniform Facility Location via Graph Neural Networks

Neural networks, particularly message-passing neural networks (MPNNs), are increasingly used as heuristics for hard combinatorial optimization problems. Yet many learning-based methods rely on supervision, reinforcement learning, or gradient estimators, causing high computational cost, unstable training, or limited guarantees. Classical approximation algorithms provide worst-case guarantees but are non-differentiable and cannot adapt to structure in natural input distributions. We study this tradeoff through Uniform Facility Location (UniFL), a problem with applications in clustering, summarization, logistics, and supply chains. We propose a fully differentiable MPNN that incorporates approximation-algorithmic principles without solver supervision or discrete relaxations. The model has provable approximation guarantees and empirically improves on standard approximation algorithms, narrowing the gap to integer linear programming.
Feb 9, 2026

Incremental (k, z)-Clustering on Graphs

Given a weighted undirected graph, a number of clusters kk, and an exponent zz, the goal in the (k,z)(k, z)-clustering problem on graphs is to select kk vertices as centers that minimize the sum of the distances raised to the power zz of each vertex to its closest center. In the dynamic setting, the graph is subject to adversarial edge updates, and the goal is to maintain explicitly an exact (k,z)(k, z)-clustering solution in the induced shortest-path metric. While efficient dynamic kk-center approximation algorithms on graphs exist [Cruciani et al. SODA 2024], to the best of our knowledge, no prior work provides similar results for the dynamic (k,z)(k,z)-clustering problem. As the main result of this paper, we develop a randomized incremental (k,z)(k, z)-clustering algorithm that maintains with high probability a constant-factor approximation in a graph undergoing edge insertions with a total update time of O~(km1+o(1)+k1+1λm)\tilde O(k m^{1+o(1)}+ k^{1+\frac{1}λ} m), where λ≥1λ\geq 1 is an arbitrary fixed constant. Our incremental algorithm consists of two stages. In the first stage, we maintain a constant-factor bicriteria approximate solution of size O~(k)\tilde{O}(k) with a total update time of m1+o(1)m^{1+o(1)} over all adversarial edge insertions. This first stage is an intricate adaptation of the bicriteria approximation algorithm by Mettu and Plaxton [Machine Learning 2004] to incremental graphs. One of our key technical results is that the radii in their algorithm can be assumed to be non-decreasing while the approximation ratio remains constant, a property that may be of independent interest. In the second stage, we maintain a constant-factor approximate (k,z)(k,z)-clustering solution on a dynamic weighted instance induced by the bicriteria approximate solution. For this subproblem, we employ a dynamic spanner algorithm together with a static (k,z)(k,z)-clustering algorithm.
Jan 4, 2026

Exact and Approximate Range Queries in Ball Mapper

Ball Mapper summarizes a finite metric dataset by covering the sample with closed balls centered at selected landmarks and connecting landmarks whose balls share observations. Its construction therefore depends critically on repeated fixed radius range queries, yet the effect of replacing exact queries by approximate search has not been systematically characterized. We formulate Ball Mapper through an abstract range query procedure that separates the mathematical construction from the search backend used to realize it. Under fixed ordering, exact procedures preserve the landmark sequence, cover, graph, and membership-based colorings. For approximate procedures, we derive deterministic bounds on covering radius and landmark separation under additive and multiplicative query errors, prove inclusions for the induced nerve, characterize edge survival through witness redundancy for conservative approximations, and bound perturbations of mean vertex colorings. The accompanying implementation provides independent exact reference backends together with exhaustive and approximate search methods under a common closed ball convention. Experiments on Gaussian, mixture, and noisy curve data across three seeds show that approximation fidelity depends strongly on geometry and that edges supported by multiple witnesses are substantially more robust to missed memberships. At 20,000 observations, the approximate indexes did not outperform exhaustive FAISS Flat search. The results therefore establish a framework for controlled approximation rather than a universal speed advantage, and identify the geometric and combinatorial quantities that govern when approximate range search preserves the Ball Mapper summary.
Oct 4, 2025

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

Balancing resource efficiency and fairness is critical in networked systems that support modern learning applications. We introduce the Fair Minimum Labeling (FML) problem: the task of designing a minimum-cost temporal edge activation plan that ensures each group of nodes in a network has sufficient access to a designated target set, according to specified coverage requirements. FML captures key trade-offs in systems where edge activations incur resource costs and equitable access is essential, such as distributed data collection, update dissemination in edge-cloud systems, and fair service restoration in critical infrastructure. We first give a structural characterisation of the single-terminal case, showing that it is equivalent to the rooted Covering Steiner problem. We prove that FML is NP-hard and admits no ((1−ε)ln⁡∣C∣)((1-ε)\ln |\mathcal{C}|)-approximation for ∣C∣|\mathcal{C}| groups, already on a star, while for any fixed number of groups it inherits a constant-factor approximation and remains APX-hard. We then present probabilistic approximation algorithms for the two-group, single-terminal case: an algorithm whose tree subroutine is exact, hence optimal on tree-structured networks and O(log⁡∣V∣)\mathcal{O}(\log |V|) in expectation on general graphs, together with a faster bicriteria variant whose coverage violation degrades gracefully with the merge depth of the tree computation. For practical scalability, we additionally introduce a graph-native variant based on a shortest-path-tree reduction. Empirical results show that FML enforces group-level fairness, while the graph-native variant substantially improves scalability and achieves competitive activation cost.
Nov 13, 2024

Theoretical Analysis of Byte-Pair Encoding

Byte-Pair Encoding (BPE) is a widely used method for subword tokenization, with origins in grammar-based text compression. It is employed in a variety of language processing tasks such as machine translation or large language model (LLM) pretraining, to create a token dictionary of a prescribed size. Most evaluations of BPE to date are empirical, and the reasons for its good practical performance are not well understood. In this paper we focus on the optimization problem underlying BPE: finding a pair encoding that achieves optimal compression utility. We show that this problem is APX-complete, indicating that it is unlikely to admit a polynomial-time approximation scheme. This answers, in a stronger form, a question recently raised by Zouhar et al. On the positive side, we show that BPE approximates the compression utility of the optimal pair encoding to a worst-case factor between 1/31/3 and (1−e−2)/2≈0.4324(1-e^{-2})/2 \approx 0.4324. Our results aim to explain the ongoing success of BPE and are, to our knowledge, the first rigorous guarantees on its compression utility that hold for all inputs.
Jul 15, 2024

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

Clustering problems such as kk-means and kk-median are staples of unsupervised learning, and many algorithmic techniques have been developed to tackle their numerous aspects. In this paper, we focus on the class of greedy approximation algorithm, that attracted less attention than local-search or primal-dual counterparts. In particular, we study the recursive greedy algorithm developed by Mettu and Plaxton [SIAM J. Comp 2003]. We provide a simplification of the algorithm, allowing for faster implementation, in graph metrics or in Euclidean space, where our algorithm matches or improves the state-of-the-art.
May 15, 2024

Measuring Model-Induced Discrimination via Efficient Fairness Approximation

Providing various machine learning (ML) applications in the real world, concerns about discrimination hidden in ML models are growing, particularly in high-stakes domains. Existing techniques for assessing the discrimination level of ML models include commonly used group and individual fairness measures. However, these two types of fairness measures are usually hard to be compatible, and even two different group fairness measures might be incompatible as well. To address this issue, we investigate and evaluate the discrimination level of classifiers from a manifold perspective and propose a fairness measure named harmonic fairness via manifolds (HFM)'' based on distances between sets. Yet the direct calculation of distances might be too expensive to afford, reducing its practical applicability. Therefore, we devise an approximation algorithm named Approximation of distance between sets (ApproxDist)'' to facilitate accurate estimation of distances, and we further demonstrate its algorithmic effectiveness under certain reasonable assumptions. Empirical results indicate that the proposed fairness measure HFM reflects bias from both individual and group fairness aspects and that the proposed ApproxDist is effective and efficient.
May 24, 2023

Supermodular Rank: Set Function Decomposition and Optimization

We define the supermodular rank of a function on a lattice. This is the smallest number of terms needed to decompose it into a sum of supermodular functions. The supermodular summands are defined with respect to different partial orders. We characterize the maximum possible value of the supermodular rank and describe the functions with fixed supermodular rank. We analogously define the submodular rank. We use submodular decompositions to optimize set functions. Given a bound on the submodular rank of a set function, we formulate an algorithm that splits an optimization problem into submodular subproblems. We show that this method improves the approximation ratio guarantees of several algorithms for monotone set function maximization and ratio of set functions minimization, at a computation overhead that depends on the submodular rank.
Apr 27, 2023

Proportionally Representative Clustering

In recent years, there has been a surge in effort to formalize notions of fairness in machine learning. We focus on centroid clustering--one of the fundamental tasks in unsupervised machine learning. We propose a new axiom ``proportionally representative fairness'' (PRF) that is designed for clustering problems where the selection of centroids reflects the distribution of data points and how tightly they are clustered together. Our fairness concept is not satisfied by existing fair clustering algorithms. We design efficient algorithms to achieve PRF both for unconstrained and discrete clustering problems. Our algorithm for the unconstrained setting is also the first known polynomial-time approximation algorithm for the well-studied Proportional Fairness (PF) axiom. Our algorithm for the discrete setting also matches the best known approximation factor for PF.