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.

Jul 18, 2026

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

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.

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 OptimizationCombinatorial OptimizationApproximation AlgorithmsLarge Neighborhood Search
AskPDF
Jul 16, 2026

CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees

Machine-learned predictions can speed up offline NP-hard optimization, but asking a predictor what to do amounts to asking it to solve the problem, and committing an unchecked prediction forfeits every worst-case guarantee. CASP (Certificate-Augmented Solution Pruning) instead asks which parts of the search space may be ignored, and accepts each answer only after a sound polynomial-time verifier has checked it, so correctness never depends on prediction quality. We develop the learning theory of this design. The verifier makes the induced loss class uniformly bounded, so certificate parameters are learnable from O~(ε−2log⁡K)\tilde O(\varepsilon^{-2}\log K) samples (KK the maximum instance size), whereas the unverified commitment class admits no distribution-free rate and, under cost spread RR, none below Ω(R/ε2)Ω(R/\varepsilon^2). Filtering noisy predictions by verifiable confidence dominates the standard min-combiner, with a margin we compute in closed form, and the prediction stays useful even given the LP, because it breaks ties on degenerate optimal faces, where every symmetric LP policy, meaning one whose commitments depend on the instance only through the verifiable confidence values, provably stalls. Experiments on five problems test the theory's quantitative predictions. With trained predictors, unverified pruning loses up to 2626% of the optimum under distribution shift, while the verified deployment of the same predictions loses nothing.

Haifeng Li, Mo Hai

School of Information, Central University of Finance and Economics Beijing 102206, China

Combinatorial OptimizationLearning-Augmented AlgorithmsPAC LearningApproximation AlgorithmsStatistical Learning Theory
AskPDF
Jul 14, 2026

Graph Partitioning with Demands: Generalized Conductance and its Applications

We study various graph partitioning tasks subject to general demands. In Graph Partitioning with Demands (GPD), the goal is to delete minimum cost supply edge set so that each remaining component contains at most a prescribed fraction of the total demand. In the hierarchical analogue of this problem, Hierarchical Clustering with Demands (HCD), the goal is to build a hierarchy of clusters, charging each supply edge by the demand in the smallest cluster containing its endpoints. Our main general-graph results are approximation algorithms for GPD and HCD. For every fixed 0<ρ<η<10<ρ<η<1, we give a polynomial-time bi-criteria algorithm for GPD whose components have demand at most η⋅Wη\cdot W and cost at most Oρ,η(log⁡n)\mathcal{O}_{ρ,η}(\sqrt{\log n}) times the optimum cost for threshold~ρρ. This procedure can then be applied recursively to obtain an O(log⁡n)\mathcal{O}(\sqrt{\log n})-approximation for HCD. The algorithm for GPD itself uses a crucial subproblem called Generalized Conductance (GC), a new generalization of the Sparsest Cut. On supply trees, we show that GC can be solved exactly in polynomial time. We also give bi-criteria algorithms for GPD based on anchored-LP rounding and separator recursion, as well as a single-criterion (4+ε)(4+ε)-approximation in nO(1/ρ)n^{O(1/ρ)} time. Moreover, through previous reduction, these GPD algorithms yield a 4ee−1\frac{4e}{e-1}-approximation for HCD on trees. We also prove that HCD and GPD and GC are SSEH-hard to approximate within any constant factor. On trees, assuming the Unique Games Conjecture (UGC), GPD is hard to approximate within a factor of 2−ε2-ε by reduction from Vertex Cover, while HCD is hard to approximate within a factor of 1.07481.0748, by reduction from Min-Sum Vertex Cover.

Michał Szyfelbein, Dariusz Dereniowski

Gdańsk University of Technology

Hierarchical ClusteringApproximation AlgorithmsGraph Partitioning
AskPDF
Jul 14, 2026

Hierarchical F\mathcal{F}-Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs

Consider the following variation on the Hierarchical Clustering problem: Usually, while building a hierarchical clustering, one recursively partitions the data until each cluster becomes a singleton. We relax the halting condition of the recursive process to stop whenever the remaining cluster is a graph belonging to a class F\mathcal{F}. We call this problem Hierarchical F\mathcal{F}-Clustering and we measure the quality of any solution using adapted Dasgupta's clustering objective. We study two natural choices of F\mathcal{F}: trees and graphs of bounded diameter. We present the first polynomial time O(log⁡n⋅log⁡log⁡n)\mathcal{O}(\log n\cdot\log\log n) and O(log⁡n)\mathcal{O}(\log n)-approximation algorithms for clustering into trees and bounded diameter graphs respectively. Our main technical contribution is a framework for approximating such problems based on linear programming. In fact, we characterize graphs classes F\mathcal{F} for which our approach can be applied and show that it includes both trees and bounded diameter graphs. However, our ideas are not limited to them and might be useful for other structures as well. Broadly speaking, our framework applies whenever the corresponding flat clustering problem, which we call pFp_{\mathcal{F}}-Partitioning, admits a natural ILP formulation together with a rounding procedure with provable approximation guarantees. Intuitively, given a set of vertices called terminals, the problem is to find an edge set whose removal results in satisfying certain vertex-dependent structural predicate for each terminal. We then use these ingredients to build clustering trees with the aforementioned approximation guarantees. To complement these results, we show that both Hierarchical Clustering into trees and into bounded diameter graphs cannot be approximated within any constant factor under the Small Set Expansion Hypothesis.

