Overview

Approximation algorithms study how to solve optimization problems efficiently when finding an exact optimum is computationally infeasible, while measuring how close the result is to the best possible solution. Common tools include greedy methods for set cover and submodular maximization, linear-programming relaxations with rounding for clustering and graph problems, and randomized, streaming, or coreset methods for large or changing inputs. Researchers also develop PTAS and FPTAS schemes for restricted settings and prove hardness bounds that show when stronger guarantees are unlikely, across problems such as fair clustering, facility location, scheduling, allocation, and robot motion planning. A central tension is balancing worst-case guarantees with practical speed, scalability, and constraints such as fairness, online decisions, or imperfect predictions.

Latest papers

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

Nov 15, 2026

Tight Bounds for Non-Monotone Submodular Maximization under a Cardinality Constraint with Constant Recourse

We study the maximization of a nonnegative submodular function under a cardinality constraint when elements arrive one at a time and an algorithm must report a feasible set after every arrival. The recourse of an algorithm is the largest number of insertions and deletions that it makes to the reported set at a single arrival. For every ε>0ε>0, we give an algorithm with recourse O(ε−2)O(ε^{-2}) whose reported set has, at every time, expected value at least 1/4−ε1/4-ε times the largest value of a feasible set of arrived elements. The algorithm evaluates the function polynomially often, and only on sets of arrived elements. We also show that no algorithm with constant recourse achieves a ratio above 1/41/4, even if it knows the function and the arrival order in advance and has unlimited computation, and that any fixed ratio above 1/41/4 requires recourse that grows as a positive power of the cardinality budget. Thus 1/41/4 is the optimal limiting ratio with constant recourse. The previous best ratio with constant recourse was 3−22≈0.1723-2\sqrt2\approx0.172. Our algorithm assigns selection probabilities of at most one half and maintains, as elements arrive, an inequality bounding the value of every feasible set by a multiple of the expected value of a random set drawn with these probabilities; the reported set moves to a rounding of these probabilities through gradual replacements. The upper bound uses a weighted directed graph whose vertices arrive in groups of decreasing sizes.
Nov 13, 2026

OverclusterDRG: a Deterministic, LP-Free Heuristic for Robust kk-Center

The kk-center problem is a fundamental formulation for metric clustering. However, its min-max objective is highly sensitive to outliers, motivating the Robust kk-Center (RkkC) formulation which permits excluding up to zz points as outliers. Existing algorithms for RkkC suffer from scalability issues: LP rounding relies on fractional relaxations that scale poorly, known combinatorial approximation algorithms are computationally expensive due to radius guessing, and scalable randomized heuristics require exponential trial multipliers to guarantee success. We present OverclusterDRG, a deterministic, LP-free heuristic for RkkC. The algorithm leverages the theoretical insight of farthest-point oversampling -- adding exactly zz extra candidates to the center set to absorb outliers -- followed by a forward-greedy initialization and a 11-swap local search. Evaluations across real-world datasets show that OverclusterDRG attains a mean approximation ratio of 1.147 against fractional LP lower bounds on the UCI Adult dataset, outperforming state-of-the-art baselines in both clustering quality and speed. By avoiding subset-guessing and exponential trial multipliers, it scales smoothly to n=105n=10^5 points where LP solvers and theoretical algorithms become intractable.
Nov 12, 2026

Informative Path Planning with Gaussian Processes: Error Bounds, Algorithms, and Benchmarks

Accurate environmental monitoring relies on Informative Path Planning (IPP) to deploy autonomous systems that maximize information gain. While Gaussian Processes (GPs) provide a robust mathematical foundation for modeling the environment, contemporary IPP approaches remain hindered by heuristic operational constraints and the lack of simultaneous theoretical guarantees for worst-case estimation error and approximation quality. Rather than introducing yet another heuristic, this paper presents a rigorous theoretical analysis of existing error bounds and algorithms to further develop the mathematical foundation for IPP. By evaluating probabilistic and deterministic bounds on reconstruction error, we establish that predictive variance is the theoretically ideal optimization objective for GP-based IPP. Furthermore, we analyze GreedyCover, a recent approach for optimizing predictive variance, and demonstrate that its near-optimal approximation guarantee matches the fundamental hardness-of-approximation limit for the problem. Comprehensive benchmarking confirms that this approach delivers superior estimation accuracy and computational efficiency compared to prominent information-theoretic objectives and optimization methods used in IPP. Finally, this theoretical analysis establishes a rigorous, near-optimal foundation for discrete offline IPP under bounded uncertainty constraints, offering clear and principled guidance for future work in continuous-space and online formulations.
Nov 11, 2026

Sparse PCA with Overlapping Supports: NP-Hardness and an FPTAS

