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.

May 6, 2026

TRAM: Training Approximate Multiplier Structures for Low-Power AI Accelerators

Reducing power consumption in AI accelerators is increasingly important. Approximate computing can reduce power consumption while keeping the accuracy loss small. Since multipliers are power-hungry components in AI models, this paper focuses on synthesizing low-power approximate multipliers (AxMs). Unlike prior works that design AxMs separately from AI model training, we present TRAM, which jointly optimizes the AxM structure and AI model parameters to lower power with small accuracy loss. Experiments show that compared to state-of-the-art AxMs, TRAM achieves up to 25.05% AxM power reduction on CNNs with CIFAR-10, and reduces power by up to 27.09% on vision transformers with ImageNet.

Chang Meng, Hanyu Wang, Yuyang Ye +3

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

AI Accelerator Inference Energy-Efficient ML Hardware-Software Co-Design Approximation Algorithms Approximate Computing Neural Network Hardware Acceleration

Ask PDF

May 5, 2026

On Computing Total Variation Distance Between Mixtures of Product Distributions

We study the problem of approximating the total variation distance between two mixtures of product distributions over an

n

-dimensional discrete domain. Given two mixtures

\mathbb{P}

and

\mathbb{Q}

with

k_1

and

k_2

product distributions over

[q]^n

, respectively, we give a randomized algorithm that approximates

d_{\mathrm{TV}}\left({\mathbb{P}},{\mathbb{Q}}\right)

within a multiplicative error of

(1\pm \varepsilon)

in time

\mathrm{poly}((nq)^{k_1+k_2},1/\varepsilon)

. We also study the special case of mixtures of Boolean subcubes over

\{0,1\}^n

. For this class, we give a deterministic algorithm that exactly computes the total variation distance in time

\mathrm{poly}(n,2^{O(k_1+k_2)})

, and show that exact computation is

\#\mathsf{P}

-hard when

k_1+k_2=Θ(n)

Weiming Feng, Yucheng Fu, Minji Yang +1

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

Distribution Matching Approximation Algorithms TV Distance Computation

Ask PDF

May 5, 2026

Exact and Approximate Algorithms for Polytree Learning

Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of

n

variables as a directed forest and are motivated by their more efficient inference and improved interpretability. Since the problem of learning the best polytree is NP-hard, we study which restrictions make it more tractable by considering for example in-degree bounds, properties of score functions measuring the quality of a polytree, and approximation algorithms. We devise an algorithm that finds the optimal polytree in time

O((2+ε)^n)

for arbitrarily small

ε> 0

and any constant in-degree bound

k

, improving over the fastest previously known algorithm of time complexity

O(3^n)

. We further give polynomial-time algorithms for finding a polytree whose score is within a factor of

k

from the optimal one for arbitrary scores and a factor of

2

for additive ones. Many of the results are complemented by (nearly) tight lower bounds for either the time complexity or the approximation factors.

Juha Harviainen, Frank Sommer, Manuel Sorge

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

Graph Structure Learning Bayesian Networks Probabilistic Graphical Models Approximation Algorithms Bayesian Network Structure Learning

Ask PDF

Apr 30, 2026

Matroid Algorithms Under Size-Sensitive Independence Oracles

The standard oracle model for matroid algorithms assumes that each independence query can be answered in constant time, regardless of the size of the queried set. While this abstraction has underpinned much of the theoretical progress in matroid optimization, it masks the true computational effort required by these algorithms. In particular, for natural and widely studied classes such as graphic matroids, even a single independence query can require work linear in the size of the set, making the constant-time assumption implausible. We address this gap by introducing a size-sensitive cost model where the cost of a query

Q

scales with

|Q|