Michał Szyfelbein, Dariusz Dereniowski

Gda´nsk University of Technology

Hierarchical ClusteringGraph ClusteringApproximation Algorithms
AskPDF
Jul 12, 2026

Exact and Certified Data Shapley for Weighted k-Nearest-Neighbor Regression and Soft-Label Prediction

Data Shapley is the standard principled answer to which training points are worth what, and its k-nearest-neighbor (KNN) specialization is the version deployed in practice: the exact estimator shipped by toolkits such as pyDVL and OpenDataVal. Exact algorithms are known for unweighted KNN and for weighted KNN classification, but weighted KNN regression and soft-label prediction have resisted: the only exact method is an O(N^K) brute force, exponential in neighborhood size K. The obstruction: the weighted regression prediction is a ratio of two coalition-dependent sums, whose normalization denominator breaks the additive, threshold, and duplication structures the prior polynomial algorithms rely on. We close this gap. We give (i) the first pseudo-polynomial-time exact algorithm (polynomial in N and K at fixed lattice precision) for weighted KNN-regression Data Shapley, a counting dynamic program over the joint integer state (sum of w, sum of w*y), verified against exhaustive enumeration with zero mismatch on 12,716 adversarial instances; (ii) a certified FPTAS for continuous weights and targets, with a machine-checkable per-value error certificate never violated across 86,400 checks; (iii) a complexity landscape, including an unconditional Omega(D_w) output-size lower bound and access-model hardness results; and (iv) a weighted soft-label multi-class extension. We release an open-source, CPU-only library and the first exact weighted-regression Data Shapley ground truth. On downstream mislabel detection our exact values are statistically equivalent to Monte-Carlo Data Shapley (dataset-level TOST, n=8, p<10^-4), the pre-registered outcome; the value of exactness is instead determinism, a certified error bound, and an exact reference for auditing estimators: Monte-Carlo did not reproduce the exact top-10% ranking at any budget tested, up to 3,000 permutations (~1.28e6 utility evaluations).

Zongye Lyu

Faculty of Information Technology, Monash University, Melbourne, VIC 3800, Australia

Shapley Value Attributionk-Nearest NeighborsApproximation Algorithms
AskPDF
Jul 7, 2026

The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression

Active learning studies the fundamental question: what data should we choose to observe? The greedy algorithm in optimal experiment design is a common heuristic and also equivalent to myopic Bayesian active learning for linear regression, the common framework where long-term planning is replaced with the one-step optimal choice. In this work, we prove a first-of-its-kind approximation ratio for the greedy algorithm's risk that is tight up to an absolute constant. The approximation ratio is linear in the maximum initial leverage score (MILS), a newly identified quantity fundamental to the greedy algorithm's performance. Finally, we illustrate the results with simple numerical simulations.

Stephen Mussmann

School of Computer Science Georgia Institute of Technology

Active LearningLinear RegressionBayesian Experimental DesignApproximation AlgorithmsActive Experimental Design
AskPDF
Jul 7, 2026

Data-dependent Evaluations for Budgeted Submodular Maximization

Submodular maximization is an important building block for developing algorithms in many areas such as machine learning and data mining. Due to the NP-hardness of the problem, analysis of submodular maximization algorithms typically provides pessimistic worst-case approximation factors only. It is not easy to evaluate how close a produced solution is to an optimal one for a given problem instance. In this paper, we develop new data-dependent upper bounds for submodular maximization with a knapsack constraint. We theoretically prove that they dominate the optimal solution and empirically demonstrate their advantages in certifying how close to optimal a solution is through experiments with real-world datasets.

Lejian Zhang, Xueyan Tang, Jing Tang

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

Submodular OptimizationApproximation Algorithms
AskPDF
Jul 4, 2026

TSP with Predictions: Heatmap to Tour with Provable Guarantees

The Traveling Salesperson Problem (TSP) has long served as a benchmark for evaluating the strength of optimization techniques in the classical theory of algorithms. In recent efforts to apply ML to algorithmic problems, TSP has also become a natural testbed for the development of ML-based techniques. A common approach is to train a neural network to output a heatmap estimating the likelihood of each edge to be part of the optimal tour; however, converting such a heatmap into an actual tour remains a non-trivial and often computationally intensive step. In this work, we propose algorithms for transforming heatmaps into tours with theoretical guarantees linking the achieved approximation ratio to the quality of the provided heatmap. In the spirit of algorithms with predictions, our results can be described as (1+2ηOPT)(1+2\fracη{\mathrm{OPT}})-approximation algorithms, where ηη denotes the L1 distance between the prediction (heatmap) and an optimal solution (tour). Since the previous works lack such explicit guarantees, we compare our approach against them experimentally.

Marek Eliáš, Fabrizio Grandoni, Adam Polak +1

Traveling Salesperson ProblemCombinatorial OptimizationLearning-Augmented AlgorithmsApproximation AlgorithmsNeural Combinatorial Optimization
AskPDF
Jun 25, 2026

Three-Objective Integral R2 Subset Selection: NP-Hardness and Submodular Approximation