In sparse principal component analysis (SPCA) with several components, each must be sparse and all must be pairwise orthogonal. When the supports of the components overlap, these two requirements interact. For a covariance matrix of fixed rank, polynomial-time algorithms with optimality or approximation guarantees are known for one component, and for several components with disjoint supports or with a common support. We study the general model, with individual sparsity constants and arbitrary support overlaps. We are given a rational n×rn\times r matrix RR and dd sparsity constants si≤ns_i \le n, and the goal is to find an n×dn\times d matrix XX with orthonormal columns that maximizes ∥R⊤X∥F2\|R^\top X\|_F^2, such that column ii has at most sis_i non-zero entries. Here RR⊤RR^\top plays the role of the covariance matrix and has rank at most rr. We show that SPCA is NP-hard even when r=d=2r = d = 2, but admits a fully polynomial-time approximation scheme (FPTAS) when rr and dd are fixed. The returned solution has exactly orthonormal columns, and its entries are real algebraic numbers in an exact representation. For fixed εε, the number of steps of the algorithm is linear in nn up to a polylogarithmic factor. Our approach reduces SPCA to a sparse version of the orthogonal Procrustes problem, that is, to maximizing a linear function over the feasible region of SPCA. We show that this problem is NP-hard even for d=2d = 2, and we give an FPTAS for it when dd is fixed. This FPTAS combines approximate dynamic programming over the rows, two-column updates that restore exact orthogonality, and an exact computation of the few variables for which these updates are not available.
Nov 11, 2026

Tokenization: Hardness and Bicriteria Approximation Algorithms

We study Binary Tokenization: given a corpus of binary strings over {0,1}\{0,1\} and a vocabulary budget KK, select at most KK substrings (called vocabulary) to minimize the total number of tokens needed to represent the corpus. The primitive symbols 00 and 11 are always available, and each document must be segmented separately. Letting nn denote the total corpus length and MM for the maximum document length, we prove that, for every fixed ε∈(0,1)\varepsilon\in(0,1), Binary Tokenization problem does not have polynomial-time n1−εn^{1-\varepsilon}-approximation algorithms unless P=NP\mathsf{P}=\mathsf{NP}. To complement the hardness result, we give a polynomial-time (γ,γ)(γ,γ)-bicriteria algorithm, with γ=Mlog⁡nγ= \sqrt{M}\log n: The algorithm outputs a vocabulary of size at most γKγK with number of tokens at most γOPTKγ{\rm OPT}_K, where OPTK{\rm OPT}_K is the optimal number of tokens under the original budget KK. We also study a storage-budget variant, in which the sum of the selected substrings' lengths is bounded by BB. For 2≤B<n2\le B<n, we obtain an (O(log⁡nlog⁡B),O(log⁡nlog⁡B))(O(\log n\log B),O(\log n\log B))-bicriteria approximation algorithm.
Nov 10, 2026

Pair-Merge Tokenisation Is Hard to Approximate on Binary Strings and Strongly NP-Hard on Unary Datasets

Tokenisers such as Byte-Pair Encoding (BPE) shorten text by repeatedly merging an adjacent pair of symbols into a new one; fewer tokens mean less computation. We ask whether an efficient algorithm can choose kk merges that leave a string of length nn almost as short as possible; doing nothing is already within a factor nn. We prove that, unless P = NP, no polynomial-time algorithm comes within a factor c n/log⁡nc\,n/\log n, for some constant c>0c>0, already for one binary string and for BPE-style merges that replace every occurrence. The key idea is that kk merges form a grammar with kk rules: a vertex-cover gap becomes a grammar-size gap, which we amplify with relabelled copies, encode in binary and realise with explicit merges. For merges that may skip occurrences, a simple algorithm achieves O(n/log⁡log⁡n)O(n/\log\log n), and no Karp reduction can prove hardness beyond order n/log⁡nn/\log n unless coNP ⊆\subseteq NP/poly. Over a one-letter alphabet, both tokenisation problems left open by Kastreva et al. are strongly NP-complete on datasets with repeated strings.
Nov 9, 2026

Beyond the First Hit: Towards Tight Guarantees for kk-means++

Let RkR_k be the worst-case ratio between the expected cost of the kk seeds chosen by kk-means++ and the optimal kk-means cost. In their seminal paper introducing kk-means++, Arthur and Vassilvitskii (SODA 2007) showed that 2ln⁡k≤Rk≤8(ln⁡k+2)2\ln k\le R_k\le8(\ln k+2), and Makarychev, Reddy and Shan (NeurIPS 2020) improved the upper bound to 5(ln⁡k+2)5(\ln k+2). We prove Rk≤1163233+2.108 Hk−2R_k\le\frac{1163}{233}+2.108\,H_{k-2} for every k≥3k\ge3 by a computer-assisted argument, and Rk≤5+2.3139 Hk−2R_k\le5+2.3139\,H_{k-2} for every k≥2k\ge2 by a short analytic argument; here HjH_j is the jjth harmonic number. Since Hk−2≤1+ln⁡kH_{k-2}\le1+\ln k, this lowers the leading coefficient of ln⁡k\ln k from 55 to 2.1082.108. We also determine R2=5R_2=5 and R3=185/32R_3=185/32 exactly; both are suprema that are approached but not attained. On the lower side we prove Rk≥2(1+Hk−1)R_k\ge2(1+H_{k-1}) for every kk, and give a second family of lower bounds that is larger than this for 2≤k≤182\le k\le18. Previous analyses bound the expected cost of a cluster just after it is first sampled by a constant times its optimal cost, and then charge that cost for the rest of the run. We instead track how a cluster's cost evolves after its first hit: a cluster left with a large residual cost is likely to be sampled again before it accumulates much of the logarithmic charge, and each repeat repairs it.
Nov 8, 2026

