Anthony Wirth

AAMAS Conference 2026 Conference Paper

A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization

• Philip Cervenjak
• Junhao Gan
• Naonori Kakimura
• Seeun William Umboh
• Anthony Wirth

Connected Submodular Maximization (CSM) is a graph problem with important applications to wireless network deployment, path planning, epidemic outbreaks, and cancer genome studies. In CSM, we are given a graph 𝐺, a non-negative monotone submodular function 𝑓 on subsets of the vertex set of 𝐺, and an integer 𝑘. The goal is to select a tree in 𝐺, with 𝑘 edges, whose vertex set maximizes 𝑓. We also study the more general Directed and Directed Rooted variants of CSM (DCSM and DRCSM respectively). In both variants, 𝐺 is directed and the solution must be an out-tree in 𝐺, with 𝑘 edges, whose vertex set maximizes 𝑓; DRCSM further specifies a vertex to be the root of the selected out-tree. For CSM, several previous works have proposed polynomial time approximation algorithms; the state-of-the-art polynomial time algorithm achieves a Ω( 1 √ 𝑘 )-approximation. We can also parameterize the approximation factor by the radius of the optimal solution, denoted by 𝑟; the state-of-the-art polynomial time algorithm achieves a Ω(1 𝑟 )-approximation. In this paper, we improve on the state-of-the-art approximation factor for CSM with respect to 𝑟 as well as 𝑘, noting that 𝑟 ≤ 𝑘. We propose a polynomial time framework that, for (Directed) CSM, achieves a Ω(𝜀3 𝑟𝜀 )-approximation for every constant 𝜀 ∈ (0, 1]. For DRCSM, our framework achieves a Ω(𝛿𝜀3 𝑟𝜀 )-approximation that violates the size constraint by at most a factor of 1 + 𝛿 for every 𝛿 ∈ [1 𝑘, 1]. A key component of our framework is GreedyRadius, an algorithm for DRCSM that outputs a bicriteria approximation, i. e. , an approximate solution that violates the size constraint by at most some factor. GreedyRadius takes an algorithm with a bicriteria approximation factor in terms of𝑘 and outputs a solution This work is licensed under a Creative Commons Attribution International 4. 0 License. Proc. of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2026), C. Amato, L. Dennis, V. Mascardi, J. Thangarajah (eds.), May 25 – 29, 2026, Paphos, Cyprus. © 2026 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). https: //doi. org/10. 65109/IPZQ7320 with the same bicriteria approximation factor (up to constants) in termsof𝑟. Moreover, touseasasubroutineforDRCSM, wepropose the algorithm RecApprox-𝑑, which achieves a 1 𝑑+1-approximation that violates the size constraint by at most a factor of (𝑑 + 1)2𝑘 1 𝑑. RecApprox-𝑑 uses a recursive greedy strategy, with𝑑 denoting the number of levels of recursion used. This enables the dependence on 𝜀 in the approximation factors of our overall framework.

TCS Journal 2026 Journal Article

Lower bounds for approximate (& exact) k-Disjoint-Shortest-Paths

• Rajesh Chitnis
• Samuel Thomas
• Anthony Wirth

Given a graph G = ( V, E ) and a set T = { ( s i, t i ): 1 ≤ i ≤ k } ⊆ V × V of k pairs, the k-Vertex-Disjoint-Paths (resp. k-Edge-Disjoint-Paths) problem asks to determine whether there exist k pairwise vertex-disjoint (resp. edge-disjoint) paths P 1, P 2, …, P k in G such that, for each 1 ≤ i ≤ k, Pi connects si to ti. Both the edge-disjoint and vertex-disjoint versions in undirected graphs are famously known to be FPT (parameterized by k) due to the Graph Minor Theory of Robertson and Seymour. Eilam-Tzoreff [DAM ’98] introduced a variant, known as the k-Disjoint-Shortest-Paths problem, where each individual path is further required to be a shortest path connecting its pair. They showed that the k-Disjoint-Shortest-Paths problem is NP-complete on both directed and undirected graphs; this holds even if the graphs are planar and have unit edge lengths. We focus on four versions of the problem, corresponding to considering edge/vertex disjointness, and to considering directed/undirected graphs. Building on the reduction of Chitnis [SIDMA ’23] for k-Edge-Disjoint-Paths on planar DAGs, we obtain the following inapproximability lower bound for each of the four versions of k-Disjoint-Shortest-Paths on n-vertex graphs: Under the gap version of the Exponential Time Hypothesis (Gap-ETH), for each 0 < ϵ ≤ 1 2 there exists a constant δ > 0 such that there is no in f(k) · n δ · k -time algorithm for any computable function f that can distinguish between the case where all terminal pairs can be satisfied, and the case where at most ( 1 2 + ϵ ) · k pairs can be satisfied. We provide a single unified framework to obtain lower bounds for each of the four versions of k-Disjoint-Shortest-Paths. We are able to further strengthen our results by restricting the structure of the input graphs in the lower bound constructions as follows: Directed: The inapproximability lower bound for edge-disjoint (resp. vertex-disjoint) paths holds even if the input graph is a planar (resp. 1-planar) DAG with max in-degree and max out-degree at most 2. Undirected: The inapproximability lower bound for edge-disjoint (resp. vertex-disjoint) paths hold even if the input graph is planar (resp. 1-planar) and has max degree 4. The reductions outlined in this paper produce graphs in which half of the terminal pairs are trivially satisfiable, so any improvement of our ( 1 2 + ϵ ) inapproximability factor requires a different approach. As a byproduct of our reductions, we also show that the exact versions of each problem is W[1]-hard and give a f(k) · n o(k)-time lower bound for them under ETH. This exact lower bound shows that the n O(k)-time algorithms of Bérczi and Kobayashi [ESA ’17] for Directed-k-EDSP and Directed-k-VDSP are tight.