Selecting a fixed number of representative points from a finite Pareto-front approximation is a fundamental post-processing task in multiobjective optimization. This paper studies this problem for the integral R2 indicator in three objectives, where the indicator is defined as the integral of the lower envelope of weighted Tchebycheff scalarizations over the two-dimensional weight simplex. We provide two complementary algorithmic results. On the positive side, we show that the integral R2 improvement with respect to any fixed baseline is a monotone submodular set function. For the usual ideal-point based R2 indicator, with the ideal point fixed, this yields a direct gap-reduction guarantee: greedy selection closes at least a (1−1/e)(1-1/e)-fraction of the maximum possible R2 gap between a fixed dominated anchor value and the best cardinality-kk value. We also give a tested greedy implementation that evaluates exact integral R2 values by subdivision, with worst-case running time O(n6)O(n^6). On the negative side, we prove that exact fixed-cardinality subset selection is NP-hard already in three objectives. The hardness proof uses a perspective transformation that maps Tchebycheff-shadow improvements to a weighted anchored-box union problem with density (x1+x2+x3)−4(x_1+x_2+x_3)^{-4}, and then adapts the three-dimensional anchored-box construction of Bringmann, Cabello, and Emmerich. Together, these results separate the tractable two-objective case from the three-objective case while identifying a principled approximation route based on submodular optimization.

Michael T. M. Emmerich

Submodular OptimizationApproximation AlgorithmsMulti-Objective OptimizationGreedy Optimization
AskPDF
Jun 19, 2026

Simultaneously Efficient Allocation of Indivisible Items Across Multiple Dimensions

Many allocation problems are intrinsically multidimensional, since an item may contribute differently to several criteria, and optimizing a single aggregate objective can hide severe losses in other dimensions. We study how much efficiency can be guaranteed simultaneously when indivisible items have multiple attributes. To this end, we introduce the multidimensional efficient allocation (MDEA) model, where each agent has an additive valuation in each dimension, and investigate simultaneous efficiency under utilitarian social welfare (USW) and egalitarian social welfare (ESW). Our results reveal a sharp worst-case frontier. For exact efficiency, maximizing the number of dimensions attaining the USW optimum admits a c/ℓc/\ell-approximation for every fixed constant cc, and this dependence on the number ℓ\ell of dimensions is essentially unavoidable; for ESW, even deciding whether two dimensions can be optimized simultaneously is NP-hard with binary valuations. For approximate simultaneous efficiency in every dimension, we identify a tight threshold of order 1/ℓ1/\ell, showing that such guarantees always exist for both USW and ESW, while any asymptotically better dependence on ℓ\ell is impossible, even for binary valuations. Finally, we introduce three natural multidimensional Pareto notions and characterize both their relationships and their computational complexity.

Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui

Chuo University, Tokyo, Japan · Indian Institute of Technology Kharagpur, Kharagpur, India

Combinatorial OptimizationApproximation AlgorithmsMulti-Objective OptimizationPareto OptimizationMulti-Agent Resource AllocationSocial Welfare Maximization
AskPDF
Jun 15, 2026

PolyMerge: Compressing 3D Gaussian Splats with Polytope Coverings for Provably Safe Resource-Constrained Navigation

Obstacle avoidance is essential for safe navigation and motion planning. Recent radiance field reconstruction methods enable object detection and modeling with high fidelity, but remain too memory- and compute-intensive for on-board perception-based path planning. To address these limitations, we propose PolyMerge to convert a large, photorealistic 3D Gaussian Splatting (3DGS) model of a scene into a lightweight representation of convex polytopes whose union provably over-approximates all obstacles in the original 3DGS model. PolyMerge tunes the polytope count to trade off conservativeness and compute cost, and integrates with control barrier functions (CBFs) to plan collision-free paths. We showcase PolyMerge in simulation and hardware experiments on a Crazyflie drone, which uses PolyMerge to compute and follow safe trajectories in real time under severe onboard compute constraints, outperforming baselines in speed while guaranteeing safety. For our code and videos, visit https://athlon76.github.io/PolyMerge-website/.

Jihoon Hong, Chih-Yuan Chiu, Sara Fridovich-Keil +1

1Georgia Institute of Technology.

3DGS CompressionConstrained Motion PlanningSafe Robot NavigationRobot SafetyApproximation AlgorithmsRobot Collision Avoidance
AskPDF
Jun 11, 2026

Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling

Recently, Antoniadis et al. (ICLR 2025) proposed a framework for incorporating predictions to approximate NP-hard selection problems. Despite its simplicity, this approach tightly matches theoretical lower bounds, making its generalization highly compelling. We address an open question raised in the work of Antoniadis et al., concerning the extension of this approach to other important problems outside the class of selection problems, such as scheduling. We develop a learning-augmented algorithm for the makespan minimization problem on unrelated machines, denoted by R∥Cmax⁡R\|C_{\max}. By using predictions of heavy job assignments, we achieve a polynomial-time (1+ε)(1+\varepsilon)-approximation for accurate predictions that smoothly degrades to a worst-case 2-approximation as the error increases. We conclude our work with an empirical analysis of our method.

Kaito Baba, Evripidis Bampis, Giorgos Mitropoulos

