MohammadHossein Bateni

ICML Conference 2025 Conference Paper

Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation

• Michal Lukasik
• Lin Chen
• Harikrishna Narasimhan
• Aditya Krishna Menon
• Wittawat Jitkrittum
• Felix X. Yu
• Sashank J. Reddi
• Gang Fu

Bipartite ranking is a fundamental supervised learning problem, with the goal of learning a ranking over instances with maximal area under the ROC curve (AUC) against a single binary target label. However, one may often observe multiple binary target labels, e. g. , from distinct human annotators. How can one synthesize such labels into a single coherent ranking? In this work, we formally analyze two approaches to this problem—loss aggregation and label aggregation—by characterizing their Bayes-optimal solutions. We show that while both approaches can yield Pareto-optimal solutions, loss aggregation can exhibit label dictatorship: one can inadvertently (and undesirably) favor one label over others. This suggests that label aggregation can be preferable to loss aggregation, which we empirically verify.

ICML Conference 2025 Conference Paper

DeepCrossAttention: Supercharging Transformer Residual Connections

• Mike Heddes
• Adel Javanmard
• Kyriakos Axiotis
• Gang Fu
• MohammadHossein Bateni
• Vahab Mirrokni

Transformer networks have achieved remarkable success across diverse domains, leveraging a variety of architectural innovations, including residual connections. However, traditional residual connections, which simply sum the outputs of previous layers, can dilute crucial information. This work introduces DeepCrossAttention (DCA), an approach that enhances residual learning in transformers. DCA employs learnable, input-dependent weights to dynamically combine layer outputs, enabling the model to selectively focus on the most relevant information in any of the previous layers. Furthermore, DCA incorporates depth-wise cross-attention, allowing for richer interactions between layers at different depths. Our language modeling experiments show that DCA achieves improved perplexity for a given training time. Moreover, DCA obtains the same model quality up to 3x faster while adding a negligible number of parameters (e. g. , 0. 2%). Theoretical analysis confirms that DCA provides an improved trade-off between accuracy and model size when the ratio of collective layer ranks to the ambient dimension falls below a critical threshold.

NeurIPS Conference 2025 Conference Paper

Replicable Online pricing

• Kiarash Banihashem
• MohammadHossein Bateni
• Hossein Esfandiari
• Samira Goudarzi
• MohammadTaghi Hajiaghayi

We explore the concept of replicability, which ensures algorithmic consistency despite input data variations, for online pricing problems, specifically prophet inequalities and delegation. Given the crucial role of replicability in enhancing transparency in economic decision-making, we present a replicable and nearly optimal pricing strategy for prophet inequalities, achieving a sample complexity of $\textnormal{poly}(\log^* |\mathcal{X}|)$, where $\mathcal{X}$ is the ground set of distributions. Furthermore, we extend these findings to the delegation problem and establish lower bound that proves the necessity of the $\log^*|\mathcal{X}|$ dependence. En route to obtaining these results, we develop a number of technical contributions which are of independent interest. Most notably, we propose a new algorithm for a variant of the heavy hitter problem, which has a nearly linear dependence on the inverse of the heavy hitter parameter, significantly improving upon existing results which have a cubic dependence.

ICML Conference 2025 Conference Paper

Synthetic Text Generation for Training Large Language Models via Gradient Matching

• Dang Nguyen
• Zeman Li
• MohammadHossein Bateni
• Vahab Mirrokni
• Meisam Razaviyayn
• Baharan Mirzasoleiman

Synthetic data has the potential to improve the performance, training efficiency, and privacy of real training examples. Nevertheless, existing approaches for synthetic text generation are mostly heuristics and cannot generate human-readable text without compromising the privacy of real data, or provide performance guarantees for training Large Language Models (LLMs). In this work, we propose the first theoretically rigorous approach for generating synthetic human-readable text that provides convergence, performance, and privacy guarantees for fine-tuning LLMs on a target task. To do so, we leverage Alternating Direction Method of Multipliers (ADMM) that iteratively optimizes the embeddings of synthetic examples to match the noisy gradient of the target training or validation data, and maps them to a sequence of text tokens with low perplexity. In doing so, the generated synthetic text guarantees convergence of the model to a close neighborhood of the solution obtained by fine-tuning on real data and preserves their privacy. Experiments on various classification tasks confirm the effectiveness of our proposed approach. Our code is available at https: //github. com/BigML-CS-UCLA/GRADMM.