ICML Conference 2023 Conference Paper

Tight Data Access Bounds for Private Top-k Selection

• Hao Wu 0057
• Olga Ohrimenko
• Anthony Wirth

We study the top-$k$ selection problem under the differential privacy model: $m$ items are rated according to votes of a set of clients. We consider a setting in which algorithms can retrieve data via a sequence of accesses, each either a random access or a sorted access; the goal is to minimize the total number of data accesses. Our algorithm requires only $O(\sqrt{mk})$ expected accesses: to our knowledge, this is the first sublinear data-access upper bound for this problem. Our analysis also shows that the well-known exponential mechanism requires only $O(\sqrt{m})$ expected accesses. Accompanying this, we develop the first lower bounds for the problem, in three settings: only random accesses; only sorted accesses; a sequence of accesses of either kind. We show that, to avoid $\Omega(m)$ access cost, supporting both kinds of access is necessary, and that in this case our algorithm’s access cost is optimal.

MFCS Conference 2020 Conference Paper

Graph Clustering in All Parameter Regimes

• Junhao Gan
• David F. Gleich
• Nate Veldt
• Anthony Wirth
• Xin Zhang 0094

Resolution parameters in graph clustering control the size and structure of clusters formed by solving a parametric objective function. Typically there is more than one meaningful way to cluster a graph, and solving the same objective function for different resolution parameters produces clusterings at different levels of granularity, each of which can be meaningful depending on the application. In this paper, we address the task of efficiently solving a parameterized graph clustering objective for all values of a resolution parameter. Specifically, we consider a new analysis-friendly objective we call LambdaPrime, involving a parameter λ ∈ (0, 1). LambdaPrime is an adaptation of LambdaCC, a significant family of instances of the Correlation Clustering (minimization) problem. Indeed, LambdaPrime and LambdaCC are closely related to other parameterized clustering problems, such as parametric generalizations of modularity. They capture a number of specific clustering problems as special cases, including sparsest cut and cluster deletion. While previous work provides approximation results for a single value of the resolution parameter, we seek a set of approximately optimal clusterings for all values of λ in polynomial time. More specifically, we show that when a graph has m edges and n nodes, there exists a set of at most m clusterings such that, for every λ ∈ (0, 1), the family contains an optimal solution to the LambdaPrime objective. This bound is tight on star graphs. We obtain a family of O(log n) clusterings by solving the parametric linear programming (LP) relaxation of LambdaPrime at O(log n) λ values, and rounding each LP solution using existing approximation algorithms. We prove that this is asymptotically tight: for a certain class of ring graphs, for all values of λ, Ω(log n) feasible solutions are required to provide a constant-factor approximation for the LambdaPrime LP relaxation. To minimize the size of the clustering family, we further propose an algorithm that yields a family of solutions of a size no more than twice of the minimum LP-approximating family.

SODA Conference 2016 Conference Paper

Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover

• Amit Chakrabarti
• Anthony Wirth

ICML Conference 2015 Conference Paper

Correlation Clustering in Data Streams

• Kook Jin Ahn
• Graham Cormode
• Sudipto Guha
• Andrew McGregor 0001
• Anthony Wirth

In this paper, we address the problem of \emphcorrelation clustering in the dynamic data stream model. The stream consists of updates to the edge weights of a graph on n nodes and the goal is to find a node-partition such that the end-points of negative-weight edges are typically in different clusters whereas the end-points of positive-weight edges are typically in the same cluster. We present polynomial-time, O(n⋅\textpolylog n)-space approximation algorithms for natural problems that arise. We first develop data structures based on linear sketches that allow the “quality” of a given node-partition to be measured. We then combine these data structures with convex programming and sampling techniques to solve the relevant approximation problem. However the standard LP and SDP formulations are not obviously solvable in O(n⋅\textpolylog n)-space. Our work presents space-efficient algorithms for the convex programming required, as well as approaches to reduce the adaptivity of the sampling. Note that the improved space and running-time bounds achieved from streaming algorithms are also useful for offline settings such as MapReduce models.