The University of Tokyo, Tokyo, Japan · Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

Combinatorial OptimizationLearning-Augmented AlgorithmsApproximation Algorithms
AskPDF
Jun 11, 2026

Multi-Objective Coevolution of Prompts and Templates for Circuit Approximation

Approximate multipliers deliberately relax computational accuracy to achieve gains in power efficiency, latency, and silicon area, which makes them well-suited for error-resilient applications such as neural networks. In this work, we introduce a co-evolutionary algorithm that leverages an off-the-shelf large language model (LLM) without requiring domain-specific training to automate the design of optimized 8-bit approximate multipliers. The approach simultaneously evolves a population of candidate circuits and a population of prompt templates that steer LLM-driven modifications. Experimental results for several target design objectives demonstrate that the proposed method discovers approximate multipliers with improved error-area trade-offs compared to highly optimized circuits from the EvoApproxLib library.

Martin Tomasovic, Lukas Sekanina

Brno University of Technology, Faculty of Information Technology Brno, Czech Republic

Multi-Objective Evolutionary OptimizationLarge Language Model-Guided OptimizationAutomatic Prompt OptimizationApproximation AlgorithmsApproximate Computing
AskPDF
Jun 3, 2026

A General Framework for Dynamic Consistent Submodular Maximization

Consistency is an important property in dynamic submodular maximization and entails maintaining a near-optimal solution at all times, making only a small number of adjustments to the solution in each step. Prior work has explored this question for the insertion-only case, where the algorithm faces a stream of nn insertions, and has established lower and upper bounds for the cardinality-constrained version of the problem. We consider this question in the fully dynamic setting, where the stream of operations may contain both insertions and deletions. We develop a general framework for designing algorithms for this setting, and instantiate it to obtain the first constant-factor approximations with sublinear consistency. For cardinality constraints, we propose a 12−O(ε)\frac 12 - O(\varepsilon) approximation that is O(1ε2)O\left(\frac{1}{\varepsilon^2}\right) consistent. For rank-kk matroid constraints, we construct a 14−O(ε)\frac 14 - O(\varepsilon) approximation to the dynamic optimum that is O(log⁡kε2)O\left(\frac{\log k}{\varepsilon^2}\right) consistent.

Paul Dütting, Federico Fusco, Silvio Lattanzi +3

1Google Research · 2Dept. of Computer, Control and Management Engineering, Sapienza University of Rome · 3EPFL

Submodular OptimizationApproximation Algorithms
AskPDF
Jun 3, 2026

Prediction Under Imperfect Compression: A Theory of Approximate MDL

Minimum Description Length (MDL) formalizes the principle of Occam's razor by optimizing the total description length: L(model)+L(data ∣ model)L(\mathrm{model})+L(\mathrm{data} \ | \ \mathrm{model}). For sequential prediction, the MDL method repeatedly selects a model with a minimum objective score of the observed prefix for the next step prediction. Classical MDL prediction theory shows that exact optimization of the MDL objective indeed provides a strong compression guarantee that supports reliable prediction. However, practical machine learning usually can only find models by approximately optimizing the objective function. To bridge this gap, this paper addresses the following fundamental question: Under what forms of approximation and regularization does approximate MDL still guarantee reliable sequential prediction? This work offers a principled characterization. We prove that for any approximation with additive slack CC of the more general form of the balanced MDL objective: λ⋅L(model)+L(data ∣ model)λ\cdot L(\mathrm{model})+L(\mathrm{data} \ | \ \mathrm{model}), the cumulative expected squared prediction error is finite for all λ≥1λ\ge1. The case λ>1λ>1 is proved by an affinity-telescoping argument, while the boundary case λ=1λ=1 is proved by a likelihood-ratio stopping argument based on exact static MDL bounds. Our results establish that classical MDL regularization remains robust to any fixed additive optimization error. Furthermore, we establish that our characterization of the approximate MDL framework is sharp: When 0<λ<10<λ<1, overfits can happen to incur infinite cumulative expected error in the universal class of estimable measures, and hence a strong form of model-complexity regularization is necessary. In addition, model selection may fail in every regularized regime λ>0λ>0, under multiplicative approximation, and thus, additive approximation is both sufficient and essential.

Qian Li, Xinyu Mao, Shang-Hua Teng +1

Shenzhen Research Institute of Big Data · University of Southern California

Minimum Description LengthApproximation AlgorithmsStatistical Learning TheorySequence PredictionSequence Modeling
AskPDF
May 24, 2026

Algorithms with Polynomially-Improved Approximation Factors for the 2→q2 \rightarrow q Norm, and Applications