. Nearly linear-time oracle implementations exist for broad families of matroids, and this refined abstraction therefore captures the true cost of query evaluation while allowing for a more faithful comparison between general matroids and their natural special cases. Within this framework we study three fundamental algorithmic tasks: finding a basis of a matroid, approximating its rank, and approximating its partition size. We establish tight results, proving nearly matching upper and lower bounds that show the optimal query cost is (up to logarithmic factors) quadratic in the size of the matroid. On the algorithmic side, our upper bounds are realized by explicit procedures that construct the desired solution. On the complexity side, our lower bounds are unconditional and already hold even for weaker distinguishing formulations of the problems. Finally, for matroids with maximum circuit size at most

c

, we show that the quadratic barrier can be broken, providing an algorithm that calculates the maximum-weight basis with expected query cost

\mathcal{O}(n^{2-1/c} \log n)

Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz +1

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

Query Complexity Oracle Complexity Combinatorial Optimization Approximation Algorithms

Ask PDF

Apr 27, 2026

Nearly Optimal Subdata Selection

When, in terms of the number of data points, the size of a dataset exceeds available computing resources, or when labeling is expensive, an attractive solution consists of selecting only some of the data points (subdata) for further consideration. A central question for selecting subdata of size

n

from

N

available data points is which

n

points to select. While an answer to this question depends on the objective, one approach for a parametric model and a focus on parameter estimation is to select subdata that retains maximal information. Identifying such subdata is a classical NP-hard problem due to its inherent discreteness. Based on optimal approximate design theory, we develop a new methodology for information-based subdata selection, resulting in subdata that approaches the optimal solution. To achieve this, we develop a novel algorithm that applies to a general model, accommodates arbitrary choices of

N

and

n

, and supports multiple optimality criteria, and we prove its convergence. Moreover, the new methodology facilitates an assessment of the efficiency of subdata selected by any method by obtaining tight lower and upper bounds for the efficiency. We show that the subdata obtained through the new methodology is highly efficient and outperforms all existing methods.

Min Yang, Wei Zheng, John Stufken +3

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

Data Selection Training Data Selection Coreset Selection Approximation Algorithms

Ask PDF

Apr 17, 2026

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

We study discrete k-clustering problems in general metric spaces that are constrained by a combination of two different fairness conditions within the demographic fairness model. Given a metric space (P,d), where every point in P is equipped with a protected attribute, and a number k, the goal is to partition P into k clusters with a designated center each, such that a center-based objective function is minimized and the attributes are fairly distributed with respect to the following two fairness concepts: 1) group fairness: We aim for clusters with balanced numbers of attributes by specifying lower and upper bounds for the desired attribute proportions. 2) diverse center selection: Clusters have natural representatives, i.e., their centers. We ask for a balanced set of representatives by specifying the desired number of centers to choose from each attribute. Dickerson, Esmaeili, Morgenstern and Zhang (2023) denote the combination of these two constraints as doubly constrained fair clustering. They present algorithms whose guarantees depend on the best known approximation factors for either of these problems. Currently, this implies an 8-approximation with a small additive violation on the group fairness constraint. For k-center, we improve this approximation factor to 4 with a small additive violation. This guarantee also depends on the currently best algorithm for DS-fair k-center given by Jones, Nguyen and Nguyen (2020). For k-median and k-means, we propose the first constant-factor approximation algorithms. Our algorithms transform a solution that satisfies diverse center selection into a doubly constrained fair clustering using an LP-based approach. Furthermore, our results are generalizable to other center-selection constraints, such as matroid k-clustering and knapsack constraints.

Nicole Funk, Annika Hennes, Johanna Hillebrand +1

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

Clustering Group Fairness Approximation Algorithms

Ask PDF

Apr 17, 2026

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