Fast Approximate ℓp\ell_p Chamfer Distance via Lopsided Embeddings and Structured JL

For two dd-dimensional point sets A,BA, B of size nn, the Chamfer distance from AA to BB is defined as CH(A,B)=∑a∈Amin⁡b∈Bdist(a,b)\text{CH}(A,B)=\sum_{a \in A} \min_{b \in B} \mathsf{dist}(a, b), where dist\mathsf{dist} is some underlying distance measure. We present efficient algorithms for approximating the Chamfer distance under the ℓp\ell_p norm for 1<p≤21 < p \le 2. For the general case 1<p<21 < p < 2, we utilize lopsided ℓp\ell_p to ℓ1\ell_1 embeddings with weak guarantees. We show that they are sufficient for preserving the Chamfer distance. In the high-dimensional regime, we use Fast Matrix Multiplication techniques to speed up the lopsided embeddings. These lead to O(nd⋅poly(log⁡log⁡n,log⁡(1/ε))/ε2)O(nd\cdot \mathrm{poly}(\log \log n, \log(1/\varepsilon))/\varepsilon^2) total time. For the specific Euclidean case (p=2p=2), we leverage the Fast Johnson-Lindenstrauss Transform based on Toeplitz matrices and re-analyze the previous ℓ1\ell_1-specific Chamfer algorithm in ℓ2\ell_2. These achieve a runtime matching the recent state-of-the-art ℓ1\ell_1 result of O(nd(log⁡log⁡n+log⁡(1/ε))/ε2)O(nd(\log \log n + \log (1/\varepsilon))/\varepsilon^2), improving upon the previous O(ndlog⁡n/ε2)O(nd \log n/\varepsilon^2) bound for ℓ2\ell_2. We also give additional results for the angular distance and upper and lower bounds in the streaming setting.
Nov 8, 2026

Optimal Polynomial-Query Approximation for Consistent Submodular Maximization with Short Lookahead

Elements arrive one at a time, and after each arrival an algorithm holds a set of at most kk arrived elements. Its goal is a held set whose value under a monotone submodular function is close to the best value that kk arrived elements can achieve. The recourse of an update is the number of elements inserted into or removed from the held set, and we require it to be bounded independently of kk and of the number nn of arrivals. With evaluations only on sets of arrived elements and polynomially many of them, the best ratio a randomized algorithm can achieve is 2−2≈0.58582-\sqrt{2}\approx0.5858. We show that seeing future arrivals raises the best ratio for polynomially many evaluations to 1−1/e≈0.63211-1/e\approx0.6321, for deterministic and for randomized algorithms; no algorithm with polynomially many evaluations exceeds 1−1/e1-1/e, even when all elements are available at once. For every ε>0\varepsilon>0, a deterministic algorithm that sees the next ⌈εk/3⌉\lceil\varepsilon k/3\rceil arrivals keeps a set of value at least 1−1/e−ε1-1/e-\varepsilon times the optimum at every time, changes O(ε−3)O(\varepsilon^{-3}) elements per arrival and makes (n+1)O(ε−2)(n+1)^{O(\varepsilon^{-2})} evaluations. With the whole arrival sequence known in advance, a deterministic algorithm attains the same ratio with O(ε−2)O(\varepsilon^{-2}) changes per arrival. A randomized algorithm with the same short lookahead makes O(n2k)O(n^2k) evaluations, changes O(ε−2)O(\varepsilon^{-2}) elements per arrival, and attains the same ratio in expectation at each fixed time. The main tool is a greedy algorithm with an explicit guarantee for each of its partial solutions combined with each initial segment of the known future arrivals. A second tool moves between two such solutions one element at a time while keeping the value high, and the deterministic algorithm times each move using upper bounds on the optimum from failed searches.
Nov 5, 2026

Greedy Byte-Pair Encoding Achieves 0.391 of the Optimum, Past the One-Third Barrier for Packing-Based Analyses

Byte-Pair Encoding (BPE) builds most language-model tokenisers by repeatedly merging a most frequent adjacent pair of symbols. How much shortening can this greedy rule lose against the best kk merges? Kozma and Voderholzer proved that greedy achieves at least one third of the optimal shortening; the best known upper bound is (1−e−2)/2≈0.432(1-e^{-2})/2\approx 0.432. We show that one third is a barrier for packing-based analyses, which see the optimum only through a pair packing, and we prove that greedy achieves at least 0.3910.391 of the optimum on every input, with any tie-breaking. The key idea is rule determinism: all copies of a rule of the optimum spell the same letters, so when one greedy replacement destroys three of the optimum's merge points, half a unit can be refunded on each side. A weaker bound, 0.3740.374, has a short proof that needs no computer; 0.3910.391 adds a certificate in exact arithmetic. We also show that the worst-case ratio is exactly 3/43/4 for two merges and at most 7/127/12 for three.
Nov 4, 2026

Consistent Submodular Maximization with Full Foresight