SODA Conference 2010 Conference Paper

A Polynomial Time Approximation Scheme for k-Consensus Clustering

• Tom Coleman
• Anthony Wirth

ICML Conference 2008 Conference Paper

Spectral clustering with inconsistent advice

• Tom Coleman
• James Saunderson
• Anthony Wirth

TCS Journal 2006 Journal Article

Asymmetry in k -center variants

• Inge Li Gørtz
• Anthony Wirth

This paper explores three concepts: the k -center problem, some of its variants, and asymmetry. The k -center problem is fundamental in location theory. Variants of k -center may more accurately model real-life problems than the original formulation. Asymmetry is a significant impediment to approximation in many graph problems, such as k -center, facility location, k -median, and the TSP. We give an O ( log * n ) -approximation algorithm for the asymmetric weighted k -center problem. Here, the vertices have weights and we are given a total budget for opening centers. In the p-neighbor variant each vertex must have p (unweighted) centers nearby: we give an O ( log * k ) -bicriteria algorithm using 2 k centers, for small p. Finally, we show the following three versions of the asymmetric k -center problem to be inapproximable: priority k -center, k-supplier, and outliers with forbidden centers.

FOCS Conference 2004 Conference Paper

Maximizing Quadratic Programs: Extending Grothendieck's Inequality

• Moses Charikar
• Anthony Wirth

This paper considers the following type of quadratic programming problem. Given an arbitrary matrix A, whose diagonal elements are zero, find x /spl isin/ {-1, 1}/sup n/ such that x/sup T/Ax is maximized. Our approximation algorithm for this problem uses the canonical semidefinite relaxation and returns a solution whose ratio to the optimum is in /spl Omega/(1/ logn). This quadratic programming problem can be seen as an extension to that of maximizing x/sup T/Ay (where y's components are also /spl plusmn/1). Grothendieck's inequality states that the ratio of the optimum value of the latter problem to the optimum of its canonical semidefinite relaxation is bounded below by a constant. The study of this type of quadratic program arose from a desire to approximate the maximum correlation in correlation clustering. Nothing substantive was known about this problem; we present an /spl Omega/ (1/logn) approximation, based on our quadratic programming algorithm. We can also guarantee that our quadratic programming algorithm returns a solution to the MAXCUT problem that has a significant advantage over a random assignment.

FOCS Conference 2003 Conference Paper

Clustering with Qualitative Information

• Moses Charikar
• Venkatesan Guruswami
• Anthony Wirth

We consider the problem of clustering a collection of elements based on pairwise judgments of similarity and dissimilarity. N. Bansal et al. (2002) cast the problem thus: given a graph G whose edges are labeled "+" (similar) or "-" (dissimilar), partition the vertices into clusters so that the number of pairs correctly (resp. incorrectly) classified with respect to the input labeling is maximized (resp. minimized). Complete graphs, where the classifier labels every edge, and general graphs, where some edges are not labeled, are both worth studying. We answer several questions left open by N. Bansal et al. (2002) and provide a sound overview of clustering with qualitative information. We give a factor 4 approximation for minimization on complete graphs, and a factor O(log n) approximation for general graphs. For the maximization version, a PTAS for complete graphs is shown by N. Bansal et al. (2002); we give a factor 0. 7664 approximation for general graphs, noting that a PTAS is unlikely by proving APX-hardness. We also prove the APX-hardness of minimization on complete graphs.

FOCS Conference 2001 Conference Paper

Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity

• Amit Chakrabarti
• Yaoyun Shi
• Anthony Wirth
• Andrew Chi-Chih Yao

Given m copies of the same problem, does it take m times the amount of resources to solve these m problems? This is the direct sum problem, a fundamental question that has been studied in many computational models. We study this question in the simultaneous message (SM) model of communication introduced by A. C. Yao (1979). The equality problem for n-bit strings is well known to have SM complexity /spl Theta/(/spl radic/n). We prove that solving m copies of the problem has complexity /spl Omega/(m/spl radic/n); the best lower bound provable using previously known techniques is /spl Omega/(/spl radic/(mn)). We also prove similar lower bounds on certain Boolean combinations of multiple copies of the equality function. These results can be generalized to a broader class of functions. We introduce a new notion of informational complexity which is related to SM complexity and has nice direct sum properties. This notion is used as a tool to prove the above results; it appears to be quite powerful and may be of independent interest.