Chromatic Correlation Clustering (CCC) extends Correlation Clustering by assigning semantic colors to edges and requiring each cluster to receive a single color label. Unlike standard CC, whose LP relaxation has integrality gap 2 on complete graphs and admits a 2.06-approximation, the analogous LP for CCC has a strict lower bound of 2.11, and the best known LP-rounding algorithm achieves 2.15. We explain this gap by isolating the source of difficulty: cross-edge chromatic interference. Neutral edges, whose color does not match the candidate cluster color, create an irreducible cost absent from standard CC and force any color-independent rounding scheme to pay an additional mismatch penalty. We make four contributions. First, we prove a Global Integrality Gap Decomposition Theorem showing that the gap of any color-independent CCC rounding algorithm equals the standard CC gap plus an irreducible chromatic penalty Delta(L) > 0. Second, we solve the associated min-max problem and derive the staircase formula Delta(L) = ((L-1)/L) Delta_infinity, where Delta_infinity is approximately 0.0734. In particular, the two-color gap is 2.0967, separating CCC from standard CC already at L = 2. Third, we introduce Color-Coupled Correlation Clustering (C4). Adding the valid global constraint sum_c x_uv^c >= L-1 and a correlated interval-packing rounding scheme makes neutral edges behave like classical negative edges, recovering the optimal 2.06 approximation and bypassing the 2.11 lower bound for the uncoupled LP. Fourth, experiments on extremal instances, real multi-relational networks, and fairness benchmarks validate the theory: empirical LP gaps follow the predicted staircase, and C4 matches the unconstrained approximation ratio under fairness constraints.

Ibne Farabi Shihab, Sanjeda Akter, Anuj Sharma

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

Clustering Approximation Algorithms

Ask PDF

Apr 14, 2026

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

Ollivier-Ricci curvature (ORC), defined via the Wasserstein distance that captures rich geometric information, has received growing attention in both theory and applications. However, the high computational cost of Wasserstein distance evaluation has significantly limited the broader practical use of ORC. To alleviate this issue, previous work introduced a computationally efficient lower bound as a proxy for ORC based on 1-hop random walks, but this approach empirically exhibits large gaps from the exact ORC. In this paper, we establish a substantially tighter lower bound for ORC than the existing lower bound, while retaining much lower computational cost than exact ORC computation, with practical speedups of tens of times. Moreover, our bound is not restricted to 1-hop random walks, but also applies to k-hop random walks (k > 1). Experiments on several fundamental graph structures demonstrate the effectiveness of our bound in terms of both approximation accuracy and computational efficiency.

Xiang Gu, Huichun Zhang, Jian Sun

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

Ollivier-Ricci Curvature Approximation Algorithms

Ask PDF

Apr 13, 2026

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

We study the problem of constructing a decision tree that identifies an unknown hypothesis from a given ground set, under both average- and worst-case cost. The Optimal Decision Tree (ODT) problem has been extensively studied in the literature, and

\mathcal{O}(\log n)

-approximation guarantees are known for each criterion, including a simultaneous guarantee for both (here

n

is the number of hypotheses) [ICML]. Although most of the existing algorithm use simple greedy strategies, their analyses rely on intricate arguments. Since ODT is a fundamental problem with wide-ranging applications, we are interested in developing algorithms that are both effective and easy to understand. We present a new greedy algorithm with a simplified analysis that simultaneously achieves approximation factors below

3.65\log_2 n

for worst-case cost and

7.3\log_2 n

for average-case cost. Our algorithm for the Optimal Decision Tree behaves greedily with respect to the hereby introduced Separating Subfamily problem which asks for the cheapest subfamily of tests which partitions the hypotheses into pieces of small enough size. We show that the Separating Subfamily can itself be reduced to an instance of the well-known Maximum Coverage problem. At the core of our approach lies exploiting properties of cutting a clique into small pieces, where edges represent pairs of hypotheses to be separated. In the spirit of simplicity, we also provide a new and straightforward application of ODT: an

\mathcal{O}(\log (k\cdot n))

-approximation for the Adaptive Set Cover problem, where

k

is the number of possible realizations.

Michał Szyfelbein

Approximation Algorithms Combinatorial Optimization Decision Tree Learning

Ask PDF

Apr 11, 2026

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