Online algorithms with bounded recourse face three intertwined obstacles: uncertainty about the future, computational limits, and a limited budget for changes. We ask a fundamental question that separates consistency from the other two: what does solution stability cost when the entire future is known and computation is unlimited? We answer this question for monotone submodular maximization, where an algorithm must maintain a solution of at most kk arrived elements, with a constant number of changes per step. We determine the optimal approximation thresholds: 3/43/4 for deterministic algorithms and ξ⋆≈0.7942ξ^\star \approx 0.7942 for randomized algorithms. For every ε>0\varepsilon>0, we get within ε\varepsilon of these thresholds with worst-case recourse polynomial in 1/ε1/\varepsilon, independent of kk and the stream length. We prove matching impossibility results even for coverage functions. We attain the sharp bounds by optimally balancing two opposing forces: preparing for future arrivals and protecting the current solution. For randomized algorithms, we use addition robustness against prefixes of the known future, which we analyze tightly via an interval-selection problem. For deterministic algorithms, we introduce certificates, paths in a fractional relaxation that maintain high value, which we round into an update schedule.
Nov 4, 2026

Improved approximation algorithms for capacitated cluster editing

We study the minimum-disagreement cluster editing problem that, from a complete edge-signed graph, where a positive edge represents two vertices agreeing to each other while a negative represents a disagreement, constructs disjoint cliques of upper bounded size such that the total number of negative edges inside cliques and positive edges outside cliques is minimized. When the sizes of the candidate cliques are unbounded, the problem is NP-hard and APX-hard, and many approximation algorithms with improving ratios have been proposed in the literature and the state-of-the-art approximation ratio of α=1.3865+εα= 1.3865 + ε. The capacitated variant, in which the candidate cliques have sizes no greater than a given kk, is less studied and the best approximation ratio is 5.375.37. In this paper, we study the latter problem. We first present a downsizing procedure that achieves an approximation ratio of αk=2α+1α_k = 2 α+ 1, based on any αα-approximation algorithm for the uncapacitated problem. Secondly, we propose a hybrid of cluster-LP sampling and pivoting and show that for every fractional capacitated cluster-LP solution of cost LL, the hybrid using ordinary pivoting has an expected cost at most 95L+110\OPTk\frac 95 L + \frac 1{10} \OPT_k, and the hybrid using conditional pivoting has an expected cost at most 306203L+50203\OPTk\frac {306}{203} L + \frac {50}{203} \OPT_k. A cardinality-constrained adaptation of the approximate dual-separation framework of García-Soriano and Schohn supplies the required fractional solution and yields a randomized (1.9+ε)(1.9 + ε)-approximation algorithm and a randomized (1.7537+ε)(1.7537 + ε)-approximation algorithm, respectively.
Oct 28, 2026

On Worst-Case Guarantees for Graph-Based Nearest-Neighbor Search

Graph-based nearest neighbor search algorithms like HNSW, DiskANN, NSG, and others have surged in popularity in recent years due to their excellent empirical performance in comparison to space-partitioning methods like IVF data structures and Locality Sensitive Hashing (LSH). However, in contrast to LSH and related methods, obtaining strong worst-case theoretical guarantees for graph-based search has proven challenging. In this paper, we prove a strong lower bound that helps explain the lack of progress towards such guarantees. We show that no standard graph-based method (any that runs a variant of greedy search on a flat or hierarchical graph) can achieve sublinear query time for approximate nearest neighbor search in Euclidean space, even for an arbitrarily large approximation factor. On the other hand, we prove that sublinear query time is possible if we allow for Steiner points in the search graph. We obtain bounds comparable to LSH, showing e.g., that graph-based search with Steiner points can solve cc-approximate nearest neighbor search in Euclidean space with query time O~(n1/(c−1))\tilde{O}(n^{1/(c-1)}). We complement this result with initial experiments exploring how Steiner points can be incorporated into practical graph-based methods.
Oct 18, 2026

Breaking the 1/3 Barrier for Approximate Nash Equilibria in Symmetric Bimatrix Games

We give the first unconditional family of polynomial-time algorithms that breaks the 1/31/3 approximation barrier for symmetric bimatrix games. For every fixed δ>0δ>0, an algorithm in this family computes a symmetric (1−1/2+δ)(1-1/\sqrt{2}+δ)-approximate Nash equilibrium, improving on the previous best guarantee of (1/3+δ)(1/3+δ) due to Kontogiannis and Spirakis [2011].
Oct 18, 2026

When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?

Weakly submodular maximization finds numerous applications in machine learning, data mining and statistics. In particular, under a cardinality constraint, the standard greedy algorithm is known to attain the tight (1−e−γ)(1-e^{-γ})-approximation guarantee, where γγ denotes the submodularity ratio. However, when considering general matroid constraints, how well standard greedy can perform has remained a longstanding open question. In this paper, we resolve this question by studying the worst-case approximation guarantee Rgr(γ,r)R_{\mathrm{gr}}(γ,r) of standard forward greedy, where rr is the rank of matroid. Specifically, our first contribution is the following refined lower bound \begin{equation*} R_{gr}(γ,r)\ge \max\left{ \fracγ{r}, \frac{γ^2} {B_γ+\sqrt{γ(r-1)}}, \frac{γ^{r+1}} {2-γ+γ^{r+1}}, \frac{γ^2} {14\left(B_γ+\sqrt{γ(1-γ)(r-1)}\right)} \right}, \end{equation*} where Bγ≜2−γ+γ2B_γ\triangleq2-γ+γ^2. This lower bound not only strictly improves upon the previous guarantee of 0.4γ2/(1+γr)0.4γ^2/(1+\sqrt{γr}), but also can recover the classical 1/21/2-approximation guarantee at γ=1γ=1. Subsequently, a corresponding upper bound is established for Rgr(γ,r)R_{\mathrm{gr}}(γ,r), namely, \begin{equation}\label{eq_upper_abstract} R_{gr}(γ,r) \le\min\left{\frac{1}{2},20\max\left{\fracγ{r}, \frac{γ^2}{B_γ+ \sqrt{γ(1-γ)(r-1)}}\right}\right}. \end{equation} For every fixed γ∈(0,1)γ\in(0,1), this equation effectively sharpens the recent Oγ(1/log⁡(n−1))O_γ(1/\log(n-1)) upper bound to Oγ(r−1/2)O_γ(r^{-1/2}), where nn is the size of ground set. Putting all these results together, we eventually can obtain Rgr(γ,r)=Θ(max⁡{γr,γ21+γ(1−γ)r}).R_{gr}(γ,r) = Θ\left( \max\left\{\fracγ{r}, \frac{γ^2} {1+\sqrt{γ(1-γ)r}}\right\} \right).
Oct 16, 2026