NeurIPS Conference 2024 Conference Paper

Efficient Centroid-Linkage Clustering

• MohammadHossein Bateni
• Laxman Dhulipala
• Willem Fletcher
• Kishen N. Gowda
• D E. Hershkowitz
• Rajesh Jayaram
• Jakub Łącki

We give an algorithm for Centroid-Linkage Hierarchical Agglomerative Clustering (HAC), which computes a $c$-approximate clustering in roughly $n^{1+O(1/c^2)}$ time. We obtain our result by combining a new centroid-linkage HAC algorithm with a novel fully dynamic data structure for nearest neighbor search which works under adaptive updates. We also evaluate our algorithm empirically. By leveraging a state-of-the-art nearest-neighbor search library, we obtain a fast and accurate centroid-linkage HAC algorithm. Compared to an existing state-of-the-art exact baseline, our implementation maintains the clustering quality while delivering up to a $36\times$ speedup due to performing fewer distance comparisons.

NeurIPS Conference 2024 Conference Paper

SequentialAttention++ for Block Sparsification: Differentiable Pruning Meets Combinatorial Optimization

• Taisuke Yasuda
• Kyriakos Axiotis
• Gang Fu
• MohammadHossein Bateni
• Vahab Mirrokni

Neural network pruning is a key technique towards engineering large yet scalable, interpretable, and generalizable models. Prior work on the subject has developed largely along two orthogonal directions: (1) differentiable pruning for efficiently and accurately scoring the importance of parameters, and (2) combinatorial optimization for efficiently searching over the space of sparse models. We unite the two approaches, both theoretically and empirically, to produce a coherent framework for structured neural network pruning in which differentiable pruning guides combinatorial optimization algorithms to select the most important sparse set of parameters. Theoretically, we show how many existing differentiable pruning techniques can be understood as nonconvex regularization for group sparse optimization, and prove that for a wide class of nonconvex regularizers, the global optimum is unique, group-sparse, and provably yields an approximate solution to a sparse convex optimization problem. The resulting algorithm that we propose, SequentialAttention++, advances the state of the art in large-scale neural network block-wise pruning tasks on the ImageNet and Criteo datasets.

SODA Conference 2023 Conference Paper

Optimal Fully Dynamic k -Center Clustering for Adaptive and Oblivious Adversaries

• MohammadHossein Bateni
• Hossein Esfandiari
• Hendrik Fichtenberger
• Monika Henzinger
• Rajesh Jayaram
• Vahab Mirrokni
• Andreas Wiese

In fully dynamic clustering problems, a clustering of a given data set in a metric space must be maintained while it is modified through insertions and deletions of individual points. In this paper, we resolve the complexity of fully dynamic k -center clustering against both adaptive and oblivious adversaries. Against oblivious adversaries, we present the first algorithm for fully dynamic k -center in an arbitrary metric space that maintains an optimal (2 + ε)-approximation in O ( k · polylog( n, Δ)) amortized update time. Here, n is an upper bound on the number of active points at any time, and Δ is the aspect ratio of the metric space. Previously, the best known amortized update time was O ( k 2 · polylog( n, Δ)), and is due to Chan, Gourqin, and Sozio (2018). Moreover, we demonstrate that our runtime is optimal up to polylog( n, Δ) factors. In fact, we prove that even offline algorithms for k -clustering tasks in arbitrary metric spaces, including k -medians, k -means, and k -center, must make at least Ω( nk ) distance queries to achieve any non-trivial approximation factor. This implies a lower bound of Ω( k ) which holds even for the insertions-only setting. For adaptive adversaries, we give the first deterministic algorithm for fully dynamic k -center which achieves a approximation in O ( k -polylog( n, Δ)) amortized update time. Further, we demonstrate that any algorithm which achieves a -approximation against adaptive adversaries requires f (k, n) update time, for any arbitrary function f. Thus, in the regime where, we close the complexity of the problem up to polylog( n, Δ) factors in the update time. Our lower bound extends to other k -clustering tasks in arbitrary metric spaces, including k -medians and k -means. Finally, despite the aforementioned lower bounds, we demonstrate that an update time sublinear in k is possible against oblivious adversaries for metric spaces which admit locally sensitive hash functions (LSH), resulting in improved algorithms for a large class of metrics including Euclidean space, ℓ p -spaces, the Hamming Metric, and the Jaccard Metric. We also give the first fully dynamic O (1)-approximation algorithms for the closely related k -sum-of-radii and k -sum-of-diameter problems, with O (poly( k, log Δ)) update time.