In this paper, we discuss an efficient algorithm for computing the growth distance between two compact convex sets with representable support functions. The growth distance between two sets is the minimum scaling factor such that the sets intersect when scaled about some center points. Unlike the minimum distance between sets, the growth distance provides a unified measure for set intersection and separation. We first reduce the growth distance problem to an equivalent ray intersection problem on the Minkowski difference set. Then, we propose an algorithm to solve the ray intersection problem by iteratively constructing inner and outer polyhedral approximations of the Minkowski difference set. We show that our algorithm satisfies several key properties, such as primal and dual feasibility and monotone convergence. We provide extensive benchmark results for our algorithm and show that our open-source implementation achieves state-of-the-art performance across a wide variety of convex sets. Finally, we demonstrate robotics applications of our algorithm in motion planning and rigid-body simulation.

Akshay Thirugnanam, Koushil Sreenath

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

Approximation Algorithms

Ask PDF

Apr 9, 2026

Adalina: Adaptive Linear Approximation for the Shapley Value and Beyond

The Shapley value, and its broader family of semi-values, has received much attention in various attribution problems. A fundamental and long-standing challenge is their efficient approximation, since exact computation generally requires an exponential number of utility queries in the number of players

n

. To meet the challenges of large-scale applications, we explore the limits of efficiently approximating semi-values under a

Θ(n)

space constraint. Building upon a vector concentration inequality, we establish a theoretical framework that enables sharper query complexities for existing unbiased randomized algorithms. Within this framework, we systematically develop a linear-space algorithm that requires

O(\frac{n}{ε^{2}}\log\frac{1}δ)

utility queries to ensure

P(\|\hat{\boldsymbolφ}-\boldsymbolφ\|_{2}\geqε)\leq δ

for all commonly used semi-values. In particular, our framework naturally bridges OFA, unbiased kernelSHAP, SHAP-IQ and the regression-adjusted approach, and definitively characterizes when paired sampling is beneficial. Moreover, our algorithm allows explicit minimization of the mean squared error

\mathbb{E}[\|\hat{\boldsymbolφ}-\boldsymbolφ\|_{2}^{2}]

for each specific utility function. Accordingly, we introduce the first adaptive, linear-time, linear-space randomized algorithm, Adalina, that theoretically achieves improved mean squared error. All of our theoretical findings are experimentally validated. Our code is available at https://github.com/watml/adalina.

Weida Li, Yaoliang Yu, Bryan Kian Hsiang Low

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

Shapley Value Attribution Approximation Algorithms Adaptive Sampling

Ask PDF

Apr 3, 2026

Adaptive Threshold-Driven Continuous Greedy Method for Scalable Submodular Optimization

Submodular maximization under matroid constraints is a fundamental problem in combinatorial optimization with applications in sensing, data summarization, active learning, and resource allocation. While the Sequential Greedy (SG) algorithm achieves only a

\frac{1}{2}

-approximation due to irrevocable selections, Continuous Greedy (CG) attains the optimal

\bigl(1-\frac{1}{e}\bigr)

-approximation via the multilinear relaxation, at the cost of a progressively dense decision vector that forces agents to exchange feature embeddings for nearly every ground-set element. We propose ATCG (Adaptive Thresholded Continuous Greedy), which gates gradient evaluations behind a per-partition progress ratio

η_i

, expanding each agent's active set only when current candidates fail to capture sufficient marginal gain, thereby directly bounding which feature embeddings are ever transmitted. Theoretical analysis establishes a curvature-aware approximation guarantee with effective factor

τ_{\mathrm{eff}}=\max\{τ,1-c\}

, interpolating between the threshold-based guarantee and the low-curvature regime where ATCG recovers the performance of CG. This shows that the problem structure, as captured by curvature, determines the amount of coordination and communication required to approach full-CG performance. Experiments on a class-balanced prototype selection problem over a subset of the CIFAR-10 animal dataset show that ATCG achieves objective values comparable to those of the full CG method while substantially reducing communication overhead through adaptive active-set expansion.

Mohammadreza Rostami, Solmaz S. Kia

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

Submodular Optimization Approximation Algorithms

Ask PDF

Apr 1, 2026

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