Budgeted Bayesian Bandits for Future Utilization

The multi-armed bandit problem models the trade-off between exploration and exploitation. In this paper, we study the variant where exploration has a hard budget and precedes exploitation. Prior guarantees include a 1/3 approximation by Guha and Munagala using Lagrangian duality, and a 4/27 approximation by Ma against a primal linear programming relaxation for a more general model. We show that the analyses of both algorithms are tight, even when their relaxations are asymptotically exact. We provide a different efficient algorithm that achieves a 0.43 approximation. We then provide an efficient algorithm whose guarantee approaches 1-e^{-1} approx 0.63 for bounded exchangeable reward observations in a non-vanishing regime, which is asymptotically tight against natural linear programming relaxations. The technique also gives certificates for stopping sequential model evaluation.
Oct 14, 2026

FPTAS for Polygonal Multi-Robot Motion Planning

We study multi-robot motion planning in a polygonal environment with polygonal robots. The setting of the problem consists of a polygonal domain W\mathcal{W} with nn vertices and kk robots R1,…,RkR_1,\dots,R_k translating in W\mathcal{W} each of which is represented by a polygon of constant complexity. Given a source configuration s\mathbf{s} and a target configuration t\mathbf{t} of the robots in W\mathcal{W}, the goal of the problem is to find a collision-free motion plan from s\mathbf{s} to t\mathbf{t} that is shortest with respect to some cost function. We present the first fully polynomial-time approximation schemes (FPTAS) for motion planning with any fixed number kk of robots, under the min-sum objective, the min-max objective, and the min-makespan objective. Here, the min-sum variant aims to minimize the total traveling distance of all robots, the min-max variant aims to minimize the maximum traveling distance of a single robot, and the min-makespan variant aims to minimize the total time cost under the assumption that all robots move with a maximum speed 11. The algorithm directly generalizes to the problem in any fixed dimension dd, with a polytope environment and polytope robots. Our result settles an open question of Agarwal, Halperin, Sharir, Steiger [SODA'24] and Agarwal, Holmgren, Steiger [SODA'26], who gave an FPTAS for k=2k=2 unit-square robots and a bicriteria-approximation algorithm for a fixed number kk of unit-square or unit-disk robots, respectively. Compared to the previous results, our algorithm is substantially simpler.
Oct 14, 2026

Geometric Kernel Diversity: An Axiomatic Diversity Measure in Euclidean Space

Quantifying the diversity of a set of objects is a fundamental problem in machine learning and statistics. Mironov and Prokhorenkova (2025) recently showed that three axioms-monotonicity, uniqueness, and continuity-are crucial for a reliable diversity measure and that none of the standard metrics in the literature satisfy all three. They also constructed two measures that do satisfy the axioms, but both are NP-hard to compute, leaving open the question of whether efficient axiomatic diversity measures can exist. We study a Euclidean-restricted version of this question. We introduce Geometric Kernel Diversity (GKD), which associates a radial kernel solid with each point and measures the volume of their union. We show that canonical GKD satisfies all three Mironov-Prokhorenkova axioms on Euclidean-realizable inputs. For canonical GKD, we give exact polynomial-time algorithms in dimensions d≤3d \le 3. In arbitrary dimensions, we give a randomized algorithm that returns a (1±ε)(1 \pm \varepsilon)-approximation with probability at least 1−δ1-δ in time O(ndε2log⁡2δ)O \left(\frac{nd}{\varepsilon^2}\log\frac{2}δ\right) for nn points. The axiomatic guarantee applies to exact canonical GKD; the randomized algorithm approximates this deterministic quantity. We further show that the two diversity measures of Mironov and Prokhorenkova (2025) remain NP-hard on Euclidean-realizable inputs and, unless NP=RP\mathrm{NP} = \mathrm{RP}, admit no FPRAS even on this restricted domain.
Oct 13, 2026

Approximating Optimal Policies in Heterogeneous Asynchronous Multi-player Bandits