ICLR Conference 2023 Conference Paper

Sequential Attention for Feature Selection

• Taisuke Yasuda 0002
• MohammadHossein Bateni
• Lin Chen
• Matthew Fahrbach
• Gang Fu
• Vahab Mirrokni

Feature selection is the problem of selecting a subset of features for a machine learning model that maximizes model quality subject to a budget constraint. For neural networks, prior methods, including those based on $\ell_1$ regularization, attention, and other techniques, typically select the entire feature subset in one evaluation round, ignoring the residual value of features during selection, i.e., the marginal contribution of a feature given that other features have already been selected. We propose a feature selection algorithm called Sequential Attention that achieves state-of-the-art empirical results for neural networks. This algorithm is based on an efficient one-pass implementation of greedy forward selection and uses attention weights at each step as a proxy for feature importance. We give theoretical insights into our algorithm for linear regression by showing that an adaptation to this setting is equivalent to the classical Orthogonal Matching Pursuit (OMP) algorithm, and thus inherits all of its provable guarantees. Our theoretical and empirical analyses offer new explanations towards the effectiveness of attention and its connections to overparameterization, which may be of independent interest.

UAI Conference 2023 Conference Paper

SubMix: Learning to Mix Graph Sampling Heuristics

• Sami Abu-El-Haija
• Joshua V. Dillon
• Bahare Fatemi
• Kyriakos Axiotis
• Neslihan Bulut
• Johannes Gasteiger
• Bryan Perozzi
• MohammadHossein Bateni

Sampling subgraphs for training Graph Neural Networks (GNNs) is receiving much attention from the GNN community. While a variety of methods have been proposed, each method samples the graph according to its own heuristic. However, there has been little work in mixing these heuristics in an end-to-end trainable manner. In this work, we design a generative framework for graph sampling. Our method, SubMix, parameterizes subgraph sampling as a convex combination of heuristics. We show that a continuous relaxation of the discrete sampling process allows us to efficiently obtain analytical gradients for training the sampling parameters. Our experimental results illustrate the usefulness of learning graph sampling in three scenarios: (1) robust training of GNNs by automatically learning to discard noisy edge sources; (2) improving model performance by trainable and online edge subset selection; and (3) by integrating our framework into decoupled GNN models improves their performance on standard benchmarks.

TMLR Journal 2023 Journal Article

Tackling Provably Hard Representative Selection via Graph Neural Networks

• Mehran Kazemi
• Anton Tsitsulin
• Hossein Esfandiari
• MohammadHossein Bateni
• Deepak Ramachandran
• Bryan Perozzi
• Vahab Mirrokni

Representative Selection (RS) is the problem of finding a small subset of exemplars from a dataset that is representative of the dataset. In this paper, we study RS for attributed graphs, and focus on finding representative nodes that optimize the accuracy of a model trained on the selected representatives. Theoretically, we establish a new hardness result for RS (in the absence of a graph structure) by proving that a particular, highly practical variant of it (RS for Learning) is hard to approximate in polynomial time within any reasonable factor, which implies a significant potential gap between the optimum solution of widely-used surrogate functions and the actual accuracy of the model. We then study the setting where a (homophilous) graph structure is available, or can be constructed, between the data points. We show that with an appropriate modeling approach, the presence of such a structure can turn a hard RS (for learning) problem into one that can be effectively solved. To this end, we develop RS-GNN, a representation learning-based RS model based on Graph Neural Networks. Empirically, we demonstrate the effectiveness of RS-GNN on problems with predefined graph structures as well as problems with graphs induced from node feature similarities, by showing that RS-GNN achieves significant improvements over established baselines on a suite of eight benchmarks.

AAAI Conference 2021 Conference Paper

Extreme k-Center Clustering

• MohammadHossein Bateni
• Hossein Esfandiari
• Manuela Fischer
• Vahab Mirrokni

Metric clustering is a fundamental primitive in machine learning with several applications for mining massive datasets. An important example of metric clustering is the k-center problem. While this problem has been extensively studied in distributed settings, all previous algorithms use Ω(k) space per machine and Ω(nk) total work. In this paper, we develop the first highly scalable approximation algorithm for k-center clustering, with e O(nε ) space per machine and e O(n1+ ) total work, for arbitrary small constant ε. It produces an O(log log log n)approximate solution with k(1+o(1)) centers in O(log log n) rounds of computation.