Stochastic Multi-Objective Optimization (SMOO) is critical for decision-making trading off multiple potentially conflicting objectives in uncertain environments. SMOO aims at identifying the Pareto frontier, which contains all mutually non-dominating decisions. The problem is highly intractable due to the embedded probabilistic inference, such as computing the marginal, posterior probabilities, or expectations. Existing methods, such as scalarization, sample average approximation, and evolutionary algorithms, either offer arbitrarily loose approximations or may incur prohibitive computational costs. We propose XOR-SMOO, a novel algorithm that with probability

1-δ

, obtains

γ

-approximate Pareto frontiers (

γ>1

) for SMOO by querying an SAT oracle poly-log times in

γ

and

δ

. A

γ

-approximate Pareto frontier is only below the true frontier by a fixed, multiplicative factor

γ

. Thus, XOR-SMOO solves highly intractable SMOO problems (#P-hard) with only queries to SAT oracles while obtaining tight, constant factor approximation guarantees. Experiments on real-world road network strengthening and supply chain design problems demonstrate that XOR-SMOO outperforms several baselines in identifying Pareto frontiers that have higher objective values, better coverage of the optimal solutions, and the solutions found are more evenly distributed. Overall, XOR-SMOO significantly enhanced the practicality and reliability of SMOO solvers.

Jinzhao Li, Nan Jiang, Yexiang Xue

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.

Multi-Objective Optimization Pareto Optimization Approximation Algorithms

Ask PDF

Mar 24, 2026

Multi-LLM Query Optimization

Deploying multiple large language models (LLMs) in parallel to classify an unknown ground-truth label is a common practice, yet the problem of optimally allocating queries across heterogeneous models remains poorly understood. In this paper, we formulate a robust, offline query-planning problem that minimizes total query cost subject to statewise error constraints which guarantee reliability for every possible ground-truth label. We first establish that this problem is NP-hard via a reduction from the minimum-weight set cover problem. To overcome this intractability, we develop a surrogate by combining a union bound decomposition of the multi-class error into pairwise comparisons with Chernoff-type concentration bounds. The resulting surrogate admits a closed-form, multiplicatively separable expression in the query counts and is guaranteed to be feasibility-preserving. We further show that the surrogate is asymptotically tight at the optimization level: the ratio of surrogate-optimal cost to true optimal cost converges to one as error tolerances shrink, with an explicit rate of

O\left(\log\log(1/α_{\min}) / \log(1/α_{\min})\right)

. Finally, we design an asymptotic fully polynomial-time approximation scheme (AFPTAS) that returns a surrogate-feasible query plan within a

(1+\varepsilon)

factor of the surrogate optimum.

Arlen Dean, Zijin Zhang, Stefanus Jasin +1

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

Multi-LLM Collaboration Approximation Algorithms Robust Optimization Multiclass Classification

Ask PDF

Mar 19, 2026

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

We study unlabeled MRMP for unit-disk robots in a polygonal environment. Although the problem is hard in general, polynomial-time solutions exist under appropriate separation assumptions on start and target positions. Banyassady et al.(SoCG'22) guarantee feasibility in simple polygons under start--start and target--target distances of at least

4

, and start--target distances of at least

3

, but without optimality guarantees. Solovey et al.(RSS'15) provide a near-optimal solution in general polygonal domains, under stricter conditions: start/target positions must have pairwise distance at least

4

, and at least

\sqrt{5}\approx2.236

from obstacles. This raises the question of whether polynomial-time algorithms can be obtained in even more densely packed environments. In this paper we present a generalized algorithm that achieve different tradeoffs on the robots-separation

ρ

and obstacles-separation

ω

, all significantly improving upon the state of the art. Specifically, we obtain polynomial-time constant-approximation algorithms to minimize the total path length when (i)

ρ=2\frac{2}{3}

and

ω=1\frac{2}{3}

, or (ii)

ρ\approx3.291

and

ω\approx1.354

. These solutions are weakly-monotone; we also provide a monotone solution requiring

ω=\approx1.614

and

ρ=4

. We prove that monotone plans may not exist when

ω<1.614

, and weakly-monotone plans may not exist when

ω<1.354

. We then present tradeoffs between the separation bounds and the approximation factor, specifically achieving an (almost) optimal bound of

ρ=2

at the cost of a linear approximation factor and requiring

ω=2

. This applies also for the labeled variant of MRMP, in which case we show a tight bound on

ω

. Finally, we show that without any robots-separation assumption, obstacles-separation of at least

1.5

may be necessary for a solution to exist.

Tsuri Farhana, Omrit Filtser, Shalev Goldshtein

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

Multi-Robot Motion Planning Approximation Algorithms

Ask PDF

Mar 19, 2026

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

Robotic path planning problems are often NP-hard, and practical solutions typically rely on approximation algorithms with provable performance guarantees for general cases. While designing such algorithms is challenging, formally proving their approximation optimality is even more demanding, which requires domain-specific geometric insights and multi-step mathematical reasoning over complex operational constraints. Recent Large Language Models (LLMs) have demonstrated strong performance on mathematical reasoning benchmarks, yet their ability to assist with research-level optimality proofs in robotic path planning remains under-explored. In this work, we introduce the first benchmark for evaluating LLMs on approximation-ratio proofs of robotic path planning algorithms. The benchmark consists of 34 research-grade proof tasks spanning diverse planning problem types and complexity levels, each requiring structured reasoning over algorithm descriptions, problem constraints, and theoretical guarantees. Our evaluation of state-of-the-art proprietary and open-source LLMs reveals that even the strongest models struggle to produce fully valid proofs without external domain knowledge. However, providing LLMs with task-specific in-context lemmas substantially improves reasoning quality, a factor that is more effective than generic chain-of-thought prompting or supplying the ground-truth approximation ratio as posterior knowledge. We further provide fine-grained error analysis to characterize common logical failures and hallucinations, and demonstrate how each error type can be mitigated through targeted context augmentation.

Zhengbang Yang, Md. Tasin Tazwar, Minghan Wei +1

George Mason University · Florida Atlantic University

Mathematical Reasoning Benchmarks Automated Theorem Proving Approximation Algorithms Robot Motion Planning LLM Reasoning

Ask PDF

Mar 9, 2026

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

The celebrated Myerson--Satterthwaite theorem shows that in bilateral trade, no mechanism can be simultaneously fully efficient, Bayesian incentive compatible (BIC), and budget balanced (BB). This naturally raises the question of how closely the gains from trade (GFT) achievable by a BIC and BB mechanism can approximate the first-best (fully efficient) benchmark. The optimal BIC and BB mechanism is typically complex and highly distribution-dependent, making it difficult to characterize directly. Consequently, much of the literature analyzes simpler mechanisms such as the Random-Offerer (RO) mechanism and establishes constant-factor guarantees relative to the first-best GFT. An important open question concerns the worst-case performance of the RO mechanism relative to first-best (FB) efficiency. While it was originally hypothesized that the approximation ratio

\frac{\text{GFT}_{\text{FB}}}{\text{GFT}_{\text{RO}}}

is bounded by

2

, recent work provided counterexamples to this conjecture: Cai et al. proved that the ratio can be strictly larger than

2

, and Babaioff et al. exhibited an explicit example with ratio approximately

2.02

. In this work, we employ AlphaEvolve, an AI-guided evolutionary search framework, to explore the space of value distributions. We identify a new worst-case instance that yields an improved lower bound of

\frac{\text{GFT}_{\text{FB}}}{\text{GFT}_{\text{RO}}} \ge \textbf{2.0749}

. This establishes a new lower bound on the worst-case performance of the Random-Offerer mechanism, demonstrating a wider efficiency gap than previously known.

Yang Cai, Vineet Gupta, Zun Li +1

Yale University

Mechanism Design Approximation Algorithms

Ask PDF

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

Ω(n^2)

time, but designed a 2.62-approximation for MFC with subquadratic complexity. The same method is a

(2γ+ 1)

-approximation for the original MST problem, where

γ\geq 1

is a quality parameter for the initial forest. We introduce a generalized method that interpolates between this prior algorithm and an optimal

Ω(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)

for metric MST to 2 and

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.

Nate Veldt, Thomas Stanley, Benjamin W. Priest +5

Texas A&M University · Lawrence Livermore National Laboratory

Learning-Augmented Algorithms Approximation Algorithms

Ask PDF

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)

X

is a predecessor of

Y

, then in any feasible decision tree

X

needs to be an ancestor of

Y

(or respectively, if

Y

is added to set cover, then so must be

X

). 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

\mathcal{O}^*(\sqrt{m})

-approximation polynomial-time algorithms for all aforementioned problems. The picture is complemented by a number of hardness reductions that provide

\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.

Michał Szyfelbein, Dariusz Dereniowski

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

Combinatorial Optimization Constrained Optimization Approximation Algorithms

Ask PDF

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

k

-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

k

-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

3

-approximation is known for fair

k

-center in general metrics, it has remained open whether this approximation guarantee is tight or could be further improved, especially since the classical unconstrained

k

-center problem admits a polynomial-time factor-

2

approximation. We resolve this open question by proving that, assuming

\mathsf{P} \neq \mathsf{NP}

, for any

ε>0

, no polynomial-time algorithm can approximate fair

k

-center to

(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

k

-groups (for arbitrary

k

), where exactly one center must be selected from each group. Consequently, the factor-

3

barrier for fair

k

-center in general metric spaces is inherent, and existing

3

-approximation algorithms are optimal up to lower-order terms even in these restricted regimes. This result stands in sharp contrast to the

k

-supplier formulation, where both the unconstrained and fair variants admit factor-

3

approximation in polynomial time.

Suhas Thejaswi

Department of Computer Science, Aalto University, Finland

Approximation Algorithms Clustering Group Fairness

Ask PDF

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.

Chendi Qian, Christopher Morris, Stefanie Jegelka +1

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

Graph Neural Networks Combinatorial Optimization Message Passing Neural Networks Approximation Algorithms Neural Combinatorial Optimization

Ask PDF

Feb 9, 2026

Incremental (k, z)-Clustering on Graphs

Given a weighted undirected graph, a number of clusters

k

, and an exponent

z

, the goal in the

(k, z)

-clustering problem on graphs is to select

k

vertices as centers that minimize the sum of the distances raised to the power

z

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)

-clustering solution in the induced shortest-path metric. While efficient dynamic

k

-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)

-clustering problem. As the main result of this paper, we develop a randomized incremental

(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

\tilde O(k m^{1+o(1)}+ k^{1+\frac{1}λ} m)

, where

λ\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

\tilde{O}(k)

with a total update time of

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)

-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)