Motivated by applications to cognitive radio networks, multi-player multi-armed bandits (MMAB) have attracted considerable attention in recent years. The asynchronous variant, in which players are active only at a fraction of timesteps, better reflects real-world decentralized networks, where devices are not permanently active. Despite its practical relevance, this setting remains relatively understudied. Existing work on asynchronous MMAB has focused on homogeneous players, who share the same activation probability, a setting in which the optimal centralized allocation can be easily characterized. In contrast, efficiently computing the optimal allocation in the heterogeneous setting, where players have different activation probabilities, has remained an open problem. In this work, we investigate this problem and first establish its NP-hardness. We then turn to the greedy algorithm, which runs in polynomial time, and prove that it achieves a 1e\frac{1}{e}-approximation of the optimal allocation. Furthermore, when players are processed in decreasing order of their activation probabilities, the approximation guarantee improves to 1e\frac{1}{\sqrt{e}}. Overall, our results establish the greedy algorithm as an efficient approximation to the optimal allocation, providing a practical oracle baseline for the design of online algorithms for heterogeneous asynchronous multi-player bandits.
Oct 11, 2026

Improving the Bounds on Approximating Weighted Maximin Share for Chores

We investigate the problem of allocating indivisible chores among agents with arbitrary positive weights and additive nonnegative cost functions. An allocation is said to be αα-weighted-maximin-share (WMMS) fair if the cost incurred by each agent is at most αα times her weighted maximin share. We establish that every instance admits a 4.1242345284.124234528-WMMS allocation. Moreover, for instances in which all weights and costs are rational numbers represented in binary, we give an algorithm that computes a 4.124244.12424-WMMS allocation in time polynomial in the number of agents, the number of chores, and the total binary encoding length of the input. Complementing these upper bounds, we construct a family of instances with strictly positive, identically ordered costs for which the optimal WMMS approximation factors converge to ee. Together, our results substantially narrow the previously best-known gap of [2,12][2,12] established by Li et al.~\cite{LWX26} to [e,4.12424][e,4.12424].
Oct 7, 2026

Minimizing Cumulative Envy in Allocating a Sequence of Items

We study temporal fair division with indivisible goods that arrive sequentially and must be allocated irrevocably. In contrast to the usual online model, we assume that valuations and future arrivals are known in advance, and ask how unfairness evolves during the process. We introduce cumulative maximum envy: the sum, over all rounds, of the maximum pairwise envy at that round. Equivalently, this is the area under the worst-envy curve, and it captures both the magnitude and the duration of envy. For a fixed arrival order, we show that the corresponding decision problem is strongly NP-complete and that minimizing this objective admits no constant-factor approximation unless P = NP, even under identical valuations and even under binary valuations. We complement these hardness results with a dynamic program that gives pseudopolynomial-time solvability for a constant number of agents, polynomial-time algorithms in further restricted settings, and an FPTAS for fixed nn under identical integer valuations. We then study a sequencing variant where the algorithm may choose the arrival order. This variant remains NP-complete even for two agents with identical valuations; however, a simple greedy algorithm achieves a 3/23/2-approximation for n=2n=2 agents, an n/(n−1)n/(n-1)-approximation for any number of agents, and an additive guarantee depending on the maximum value of any good.
Oct 4, 2026

Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations

We study the problem of computing an allocation of indivisible items that maximizes egalitarian welfare, i.e., the utility of the worst-off agent, when agents' item values or marginal values belong to a small set. For additive valuations with values in {p,q}\{p,q\}, where q>p>0q>p>0 and gcd⁡(p,q)=1\gcd(p,q)=1, we give a polynomial-time algorithm when p=2p=2 and prove constant-gap hardness when p≥3p\geq3, already with exactly three high-valued goods per agent. We also give an 3/2\sqrt{3/2}-approximation for common positive bi-valued additive valuations. For mixed additive valuations in {−p,0,c}\{-p,0,c\}, where p∈{1,2}p\in\{1,2\} and cc is a positive integer, a reduction to maximum-weight perfect matching resolves the conjectured tractability of {−2,0,c}\{-2,0,c\}-valuations. For submodular valuations with marginals in {−2,0,c}\{-2,0,c\}, where cc is odd, we establish an exact unit-gap hardness result and exponential value-query lower bounds, even when all but one agent are additive. Finally, for {−1,0,1}\{-1,0,1\}-submodular valuations, we prove that no finite multiplicative approximation exists unless \p=\np\p=\np. Together, our results resolve open questions and provide a complete picture of the computational complexity of max-min allocation with ternary valuations.
Oct 3, 2026

Maximizing pp-Mean Social Welfare in the High-Multiplicity Setting: Few Agent Types and Few Item Types