NeurIPS Conference 2021 Conference Paper

Streaming Belief Propagation for Community Detection

• Yuchen Wu
• Jakab Tardos
• MohammadHossein Bateni
• André Linhares
• Filipe Miguel Goncalves de Almeida
• Andrea Montanari
• Ashkan Norouzi-Fard

The community detection problem requires to cluster the nodes of a network into a small number of well-connected ‘communities’. There has been substantial recent progress in characterizing the fundamental statistical limits of community detection under simple stochastic block models. However, in real-world applications, the network structure is typically dynamic, with nodes that join over time. In this setting, we would like a detection algorithm to perform only a limited number of updates at each node arrival. While standard voting approaches satisfy this constraint, it is unclear whether they exploit the network information optimally. We introduce a simple model for networks growing over time which we refer to as streaming stochastic block model (StSBM). Within this model, we prove that voting algorithms have fundamental limitations. We also develop a streaming belief-propagation (STREAMBP) approach, for which we prove optimality in certain regimes. We validate our theoretical findings on synthetic and real data

ICML Conference 2019 Conference Paper

Categorical Feature Compression via Submodular Optimization

• MohammadHossein Bateni
• Lin Chen
• Hossein Esfandiari
• Thomas Fu
• Vahab Mirrokni
• Afshin Rostamizadeh

In the era of big data, learning from categorical features with very large vocabularies (e. g. , 28 million for the Criteo click prediction dataset) has become a practical challenge for machine learning researchers and practitioners. We design a highly-scalable vocabulary compression algorithm that seeks to maximize the mutual information between the compressed categorical feature and the target binary labels and we furthermore show that its solution is guaranteed to be within a $1-1/e \approx 63%$ factor of the global optimal solution. Although in some settings, entropy-based set functions are known to be submodular, this is not the case for the mutual information objective we consider (mutual information with respect to the target labels). To address this, we introduce a novel re-parametrization of the mutual information objective, which we prove is submodular, and also design a data structure to query the submodular function in amortized $O(\log n )$ time (where $n$ is the input vocabulary size). Our complete algorithm is shown to operate in $O(n \log n )$ time. Additionally, we design a distributed implementation in which the query data structure is decomposed across $O(k)$ machines such that each machine only requires $O(\frac n k)$ space, while still preserving the approximation guarantee and using only logarithmic rounds of computation. We also provide analysis of simple alternative heuristic compression methods to demonstrate they cannot achieve any approximation guarantee. Using the large-scale Criteo learning task, we demonstrate better performance in retaining mutual information and also verify competitive learning performance compared to other baseline methods.

SODA Conference 2019 Conference Paper

Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs

• Sepehr Assadi
• MohammadHossein Bateni
• Aaron Bernstein
• Vahab Mirrokni
• Cliff Stein 0001

There is a rapidly growing need for scalable algorithms that solve classical graph problems, such as maximum matching and minimum vertex cover, on massive graphs. For massive inputs, several different computational models have been introduced, including the streaming model, the distributed communication model, and the massively parallel computation (MPC) model that is a common abstraction of MapReduce-style computation. In each model, algorithms are analyzed in terms of resources such as space used or rounds of communication needed, in addition to the more traditional approximation ratio. In this paper, we give a single unified approach that yields better approximation algorithms for matching and vertex cover in all these models. The highlights include: The first one pass, significantly-better-than-2-approximation for matching in random arrival streams that uses subquadratic space, namely a (1. 5 + ε )-approximation streaming algorithm that uses Õ ( n 15 ) space for constant ε > 0. The first 2-round, better-than-2-approximation for matching in the MPC model that uses subquadratic space per machine, namely a (1. 5 + ε )-approximation algorithm with memory per machine for constant ε > 0. By building on our unified approach, we further develop parallel algorithms in the MPC model that give a (1+ ∊ )-approximation to matching and an O (1)-approximation to vertex cover in only O (log log n ) MPC rounds and O ( n /polylog( n )) memory per machine. These results settle multiple open questions posed by Czumaj et al. [STOC 2018]. We obtain our results by a novel combination of two previously disjoint set of techniques, namely randomized composable coresets and edge degree constrained subgraphs (EDCS). We significantly extend the power of these techniques and prove several new structural results. For example, we show that an EDCS is a sparse certificate for large matchings and small vertex covers that is quite robust to sampling and composition.