-clustering algorithm.

Emilio Cruciani, Sebastian Forster, Antonis Skarlatos

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

Clustering Graph Clustering Approximation Algorithms

Ask PDF

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.

Jay-Anne Bulauan, John Rick Manzanares

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

Approximation Algorithms Topological Data Analysis

Ask PDF

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 |\mathcal{C}|)

-approximation for

|\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

\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.

Lutz Oettershagen, Othon Michail

University of Liverpool

Fair Resource Allocation Combinatorial Optimization Group Fairness Approximation Algorithms

Ask PDF

Jul 15, 2024

Faster and Simpler Greedy Algorithm for $k$ -Median and $k$ -Means

Clustering problems such as

k

-means and

k

-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.

Max Dupré la Tour, David Saulpic

Clustering Approximation Algorithms

Ask PDF

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.

Yijun Bian, Yujie Luo

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

Algorithmic Fairness Group Fairness Approximation Algorithms

Ask PDF

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.

Rishi Sonthalia, Anna Seigal, Guido Montufar

UCLA · Harvard University · UCLA and MPI MiS

Submodular Optimization Approximation Algorithms

Ask PDF

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.

Haris Aziz, Barton E. Lee, Sean Morota Chu +1

UNSW Sydney · ETH Zürich · Northwestern University

Clustering Algorithmic Fairness Group Fairness Approximation Algorithms

Ask PDF