The pp-mean welfare objective unifies several classical social welfare criteria for the allocation of indivisible goods. We study its maximization under additive nonnegative utilities when item and agent multiplicities are encoded in binary. For every fixed finite rational p<1p<1, p≠0p\neq0, we show that the problem is NP\mathsf{NP}-hard with only two item types. Nash welfare (p=0p=0) and egalitarian welfare (p=−∞p=-\infty) are NP-hard with three item types. These results hold both for computing an optimal allocation and for rational-threshold decision, and the utilities and threshold can be required to be positive integers. We also show that maximizing pp-mean social welfare is strongly NP-hard with one agent type and an unrestricted number of item types, for every fixed finite rational p<1p<1 and for p=−∞p=-\infty. A quantitative gap in this reduction rules out an FPTAS in the latter setting unless P=NP\mathsf{P}=\mathsf{NP}. On the positive side, for a fixed number of item types and an arbitrary number of agent types, we give an FPTAS for every fixed p∈Q∪{−∞}p\in\mathbb Q\cup\{-\infty\}. Its running time is polynomial in the compact input length and in 1/ε1/\varepsilon, and it returns a compressed allocation. For a fixed number of agent types and an unrestricted number of item types, we give a PTAS for every fixed finite rational p<1p<1, also in the fully compact model. We further give explicit compact-model proofs of the classical exact allocation algorithms for one item type, and for egalitarian welfare with two item types. These results essentially settle the complexity and approximability of pp-mean welfare maximization with few item types and/or few agent types, leaving only the exact complexity of Nash welfare maximization with two item types unresolved in the small-item-type classification.
Oct 2, 2026

Geometry-Dependent Approximation for Non-Monotone kk-Submodular Maximization

We study the maximization of a nonnegative kk-submodular function, not assumed monotone, in which each of nn elements receives one of k≥2k\ge2 labels or stays unselected and the selected elements must satisfy a constraint. For a compact convex down-closed region P⊆[0,1]nP\subseteq[0,1]^n of fractional selection vectors, the diagonal level ζ(P)=max⁡{t∈[0,1]:t(1,…,1)∈P}ζ(P)=\max\{t\in[0,1]:t(1,\ldots,1)\in P\} is the largest selection probability that can be given to all elements at once; it equals r/nr/n for a uniform matroid of rank rr, and ζ(P)=1ζ(P)=1 means that the constraint is vacuous. We give approximation coefficients that increase continuously with ζζ. They come from one inequality for the multilinear extension of the objective: the algorithm computes an action without querying the objective, and objective feedback gives a comparator-independent update direction. For k≥3k\ge3, feasibility of the action reduces to three polynomial inequalities in one variable; for k=2k=2 the profile is closed form. At ζ=0ζ=0 the coefficients are 0.4456…0.4456\ldots for k=2k=2 and 0.4541…0.4541\ldots for every k≥3k\ge3. For every finite k≥3k\ge3 they reach 1/21/2 above an explicit level, which is 0.4026…0.4026\ldots for k=3,4,5k=3,4,5, and at ζ=1ζ=1 they reach 1/21/2 for k=2k=2, (17−3)/2(\sqrt{17}-3)/2 for k=3,4k=3,4, and k/(2k−1)k/(2k-1) for k≥5k\ge5. Online linear optimization gives O(T)O(\sqrt T) approximate regret, with gradient feedback or with value queries made after each action. The coefficients carry over to matroids, with expected and high-probability guarantees, and to any fixed number of knapsacks: the zero-level coefficients hold on every instance, and the larger ones when items are small or when prefix enumeration keeps the diagonal level on one branch. For one budget the enumeration exponent is O(1/ε)O(1/\varepsilon).
Oct 1, 2026

Streaming algorithms for robust max-min diversification

Given a set of nn points XX in a metric space and an integer kk, max-min diversification aims to select kk points of XX maximizing their minimum pairwise distance. This objective function is however highly vulnerable to noisy points. In[Amagata, AAAI23], a robust formulation is proposed which addresses this vulnerability by excluding solutions containing any of zz outliers, defined as the zz points in XX with the largest nearest-neighbor distances. That paper also presents a coreset-based streaming algorithm for the new formulation, based on a suitable inlier-outlier separation assumption. However, we identify three shortcomings in the algorithm by [Amagata, AAAI23]: its coreset construction requires an offline computation over XX, which needs memory linear in nn, in stark contrast with the typical goals of stream processing; the one-pass procedure used to extract the solution from the coreset may return fewer than kk points (hence, an unfeasible solution) because it permanently discards points too far from the current solution; and its outlier-exclusion guarantee is only probabilistic and weakens as the coreset size shrinks. In contrast, we present a deterministic coreset-based algorithm that, under a natural inlier-outlier separation assumption (similar to the one used in [Amagata, AAAI23]), returns exactly kk inliers which are a (2+ε)(2+\varepsilon)-approximate solution, for any ε>0\varepsilon>0, thus only ε\varepsilon above the best polynomial-time sequential approximation, even without outliers. Its one-pass streaming implementation adapts obliviously to the dataset's doubling dimension DD and, for wide ranges of kk, zz, ε\varepsilon, and DD, it uses memory independent of nn. For sufficiently long streams, its amortized update time is proportional to the coreset size, thus also independent of nn.
Sep 30, 2026

Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon

Neural combinatorial optimization typically assumes a centralized solver that reads the whole instance. We study the opposite: combinatorial optimization under a hard information horizon, where every node commits to its share of a global solution seeing only its kk-hop neighborhood, and those commitments must compose into a globally feasible solution. We formalize this as local set cover and instantiate it on weighted multipoint relay (MPR) selection, the NP-hard 2-hop covering problem of the Optimized Link State Routing Protocol version 2 (OLSRv2) routing protocol (RFC7181), whose horizon is imposed by the protocol, not chosen by the modeler. We prove two results. Any deterministic selector whose horizon is one hop short must either fail coverage or land a factor ΔΔ from optimal, and an LL-layer graph neural network (GNN) read out at the deciding node is exactly an LL-hop selector, so capacity cannot buy back radius. Conversely, at the horizon a \ac{GNN} of depth O(Δ)O(Δ) reproduces the RFC7181 covering greedy, and at width O(cmax⁡Δ)O(c_{\max}Δ) its metric-aware weighted analogue, inheriting the (1+ln⁡Δ2)(1+\lnΔ_2)-approximation in both cases. Empirically, a 3-layer \ac{GATv2} with a coverage-completing decoder, behavior-cloned from the CP-SAT optimum, reaches cost/opt=1.030±0.001\text{cost}/\text{opt}=1.030\pm0.001 against greedy's 1.1381.138, closing 79.1%79.1\% of the gap at 100%100\% coverage. Restricting the same learner to one hop, on identical instances with the same decoder and demonstrations, collapses it to 1.3441.344, far worse than greedy. Two transfer checks target real-world networks. OLSRv2's unmodified selection code matches our cardinality greedy on 200/200200/200 unit-cost instances, and on 40,30840{,}308 instances of real battalion mobility the frozen model closes 48%48\% of the gap at full coverage. The information horizon, not the model capacity, is the most significant variable.
Sep 28, 2026

Reverse Sequential Proportional Approval Voting Rule: Proportionality and Approximation Guarantees

We study the Reverse Sequential Proportional Approval Voting Rule (RevSeqPAV) in approval-based committee elections. Despite its historical prominence and practical use, its properties and guarantees are much less understood than those of Sequential PAV. We analyze it along two dimensions: proportional representation (measured by Extended Justified Representation, its approximations, and proportionality degree) and approximation of the maximum PAV score of instances. We first establish strong negative results for general, unrestricted election instances and then identify settings in which the rule provides meaningful fairness and optimization guarantees.
Sep 23, 2026

Contingent Exposure Routing for Financial AI: Outage Risk and the Cost of Indivisible Decisions

Model failover restores availability, but changes which financial institutions share decision errors. We formulate outage-contingent routing through a local market-impact response matrix and study expected squared price displacement. A symmetric construction shows that a shared backup can leave an order-one concentration floor as the number of primary endpoints grows, while balanced fallback risk decreases inversely with the surviving endpoint count. For indivisible decisions, we derive the exact second moment of independent randomized routing and an effective-exposure granularity that determines its gap from fractional allocation. Conditional-expectation rounding gives a finite-agent bound without coupled quotas; a separate swap procedure preserves endpoint counts and is assessed against dual lower bounds. Across 60 synthetic portfolio networks and 11,340 scenario evaluations, the latter reduces risk by 6.57% and 10.53% for single and double endpoint removals at the central feedback setting with independent errors. A replay of 1,024 recorded API responses on constructed rebalancing tasks gives a smaller held-out reduction of 3.30% (paired bootstrap interval 2.07--4.57%). Strongly aligned errors, inferior endpoints, and indivisibility limit diversification. The contribution is an auditable routing stress test and implementation analysis, not an estimate of real-market crash probabilities.
Sep 21, 2026

Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids

Over the past decade, a growing body of research has shown that γγ-weak submodularity broadly arises in numerous subset selection tasks, including feature selection, neural network pruning, and video summarization. Despite its prevalence, maximizing a γγ-weakly submodular function subject to a general matroid constraint remains challenging. To date, the only known approximation guarantee is the conservative (1+1/γ)−2(1+1/γ)^{-2} factor established by \citet{chen2018weakly}. To improve upon this result, this paper proposes a novel algorithm called \MGPE, which repeatedly performs maximum-gain local exchanges through careful control of a non-homogeneous Poisson clock, and proves that this \MGPE\ can attain an approximation ratio arbitrarily close to ργ=1−(γ/(2−γ))γ22(1−γ)ρ_γ=1-\left(γ/(2-γ)\right)^{ \frac{γ^2}{2(1-γ)} }. In sharp contrast to the previous guarantee, our obtained factor ργρ_γ not only strictly improves upon (1+1/γ)−2(1+1/γ)^{-2} for every γ∈(0,1]γ\in(0,1], but also can asymptotically approach the optimal (1−1/e)(1-1/e)-approximation for submodular maximization as γ→1γ\to1. Furthermore, we surprisingly find that when the matroid constraint reduces to a cardinality or the objective satisfies the stronger notion of αα-weak DR-submodularity, \MGPE\ can automatically recover the tight approximation ratios of 1−e−γ1-e^{-γ} and 1−e−α1-e^{-α}, respectively. Here, α∈(0,1]α\in(0,1] denotes the DR ratio.
Sep 19, 2026

A Horizon-slicing Approach to Minimum Obstacle Displacement Planning for Robot Navigation

In this paper, we investigate the Minimum Obstacle Displacement Planning problem from a robot motion planning perspective. The problem involves determining a feasible path to a goal location by displacing movable obstacles when no collision-free path initially exists. We show that this problem is computationally challenging and, in particular, NP-hard when obstacles are modeled as polygons in the plane. Besides an exact formulation of the minimum obstacle displacement problem generalizing other problems in the literature, and the associated optimal solution, this paper proposes an approximate solution that is less intensive from a computational standpoint, and differs from the optimal solution by a fraction of the optimal cost, being able to trade-off between path length and amount of obstacle displacements.