ICML Conference 2019 Conference Paper

Distributed Weighted Matching via Randomized Composable Coresets

• Sepehr Assadi
• MohammadHossein Bateni
• Vahab Mirrokni

Maximum weight matching is one of the most fundamental combinatorial optimization problems with a wide range of applications in data mining and bioinformatics. Developing distributed weighted matching algorithms has been challenging due to the sequential nature of efficient algorithms for this problem. In this paper, we develop a simple distributed algorithm for the problem on general graphs with approximation guarantee of 2 + eps that (nearly) matches that of the sequential greedy algorithm. A key advantage of this algorithm is that it can be easily implemented in only two rounds of computation in modern parallel computation frameworks such as MapReduce. We also demonstrate the efficiency of our algorithm in practice on various graphs (some with half a trillion edges) by achieving objective values always close to what is achievable in the centralized setting.

SODA Conference 2019 Conference Paper

Polynomial-time Approximation Scheme for Minimum k-cut in Planar and Minor-free Graphs

• MohammadHossein Bateni
• Alireza Farhadi 0001
• MohammadTaghi Hajiaghayi

STOC Conference 2018 Conference Paper

Fast algorithms for knapsack via convolution and prediction

• MohammadHossein Bateni
• MohammadTaghi Hajiaghayi
• Saeed Seddighin
• Cliff Stein 0001

The knapsack problem is a fundamental problem in combinatorial optimization. It has been studied extensively from theoretical as well as practical perspectives as it is one of the most well-known NP-hard problems. The goal is to pack a knapsack of size t with the maximum value from a collection of n items with given sizes and values. Recent evidence suggests that a classic O ( nt ) dynamic-programming solution for the knapsack problem might be the fastest in the worst case. In fact, solving the knapsack problem was shown to be computationally equivalent to the (min, +) convolution problem, which is thought to be facing a quadratic-time barrier. This hardness is in contrast to the more famous (+, ·) convolution (generally known as polynomial multiplication), that has an O ( n log n )-time solution via Fast Fourier Transform. Our main results are algorithms with near-linear running times (in terms of the size of the knapsack and the number of items) for the knapsack problem, if either the values or sizes of items are small integers. More specifically, if item sizes are integers bounded by, the running time of our algorithm is Õ(( n + t )). If the item values are integers bounded by, our algorithm runs in time Õ( n + t ). Best previously known running times were O ( nt ), O ( n 2 ) and O ( n ) (Pisinger, J. of Alg., 1999). At the core of our algorithms lies the prediction technique: Roughly speaking, this new technique enables us to compute the convolution of two vectors in time ( n ) when an approximation of the solution within an additive error of is available. Our results also improve the best known strongly polynomial time solutions for knapsack. In the limited size setting, when the items have multiplicities, the fastest strongly polynomial time algorithms for knapsack run in time O ( n 2 2 ) and O ( n 3 2 ) for the cases of infinite and given multiplicities, respectively. Our results improve both running times by a factor of ( n max{1, n /}).

AAAI Conference 2017 Conference Paper

A Study of Compact Reserve Pricing Languages

• MohammadHossein Bateni
• Hossein Esfandiary
• Vahab Mirrokni
• Saeed Seddighin