The 2→q2 \rightarrow q norm of a matrix X∈Rn×dX \in \mathbb{R}^{n \times d} is defined as ∥X∥2→q=sup⁡∥v∥2=1∥Xv∥q\lVert X \rVert_{2 \rightarrow q} = \sup_{\lVert v \rVert_2 = 1} \lVert Xv \rVert_q. We give polynomial-time multiplicative approximation algorithms for this norm when q>2q > 2 (i.e. in the hypercontractive setting). This problem either directly captures or is closely related to long-standing open problems in combinatorial optimization and hardness of approximation (e.g. Small Set Expansion), quantum information (e.g. Best Separable State), and algorithmic statistics. Very little is known about what approximation factors we can achieve for this problem in polynomial time, even though such approximations have significant downstream consequences. Barak, Brandão, Harrow, Kelner, Steurer, and Zhou showed that no polynomial-time algorithm can achieve an approximation factor better than 2log⁡n2^{\sqrt{\log n}}, assuming the Exponential Time Hypothesis (FOCS'12). On the other hand, a simple spectral algorithm gives a d1/4d^{1/4}-approximation as a baseline. We give, to the best of our knowledge, the first polynomial-time approximation algorithm beating this baseline by polynomial factors. For the important special case of q=4q = 4 it achieves a d1/8d^{1/8}-approximation. All previous algorithms required additional assumptions on XX, or only surpassed the baseline for small values of nn. Moreover, we construct sum-of-squares certificates for the 2→q2 \rightarrow q norm. This directly implies improved algorithms for robust mean and covariance estimation, robust regression, and clustering, when the data only satisfies a bound on its qq-th moment.

Samuel B. Hopkins, Stefan Tiegel

MIT

Robust RegressionRobust Mean EstimationApproximation Algorithms
AskPDF
May 19, 2026

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

Squared Wasserstein distance is a frequently used tool to measure discrepancy between probability distributions. This distance is typically computed between empirical measures of size nn from two underlying random samples. Unfortunately, even in lower dimensional Euclidean space problems (d∈{2,3})\left( d \in \{2,3\} \right), algorithms for Wasserstein distance computation with approximate or exact precision guarantees scale poorly in the runtime as a function of nn and the desired precision. In response, we consider the computational-statistical runtime, where the goal is to estimate from samples the Wasserstein distance between potentially smooth measures up to εε-additive error in expectation with respect to the sampling; we allow O(1)O(1) computational cost for collecting a sample. Towards this, we develop a Sample-Sketch-Solve paradigm where we introduce a regular cartesian grid sketch of the samples. We show that (especially under αα-Hölder smooth distributions) this can compress the data without increasing asymptotic error, and also regularizes the structure which enables faster exact algorithms. Ultimately, we approximate W22(P,Q)W_2^2(P,Q) within εε error in ε−max⁡(2,d+1+o(1)1+α)ε^{-\max(2,\frac{d+1+o(1)}{1+α})} time for 0<α<10 < α< 1 Hölder smooth distributions P,QP,Q on (0,1)d(0,1)^{d}; an optimal Θ(ε−2)Θ(ε^{-2}) for α>1/2α> 1/2 when d=2d=2 and nearly optimal as α→1α\to 1 when d=3d = 3.

Peter Matthew Jacobs, Jeff M. Phillips

Department of Statistics University of Wisconsin-Madison Madison, WI 53706 · Kahlert School of Computing University of Utah Salt Lake City, UT 84101

Randomized SketchingApproximation AlgorithmsOptimal TransportWasserstein Distance
AskPDF
May 18, 2026

Nash Welfare in Additively Separable Hedonic Games

Additively separable hedonic games (ASHGs) are a prominent model of coalition formation where agents' preferences are derived from their individual valuations of peers. While social welfare maximization in ASHGs has traditionally focused mostly on utilitarian welfare, Nash welfare -- a well-established metric in economics which balances fairness with efficiency and offers scale invariance -- has been entirely overlooked. In this paper, we initiate the study of Nash welfare in ASHGs. We point out desirable properties fulfilled by partitions with high Nash welfare. This includes guaranteed contractual Nash stability in symmetric games, even for any approximation of Nash welfare. This is particularly appealing since, as for other welfare notions, Nash welfare turns out to be NP-hard to maximize, even for the ASHG subclass of symmetric aversion to enemies games (AEGs). A main focus of our study is on approximation algorithms for the Nash welfare objective. We present packing-based algorithms with approximation ratios for well-established subclasses of ASHGs: n−1n-1 for AEGs and 2n2n for appreciation of friends games. This is complemented by a strict inapproximability result showing it is NP-hard to approximate Nash welfare within a factor of 1.00007591.0000759 in general ASHGs. Further, we investigate the restricted settings with an upper bound on the coalition size or number of coalitions, and draw the boundary between the cases admitting efficient algorithms and those yielding NP-hardness: bounding the allowed size or number of coalitions by 22 admits polynomial-time solvability, whereas bounds of 33 or more yield NP-hardness or unbounded inapproximability.

Marta Pagano, Alexander Schlenga

Sapienza University of Rome, Italy · Technical University of Munich, Germany

Cooperative Game TheoryGame TheoryApproximation AlgorithmsCoalition Formation
AskPDF
May 18, 2026

An Approximation Algorithm for Graph Label Selection

In the graph label selection problem, one is given an nn-vertex graph and a budget kk, and seeks to select kk vertices whose labels enable accurate prediction of the labels on the remaining vertices. This problem formalizes distilling a small representative set from the whole graph. We present the first O~(log⁡1.5n)\tilde{O}(\log^{1.5} n)-approximation algorithm for graph label selection under the standard budget constraint. Prior work either relies on resource augmentation, allowing substantially more than kk labeled vertices, or consists primarily of heuristics without provable guarantees. Finally, we demonstrate that practical heuristic variants of our algorithm scale to significantly larger graphs than previous methods, while essentially retaining their quality.

Josia John, Simon Meierhans, Maximilian Probst Gutenberg

Department of Computer Science, ETH Zurich, Zurich, Switzerland.

Semi-Supervised LearningApproximation Algorithms
AskPDF
May 15, 2026

Optimizing Line Segment Inspection with Limited-Range Drones

Optimization problems with drones are widely studied in a variety of civilian tasks, mainly due to their ability to traverse rough terrains and to carry cameras and other sensors for surveillance tasks. The limited battery life of these aerial robots poses challenges in operational research. In this paper, we address the following optimization problem. We are given a set of line segments (e.g. tubes in a solar plant) to inspect by drones. The objective is to detect broken pipes using artificial intelligence and path planning must be carried out efficiently. On the one hand, the limited capacity of the batteries necessitates periodic visits (tours) to a fixed base station. However, it is desirable to allocate a set of tours for each drone to ensure that the segments are covered as quickly as possible, aiming to minimize the makespan, which is the maximum time spent by any drone. We are able to prove that this optimization problem is strongly NP-hard even when the segments are positioned on a line and the scenario involves only two drones. Then, approximation algorithms are proposed. Our computational experiments demonstrate that the proposed algorithm achieves near-optimal performance across diverse operational scenarios.

José-Miguel Díaz-Báñez, José-Manuel Higes, Alina Kasiuk +1

Department of Applied Mathematics, University of Seville, Spain

Aerial RoboticsCombinatorial OptimizationVehicle RoutingMulti-Robot Task AllocationApproximation Algorithms
AskPDF
May 13, 2026

Stochastic Matching via Local Sparsification

The classic online stochastic matching problem typically requires immediate and irrevocable matching decisions. However, in many modern decentralized systems such as real-time ride-hailing and distributed cloud computing, the primary bottleneck is often local communication bandwidth rather than the timing of the match itself. We formalize this challenge by introducing a two-stage local sparsification framework. In this setting, arriving requests must prune their realized compatibility sets to a strict budget of kk edges before a central coordinator optimizes the global matching. This creates a "middle ground" between local information constraints and global optimization utility. We propose a local selection strategy, parametrized by a fractional solution of the expected instance. Theoretically, we quantify the approximation ratio as a function of the solution's {\em spread}. We prove that under sufficient spread, our sparsifier globally preserves the expected size of the maximum matching. Empirically, we demonstrate the robustness of our approach using the New York City ride-hailing datasets and adversarial synthetic benchmarks. Our results show that near-optimal global matching is achievable even with highly constrained local budgets, significantly outperforming standard online baselines.

Sara Ahmadian, Edith Cohen, Mohammad Roghani

Google Research · Tel Aviv University

Approximation Algorithms
AskPDF
May 13, 2026

Decision Tree Learning on Product Spaces

Decision tree learning has long been a central topic in theoretical computer science, driven by its practical importance. A fundamental and widely used method for decision tree construction is the top-down greedy heuristic, which recursively splits on the most influential variable. Despite its empirical success, theoretical analysis of this heuristic has been limited. A recent breakthrough by Blanc et al. (ITCS, 2020) provided the first rigorous theoretical guarantees for the greedy approach, but only under the uniform distribution. We extend this analysis to the more general and practically relevant setting of arbitrary product distributions. Our main result shows that for any function ff computable by an optimal decision tree of size ss, maximum depth DoptD_{\text{opt}}, and average depth ΔoptΔ_{\text{opt}}, the greedy heuristic constructs an εε-approximating tree whose size grows at most with exp⁡(ΔoptDoptlog⁡(e/ε))\exp(Δ_{\text{opt}} D_{\text{opt}} \log(e/ε)). In the special case where the optimal tree is a full binary tree, this bound improves upon the bound of Blanc et al. and holds under a strictly broader class of distributions. Moreover, we present an algorithm based on the top-down greedy heuristic that is entirely parameter-free -- it requires no prior knowledge of the optimal tree's size or depth -- offering a practical advantage over Blanc et al.'s method.

Arshia Soltani Moakhar, Faraz Ghahremani, Kiarash Banihashem +1

Department of Computer Science, University of Maryland, College Park, USA.

Decision Tree LearningApproximation Algorithms
AskPDF
May 12, 2026

Time and Supply Fairness in Electricity Distribution using kk-times bin packing

Given items of different sizes and a fixed bin capacity, the bin-packing problem is to pack these items into the minimum number of bins such that the sum of the item sizes in each bin does not exceed the capacity. We define a new variant, k-times bin-packing (kBP), in which the goal is to pack the items so that each item appears exactly k times in k different bins. We generalize existing approximation algorithms for bin-packing to solve kBP and analyze their performance ratios. The fair electricity division problem motivates the study of kBP. The goal is to allocate the available supply among households using some fairness criteria, such as the egalitarian principle. We prove that every electricity division problem can be solved by k-times bin-packing for some finite k, which depends only on the number of households. We implement generalizations of the First-Fit and First-Fit Decreasing bin-packing algorithms to solve kBP and apply them to real electricity demand data. We show that our generalizations outperform existing heuristic solutions to the same problem in terms of the egalitarian allocation of connection time. We study another variant of the egalitarian allocation problem, in which the goal is to maximize the minimum number of watts allocated to a household. For this variant, we prove an impossibility result: there does not exist such a k that depends only on the number of agents. This impossibility result motivates us to develop four different heuristic algorithms to solve the egalitarian allocation of watts problem. We evaluate the heuristics by summing the minimum watts allocated to any household in each hour, yielding a fairness metric that reflects the lowest watt allocation across all hours. A higher total minimum of watts indicates a more equitable distribution. Thus, we establish new benchmarks for fair allocation of watts.

Dinesh Kumar Baghel, Alex Ravsky, Erel Segal-Halevi

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

Fair Resource AllocationCombinatorial OptimizationGroup FairnessApproximation Algorithms
AskPDF
May 12, 2026

On the Approximation Complexity of Matrix Product Operator (MPO) Born Machines

Matrix product operator Born machines (MPO-BMs) are tractable tensor-network models for probabilistic modeling, yet their approximation capabilities remain poorly understood in theory. In this paper, we characterize these capabilities from both negative and positive perspectives. As a negative result, we prove that constructing a polynomial-bond MPO-BM approximation to an arbitrary continuous target with bounded KL error is NP-hard. On the positive side, for score-based variational inference, we prove that targets satisfying a log-Sobolev inequality admit polynomial-bond MPO-BM approximations with provable KL guarantees when the loss-induced Hamiltonian is local and has a constant spectral gap. Furthermore, under the same conditions, we construct local importance-sampling estimators and prove that polynomially many local score queries suffice to preserve the KL guarantees.

Chao Li, Zerui Tao, Yuchen Cong +2

RIKEN-AIP · Jutentedo University

Tensor NetworksApproximation Algorithms
AskPDF
May 11, 2026

Network-Based Interventions for HIV Prevention via Cascade-Aware Suppression of Transmission

Treating and preventing Human Immunodeficiency Virus (HIV) remains a critical global health challenge. While antiretroviral therapy provides a path toward viral suppression -- effectively eliminating an individual's transmission risk -- systemic resource constraints limit the reach of intervention efforts. This work addresses the strategic distribution of intensive resources among virally unsuppressed individuals to minimize the expected cascade of new infections within a transmission network. We formalize this challenge as a novel constrained optimization problem where we have resources to "treat" kk out of a set P\mathbf{P} of virally unsuppressed individuals, and establish its theoretical connections to existing computational literature. We then propose Cascade-Aware Suppression of Transmission (CAST), a polynomial-time (δ,ε)(δ, ε)-approximation algorithm that achieves a 2∣P∣2\sqrt{|\mathbf{P}|} approximation ratio by leveraging connections to the Minimum-kk-Union (MkU) problem and Hoeffding-style concentration bounds. Extensive evaluations on real-world HIV networks demonstrate that CAST outperforms standard public health and computer science baselines. Furthermore, we show that CAST is empirically robust across diverse infectious disease networks, varied edge probability initializations, and settings involving imperfect network data.

Akseli Kangaslahti, Davin Choo, Milind Tambe +2

Harvard University · University of Witwatersrand · Wits Health Consortium +1

HealthcareCombinatorial OptimizationApproximation Algorithms
AskPDF
May 9, 2026

A Reconfigurable Multiplier Architecture for Error-Resilient Applications in RISC-V Core

Neural Networks (NNs) have been widely adopted due to their outstanding efficacy and adaptability across computer vision and deep learning applications. The optimization of NNs is necessary to enable their deployment on energy constrained embedded devices, where the limited available energy poses a significant challenge for efficient inference. This paper presents a runtime reconfigurable multiplier architecture integrated into the RISC-V core, targeting energy efficient neural network inference and edge AI applications. The proposed multiplier supports adaptability for exact and approximate computation with multiple configurable accuracy levels via a dedicated mulscr, enabling fine-grained energy accuracy control within a standard processor pipeline. The proposed design achieves 44%-52% and 62%-68% power reduction in exact and approximate modes respectively, while maintaining the computational performance of 1.89 DMIPS/MHz. Evaluations on error-tolerant workloads including 2d convolution and matrix multiplication demonstrate up to 63% reduction in energy consumption, with the proposed design achieving 1.21 pJ/instruction for matrix multiplication, confirming its effectiveness for energy-constrained edge AI deployments.

Pragun Jaswal, L. Hemanth Krishna, B. Srinivasu

Indian Institute of Technology Mandi, Mandi–175005, India

Efficient Neural Network InferenceEnergy-Efficient MLEdge MLApproximation AlgorithmsApproximate Computing
AskPDF
May 8, 2026

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions

Submodular functions -- functions exhibiting diminishing returns -- are central to machine learning. When the objective is monotone and non-negative, the greedy algorithm achieves a tight 63%63\% approximation. But many practical objectives incorporate costs that make them negative on some inputs, and all existing multiplicative guarantees require non-negativity. Prior work handles negativity through additive bounds for the special class of decomposable functions and non-monotonicity through partial-monotonicity parameters, but these address each difficulty in isolation and neither extends the classical structural theory. We extend curvature -- a parameter measuring how far a function deviates from linearity -- to all submodular functions, handling both non-monotonicity and negativity through a single classical concept. A greedy algorithm with pruning achieves a curvature-controlled multiplicative ratio for any submodular function, including those taking negative values -- the first such guarantee beyond monotonicity and non-negativity. In the non-monotone regime 1≤cg<2.21 \le c_g < 2.2, the bound strictly beats the best known uniform ratio of 0.4010.401 (for non-negative ff), and it recovers the classical (1−e−cg)/cg(1-e^{-c_g})/c_g guarantee for monotone functions. A multilinear-extension variant extends the framework to general combinatorial constraints via multilinear relaxation. Experiments on cost-penalized experimental design, coverage, feature selection, and a curvature sweep on Multi-News passage selection support the theory.

Yixin Chen, Alan Kuhnle

Department of Computer Science & Engineering, Texas A&M University

Submodular OptimizationApproximation AlgorithmsGreedy OptimizationCurvature-Aware Optimization
AskPDF
May 8, 2026

Online Allocation with Unknown Shared Supply

Many real-world resource allocation systems, such as humanitarian logistics and vaccine distribution, must preposition limited supply across multiple locations before demand is realized while stockouts incur irreversible service losses. To study this, we introduce the Online Shared Supply Allocation (OSSA) problem, a stateful online model in which a central hub allocates a finite, unknown supply to multiple sites facing sequential demand under fixed-charge transportation costs and lost-sales penalties. Unlike classical make-to-stock or make-to-order inventory models, OSSA precludes backlogging and replenishment only hedges against future demand. To tackle OSSA, we propose a deterministic threshold-proportional policy GPA and prove that it achieves a 4/34/3-approximation to the offline optimum up to an additive term independent of the total supply. We complement this with matching lower bounds showing that the 4/34/3 ratio is tight and that the additive-error dependence is unavoidable, even for randomized algorithms that know the total supply upfront. Finally, we develop a learning-augmented extension to GPA that principally incorporates imperfect forecasts (e.g., from human experts or ML models) commonly available in practice, enabling us to exploit high-quality advice while being robust against arbitrary bad ones. Synthetic and real-world experiments show that GPA outperforms natural baselines with global supply is scarce.

Tzeh Yuan Neoh, Davin Choo, Mengchu Yue +1

Harvard University

Online Resource AllocationSequential Decision MakingApproximation AlgorithmsInventory ControlSupply Chain ManagementLearning-Augmented Algorithms+2
AskPDF
May 7, 2026

Accelerated Relax-and-Round for Concave Coverage Problems

We present an accelerated relax-and-round algorithm for concave coverage problems, which generalize the classic maximum coverage problem. Building on the relax-and-round framework of Barman et al. [STACS 2021], we propose two significant improvements. First, we replace the linear programming (LP) relaxation step with a projected accelerated gradient method applied to a smooth surrogate objective to achieve a O~(mnε−1)\widetilde{O}(mn \varepsilon^{-1}) running time. Second, we use a specialized rounding scheme for the hypersimplex that combines the Carathéodory decomposition algorithm in Karalias et al. [NeurIPS 2025] with randomized swap rounding of Chekuri et al. [FOCS 2010]. We prove tight approximation ratios for new reward functions, including a 0.8270.827-approximation for the logarithmic reward φ(x)=log⁡(1+x)\varphi(x) = \log(1 + x). Finally, we conduct maximum multi-coverage experiments on synthetic and real-world graphs, demonstrating that our algorithm outperforms approaches that use state-of-the-art LP solvers.

Matthew Fahrbach, Mehraneh Liaee, Morteza Zadimoghaddam

Google Research

Submodular OptimizationApproximation Algorithms
AskPDF
May 7, 2026

Convex-Geometric Error Bounds for Positive-Weight Kernel Quadrature

Kernel quadrature can exploit RKHS spectral structure and outperform Monte Carlo on smooth integrands, but optimized quadrature weights are generally signed and may be numerically unstable. We study whether spectral acceleration remains possible when the weights are constrained to be positive, i.e., simplex weights. In the exact-target fixed-pool setting, an evaluated i.i.d. candidate pool of size NN is already available and the task is to reweight it so as to approximate the kernel mean embedding. We show that this positive reweighting problem is governed not by the equal-weight empirical average, but by the random convex hull generated by the pool. Our main geometric result shows that the mean of a bounded dd-dimensional random vector can be approximated by a convex combination of NN i.i.d. samples at accuracy O(d/N)O(d/N) with high probability, sharper than equal-weight averaging in the fixed-dimensional regime. We transfer this dd-dimensional convex-hull approximation to full RKHS worst-case error through an augmented Mercer-truncation argument. The resulting positive-weight KQ bounds consist of a spectral tail term and a finite-sample convex-hull term, yielding Monte-Carlo-beating rates in favorable spectral regimes, including near-O(1/N)O(1/N) rates up to logarithmic factors under exponential spectral decay. We also provide a constructive Frank--Wolfe algorithm that operates directly on the pool atoms, maintains simplex weights, and admits an explicit optimization-error bound.

Satoshi Hayakawa

The University of Tokyo

Constrained OptimizationKernel MethodsApproximation AlgorithmsFrank-Wolfe Algorithms
AskPDF