Online advertising allows advertisers to implement fine-tuned targeting of users. While such precise targeting leads to more effective advertising, it introduces challenging multidimensional pricing and bidding problems for publishers and advertisers. In this context, advertisers and publishers need to deal with an exponential number of possibilities. As a result, designing efficient and compact multidimensional bidding and pricing systems and algorithms are practically important for online advertisement. Compact bidding languages have already been studied in the context of multiplicative bidding. In this paper, we study the compact pricing problem. More specifically, we first define the multiplicative reserve price optimization problem (MRPOP) and show that unlike the unrestricted reserve price system, it is NP-hard to find the best reserve price solution in this setting. Next, we present an efficient algorithm to compute a solution for MRPOP that achieves a logarithmic approximation of the optimum solution of the unrestricted setting, where we can set a reserve price for each individual impression type (i. e. , one element in the Cartesian product of all features). We do so by characterizing the properties of an optimum solution. Furthermore, our empirical study confirms the effectiveness of multiplicative pricing in practice. In fact, the simulations show that our algorithm obtains 90–98% of the value of the best solution that sets the reserve prices for each auction individually (i. e. , the optimum set of reserve prices). Finally, in order to establish the tightness of our results in the adversarial setting, we demonstrate that there is no compact pricing system (i. e. , a pricing system using O(n1− ) bits to set n reserve prices) that loses, in the worst case, less than a logarithmic factor compared to the optimum set of reserve prices. Notice that this hardness result is not restricted to the multiplicative setting and holds for any compact pricing system. In summary, not only does the multiplicative reserve price system show great promise in our empirical study, but it is also theoretically optimal up to a constant factor in the adversarial setting. ∗ Supported in part by NSF CAREER award CCF-1053605, NSF BIGDATA grant IIS-1546108, NSF AF: Medium grant CCF- 1161365, DARPA GRAPHS/AFOSR grant FA9550-12-1-0423, and another DARPA SIMPLEX grant. Copyright c 2017, Association for the Advancement of Artificial Intelligence (www. aaai. org). All rights reserved.

NeurIPS Conference 2017 Conference Paper

Affinity Clustering: Hierarchical Clustering at Scale

• MohammadHossein Bateni
• Soheil Behnezhad
• Mahsa Derakhshan
• MohammadTaghi Hajiaghayi
• Raimondas Kiveris
• Silvio Lattanzi
• Vahab Mirrokni

Graph clustering is a fundamental task in many data-mining and machine-learning pipelines. In particular, identifying a good hierarchical structure is at the same time a fundamental and challenging problem for several applications. The amount of data to analyze is increasing at an astonishing rate each day. Hence there is a need for new solutions to efficiently compute effective hierarchical clusterings on such huge data. The main focus of this paper is on minimum spanning tree (MST) based clusterings. In particular, we propose affinity, a novel hierarchical clustering based on Boruvka's MST algorithm. We prove certain theoretical guarantees for affinity (as well as some other classic algorithms) and show that in practice it is superior to several other state-of-the-art clustering algorithms. Furthermore, we present two MapReduce implementations for affinity. The first one works for the case where the input graph is dense and takes constant rounds. It is based on a Massively Parallel MST algorithm for dense graphs that improves upon the state-of-the-art algorithm of Lattanzi et al. (SPAA 2011). Our second algorithm has no assumption on the density of the input graph and finds the affinity clustering in $O(\log n)$ rounds using Distributed Hash Tables (DHTs). We show experimentally that our algorithms are scalable for huge data sets, e. g. , for graphs with trillions of edges.

STOC Conference 2016 Conference Paper

A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting

• MohammadHossein Bateni
• Erik D. Demaine
• MohammadTaghi Hajiaghayi
• Dániel Marx

We present the first polynomial-time approximation scheme (PTAS), i.e., (1+ε)-approximation algorithm for any constant ε> 0, for the planar group Steiner tree problem (in which each group lies on a boundary of a face). This result improves on the best previous approximation factor of O (log n (loglog n ) O (1) ). We achieve this result via a novel and powerful technique called spanner bootstrapping , which allows one to bootstrap from a superconstant approximation factor (even superpolynomial in the input size) all the way down to a PTAS. This is in contrast with the popular existing approach for planar PTASs of constructing light-weight spanners in one iteration, which notably requires a constant-factor approximate solution to start from. Spanner bootstrapping removes one of the main barriers for designing PTASs for problems which have no known constant-factor approximation (even on planar graphs), and thus can be used to obtain PTASs for several difficult-to-approximate problems.

NeurIPS Conference 2014 Conference Paper

Distributed Balanced Clustering via Mapping Coresets

• MohammadHossein Bateni
• Aditya Bhaskara
• Silvio Lattanzi
• Vahab Mirrokni

Large-scale clustering of data points in metric spaces is an important problem in mining big data sets. For many applications, we face explicit or implicit size constraints for each cluster which leads to the problem of clustering under capacity constraints or the balanced clustering'' problem. Although the balanced clustering problem has been widely studied, developing a theoretically sound distributed algorithm remains an open problem. In the present paper we develop a general framework based on mapping coresets'' to tackle this issue. For a wide range of clustering objective functions such as k-center, k-median, and k-means, our techniques give distributed algorithms for balanced clustering that match the best known single machine approximation ratios.

SODA Conference 2012 Conference Paper

A polynomial-time approximation scheme for planar multiway cut

• MohammadHossein Bateni
• MohammadTaghi Hajiaghayi
• Philip N. Klein
• Claire Mathieu

Given an undirected graph with edge lengths and a subset of nodes (called the terminals ), the multiway cut (also called the multi-terminal cut ) problem asks for a subset of edges, with minimum total length, whose removal disconnects each terminal from all others. The problem generalizes minimum s-t cut, but is NP-hard for planar graphs and APX-hard for general graphs [11]. In this paper, we present a PTAS for multiway cut on planar graphs.

SODA Conference 2011 Conference Paper

Prize-collecting Steiner Problems on Planar Graphs

• MohammadHossein Bateni
• Chandra Chekuri
• Alina Ene
• MohammadTaghi Hajiaghayi
• Nitish Korula
• Dániel Marx

STOC Conference 2010 Conference Paper

Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth

• MohammadHossein Bateni
• MohammadTaghi Hajiaghayi
• Dániel Marx

We give the first polynomial-time approximation scheme (PTAS) for the Steiner forest problem on planar graphs and, more generally, on graphs of bounded genus. As a first step, we show how to build a Steiner forest spanner for such graphs. The crux of the process is a clustering procedure called prize-collecting clustering that breaks down the input instance into separate subinstances which are easier to handle; moreover, the terminals in different subinstances are far from each other. Each subinstance has a relatively inexpensive Steiner tree connecting all its terminals, and the subinstances can be solved (almost) separately. Another building block is a PTAS for Steiner forest on graphs of bounded treewidth. Surprisingly, Steiner forest is NP-hard even on graphs of treewidth 3. Therefore, our PTAS for bounded treewidth graphs needs a nontrivial combination of approximation arguments and dynamic programming on the tree decomposition. We further show that Steiner forest can be solved in polynomial time for series-parallel graphs (graphs of treewidth at most two) by a novel combination of dynamic programming and minimum cut computations, completing our thorough complexity study of Steiner forest in the range of bounded treewidth graphs, planar graphs, and bounded genus graphs.

SODA Conference 2009 Conference Paper

Assignment problem in content distribution networks: unsplittable hard-capacitated facility location

• MohammadHossein Bateni
• MohammadTaghi Hajiaghayi

FOCS Conference 2009 Conference Paper

Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP

• Aaron Archer
• MohammadHossein Bateni
• MohammadTaghi Hajiaghayi
• Howard J. Karloff

We study the prize-collecting versions of the Steiner tree, traveling salesman, and stroll (a. k. a. Path-TSP) problems (PCST, PCTSP, and PCS, respectively): given a graph (V, E) with costs on each edge and a penalty (a. k. a. prize) on each node, the goal is to find a tree (for PCST), cycle (for PCTSP), or stroll (for PCS) that minimizes the sum of the edge costs in the tree/cycle/stroll and the penalties of the nodes not spanned by it. In addition to being a useful theoretical tool for helping to solve other optimization problems, PCST has been applied fruitfully by AT&T to the optimization of real-world telecommunications networks. The most recent improvements for the first two problems, giving a 2-approximation algorithm for each, appeared first in 1992. (A 2-approximation for PCS appeared in 2003.) The natural linear programming (LP) relaxation of PCST has an integrality gap of 2, which has been a barrier to further improvements for this problem. We present (2 · ¿)-approximation algorithms for all three problems, connected by a unified technique for improving prize-collecting algorithms that allows us to circumvent the integrality gap barrier.

STOC Conference 2009 Conference Paper

MaxMin allocation via degree lower-bounded arborescences

• MohammadHossein Bateni
• Moses Charikar
• Venkatesan Guruswami

We consider the problem of MaxMin allocation of indivisible goods. There are m items to be distributed among n players. Each player $i$ has a nonnegative valuation p ij for an item j, and the goal is to allocate items to players so as to maximize the minimum total valuation received by each player. There is a large gap in our understanding of this problem. The best known positive result is an ~O(√ n)-approximation algorithm, while there is only a factor 2 hardness known. Better algorithms are known for the restricted assignment case where each item has exactly one nonzero value for the players. We study the effect of bounded degree for items: each item has a nonzero value for at most D players. We show that essentially the case D = 3 is equivalent to the general case, and give a 4-approximation algorithm for D = 2.