Arrow Research search

Author name cluster

Benjamin Moseley

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

42 papers
2 author rows

Possible papers

42

ICML Conference 2025 Conference Paper

Faster Global Minimum Cut with Predictions

  • Helia Niaparast
  • Benjamin Moseley
  • Karan Singh

Global minimum cut is a fundamental combinatorial optimization problem with wide-ranging applications. Often in practice, these problems are solved repeatedly on families of similar or related instances. However, the de facto algorithmic approach is to solve each instance of the problem from scratch discarding information from prior instances. In this paper, we consider how predictions informed by prior instances can be used to warm-start practical minimum cut algorithms. The paper considers the widely used Karger’s algorithm and its counterpart, the Karger-Stein algorithm. Given good predictions, we show these algorithms become near-linear time and have robust performance to erroneous predictions. Both of these algorithms are randomized edge-contraction algorithms. Our natural idea is to probabilistically prioritize the contraction of edges that are unlikely to be in the minimum cut.

Details

NeurIPS Conference 2024 Conference Paper

Binary Search with Distributional Predictions

  • Michael Dinitz
  • Sungjin Im
  • Thomas Lavastida
  • Benjamin Moseley
  • Aidin Niaparast
  • Sergei Vassilvitskii

Algorithms with (machine-learned) predictions is a powerful framework for combining traditional worst-case algorithms with modern machine learning. However, the vast majority of work in this space assumes that the prediction itself is non-probabilistic, even if it is generated by some stochastic process (such as a machine learning system). This is a poor fit for modern ML, particularly modern neural networks, which naturally generate a *distribution*. We initiate the study of algorithms with *distributional* predictions, where the prediction itself is a distribution. We focus on one of the simplest yet fundamental settings: binary search (or searching a sorted array). This setting has one of the simplest algorithms with a point prediction, but what happens if the prediction is a distribution? We show that this is a richer setting: there are simple distributions where using the classical prediction-based algorithm with any single prediction does poorly. Motivated by this, as our main result, we give an algorithm with query complexity $O(H(p) + \log \eta)$, where $H(p)$ is the entropy of the true distribution $p$ and $\eta$ is the earth mover's distance between $p$ and the predicted distribution $\hat p$. This also yields the first *distributionally-robust* algorithm for the classical problem of computing an optimal binary search tree given a distribution over target keys. We complement this with a lower bound showing that this query complexity is essentially optimal (up to constants), and experiments validating the practical usefulness of our algorithm.

PDF Details DOI

SODA Conference 2024 Conference Paper

Controlling Tail Risk in Online Ski-Rental

  • Michael Dinitz
  • Sungjin Im
  • Thomas Lavastida
  • Benjamin Moseley
  • Sergei Vassilvitskii

The classical ski-rental problem admits a textbook 2-competitive deterministic algorithm, and a simple randomized algorithm that is e / e -1-competitive in expectation. The randomized algorithm, while optimal in expectation, has a large variance in its performance: it has more than a 37% chance of competitive ratio exceeding 2, and the change of the competitive ratio exceeding n is Θ(1/ n )! We ask what happens to the optimal solution if we insist that the tail risk, i. e. , the chance of the competitive ratio exceeding a specific value, is bounded by some constant δ. We find that this additional modification significantly changes the structure of the optimal solution. The probability of purchasing skis on a given day becomes non-monotone, discontinuous, and arbitrarily large (for sufficiently small tail risk δ and large purchase cost n ). * A full version of the paper can be accessed at https: //arxiv. org/abs/2308. 05067

Details

ICML Conference 2024 Conference Paper

Incremental Topological Ordering and Cycle Detection with Predictions

  • Samuel McCauley
  • Benjamin Moseley
  • Aidin Niaparast
  • Shikha Singh 0002

This paper leverages the framework of algorithms-with-predictions to design data structures for two fundamental dynamic graph problems: incremental topological ordering and cycle detection. In these problems, the input is a directed graph on $n$ nodes, and the $m$ edges arrive one by one. The data structure must maintain a topological ordering of the vertices at all times and detect if the newly inserted edge creates a cycle. The theoretically best worst-case algorithms for these problems have high update cost (polynomial in $n$ and $m$). In practice, greedy heuristics (that recompute the solution from scratch each time) perform well but can have high update cost in the worst case. In this paper, we bridge this gap by leveraging predictions to design a learned new data structure for the problems. Our data structure guarantees consistency, robustness, and smoothness with respect to predictions—that is, it has the best possible running time under perfect predictions, never performs worse than the best-known worst-case methods, and its running time degrades smoothly with the prediction error. Moreover, we demonstrate empirically that predictions, learned from a very small training dataset, are sufficient to provide significant speed-ups on real datasets.

Details

AAAI Conference 2024 Conference Paper

Sampling for Beyond-Worst-Case Online Ranking

  • Qingyun Chen
  • Sungjin Im
  • Benjamin Moseley
  • Chenyang Xu
  • Ruilong Zhang

The feedback arc set problem is one of the most fundamental and well-studied ranking problems where n objects are to be ordered based on their pairwise comparison. The problem enjoys several efficient approximation algorithms in the offline setting. Unfortunately, online there are strong lower bounds on the competitive ratio establishing that no algorithm can perform well in the worst case. This paper introduces a new beyond-worst-case model for online feedback arc set. In the model, a sample of the input is given to the algorithm offline before the remaining instance is revealed online. This models the case in practice where yesterday's data is available and is similar to today's online instance. This sample is drawn from a known distribution which may not be uniform. We design an online algorithm with strong theoretical guarantees. The algorithm has a small constant competitive ratio when the sample is uniform---if not, we show we can recover the same result by adding a provably minimal sample. Empirical results validate the theory and show that such algorithms can be used on temporal data to obtain strong results.

PDF Details DOI

JMLR Journal 2023 Journal Article

Approximation Bounds for Hierarchical Clustering: Average Linkage, Bisecting K-means, and Local Search

  • Benjamin Moseley
  • Joshua R. Wang

Hierarchical clustering is a data analysis method that has been used for decades. Despite its widespread use, the method has an underdeveloped analytical foundation. Having a well-understood foundation would both support the currently used methods and help guide future improvements. The goal of this paper is to give an analytic framework to better understand observations seen in practice. This paper considers the dual of a problem framework for hierarchical clustering introduced by Dasgupta. The main result is that one of the most popular algorithms used in practice, average linkage agglomerative clustering, has a small constant approximation ratio for this objective. To contrast, this paper establishes that using several other popular algorithms, including bisecting $k$-means divisive clustering, have a very poor lower bound on its approximation ratio for the same objective. However, we show that there are divisive algorithms that perform well with respect to this objective by giving two constant approximation algorithms. This paper is some of the first work to establish guarantees on widely used hierarchical algorithms for a natural objective function. This objective and analysis give insight into what these popular algorithms are optimizing and when they will perform well. [abs] [ pdf ][ bib ] &copy JMLR 2023. ( edit, beta )

PDF Details

ICML Conference 2023 Conference Paper

Fast Combinatorial Algorithms for Min Max Correlation Clustering

  • Sami Davies
  • Benjamin Moseley
  • Heather Newman

We introduce fast algorithms for correlation clustering with respect to the Min Max objective that provide constant factor approximations on complete graphs. Our algorithms are the first purely combinatorial approximation algorithms for this problem. We construct a novel semi-metric on the set of vertices, which we call the correlation metric, that indicates to our clustering algorithms whether pairs of nodes should be in the same cluster. The paper demonstrates empirically that, compared to prior work, our algorithms sacrifice little in the objective quality to obtain significantly better run-time. Moreover, our algorithms scale to larger networks that are effectively intractable for known algorithms.

Details

AAAI Conference 2023 Conference Paper

Min-Max Submodular Ranking for Multiple Agents

  • Qingyun Chen
  • Sungjin Im
  • Benjamin Moseley
  • Chenyang Xu
  • Ruilong Zhang

In the submodular ranking (SR) problem, the input consists of a set of submodular functions defined on a ground set of elements. The goal is to order elements for all the functions to have value above a certain threshold as soon on average as possible, assuming we choose one element per time. The problem is flexible enough to capture various applications in machine learning, including decision trees. This paper considers the min-max version of SR where multiple instances share the ground set. With the view of each instance being associated with an agent, the min-max problem is to order the common elements to minimize the maximum objective of all agents---thus, finding a fair solution for all agents. We give approximation algorithms for this problem and demonstrate their effectiveness in the application of finding a decision tree for multiple agents.

PDF Details DOI

ICML Conference 2023 Conference Paper

Predictive Flows for Faster Ford-Fulkerson

  • Sami Davies
  • Benjamin Moseley
  • Sergei Vassilvitskii
  • Yuyan Wang

Recent work has shown that leveraging learned predictions can improve the running time of algorithms for bipartite matching and similar combinatorial problems. In this work, we build on this idea to improve the performance of the widely used Ford-Fulkerson algorithm for computing maximum flows by seeding Ford-Fulkerson with predicted flows. Our proposed method offers strong theoretical performance in terms of the quality of the prediction. We then consider image segmentation, a common use-case of flows in computer vision, and complement our theoretical analysis with strong empirical results.

Details

NeurIPS Conference 2022 Conference Paper

Algorithms with Prediction Portfolios

  • Michael Dinitz
  • Sungjin Im
  • Thomas Lavastida
  • Benjamin Moseley
  • Sergei Vassilvitskii

The research area of algorithms with predictions has seen recent success showing how to incorporate machine learning into algorithm design to improve performance when the predictions are correct, while retaining worst-case guarantees when they are not. Most previous work has assumed that the algorithm has access to a single predictor. However, in practice, there are many machine learning methods available, often with incomparable generalization guarantees, making it hard to pick a best method a priori. In this work we consider scenarios where multiple predictors are available to the algorithm and the question is how to best utilize them. Ideally, we would like the algorithm's performance to depend on the quality of the {\em best} predictor. However, utilizing more predictions comes with a cost, since we now have to identify which prediction is best. We study the use of multiple predictors for a number of fundamental problems, including matching, load balancing, and non-clairvoyant scheduling, which have been well-studied in the single predictor setting. For each of these problems we introduce new algorithms that take advantage of multiple predictors, and prove bounds on the resulting performance.

PDF Details

AAAI Conference 2022 Conference Paper

Learning-Augmented Algorithms for Online Steiner Tree

  • Chenyang Xu
  • Benjamin Moseley

This paper considers the recently popular beyond-worst-case algorithm analysis model which integrates machine-learned predictions with online algorithm design. We consider the online Steiner tree problem in this model for both directed and undirected graphs. Steiner tree is known to have strong lower bounds in the online setting and any algorithm’s worst-case guarantee is far from desirable. This paper considers algorithms that predict which terminal arrives online. The predictions may be incorrect and the algorithms’ performance is parameterized by the number of incorrectly predicted terminals. These guarantees ensure that algorithms break through the online lower bounds with good predictions and the competitive ratio gracefully degrades as the prediction error grows. We then observe that the theory is predictive of what will occur empirically. We show on graphs where terminals are drawn from a distribution, the new online algorithms have strong performance even with modestly correct predictions.

PDF Details

MFCS Conference 2021 Conference Paper

An Approximation Algorithm for the Matrix Tree Multiplication Problem

  • Mahmoud Abo Khamis
  • Ryan R. Curtin
  • Sungjin Im
  • Benjamin Moseley
  • Hung Q. Ngo 0001
  • Kirk Pruhs
  • Alireza Samadian

We consider the Matrix Tree Multiplication problem. This problem is a generalization of the classic Matrix Chain Multiplication problem covered in the dynamic programming chapter of many introductory algorithms textbooks. An instance of the Matrix Tree Multiplication problem consists of a rooted tree with a matrix associated with each edge. The output is, for each leaf in the tree, the product of the matrices on the chain/path from the root to that leaf. Matrix multiplications that are shared between various chains need only be computed once, potentially being shared between different root to leaf chains. Algorithms are evaluated by the number of scalar multiplications performed. Our main result is a linear time algorithm for which the number of scalar multiplications performed is at most 15 times the optimal number of scalar multiplications.

Details

NeurIPS Conference 2021 Conference Paper

Faster Matchings via Learned Duals

  • Michael Dinitz
  • Sungjin Im
  • Thomas Lavastida
  • Benjamin Moseley
  • Sergei Vassilvitskii

A recent line of research investigates how algorithms can be augmented with machine-learned predictions to overcome worst case lower bounds. This area has revealed interesting algorithmic insights into problems, with particular success in the design of competitive online algorithms. However, the question of improving algorithm running times with predictions has largely been unexplored. We take a first step in this direction by combining the idea of machine-learned predictions with the idea of ``warm-starting" primal-dual algorithms. We consider one of the most important primitives in combinatorial optimization: weighted bipartite matching and its generalization to $b$-matching. We identify three key challenges when using learned dual variables in a primal-dual algorithm. First, predicted duals may be infeasible, so we give an algorithm that efficiently maps predicted infeasible duals to nearby feasible solutions. Second, once the duals are feasible, they may not be optimal, so we show that they can be used to quickly find an optimal solution. Finally, such predictions are useful only if they can be learned, so we show that the problem of learning duals for matching has low sample complexity. We validate our theoretical findings through experiments on both real and synthetic data. As a result we give a rigorous, practical, and empirically effective method to compute bipartite matchings.

PDF Details

NeurIPS Conference 2021 Conference Paper

Robust Online Correlation Clustering

  • Silvio Lattanzi
  • Benjamin Moseley
  • Sergei Vassilvitskii
  • Yuyan Wang
  • Rudy Zhou

In correlation clustering we are given a set of points along with recommendations whether each pair of points should be placed in the same cluster or into separate clusters. The goal cluster the points to minimize disagreements from the recommendations. We study the correlation clustering problem in the online setting. , where points arrive one at a time, and upon arrival the algorithm must make an irrevocable cluster assignment decision. While the online version is natural, there is a simple lower bound that rules out any algorithm with a non-trivial competitive ratio. In this work we go beyond worst case analysis, and show that the celebrated Pivot algorithm performs well when given access to a small number of random samples from the input. Moreover, we prove that Pivot is robust to additional adversarial perturbations of the sample set in this setting. We conclude with an empirical analysis validating our theoretical findings.

PDF Details

AAAI Conference 2020 Conference Paper

An Objective for Hierarchical Clustering in Euclidean Space and Its Connection to Bisecting K-means

  • Yuyan Wang
  • Benjamin Moseley

This paper explores hierarchical clustering in the case where pairs of points have dissimilarity scores (e. g. distances) as a part of the input. The recently introduced objective for points with dissimilarity scores results in every tree being a 1 2 approximation if the distances form a metric. This shows the objective does not make a significant distinction between a good and poor hierarchical clustering in metric spaces. Motivated by this, the paper develops a new global objective for hierarchical clustering in Euclidean space. The objective captures the criterion that has motivated the use of divisive clustering algorithms: that when a split happens, points in the same cluster should be more similar than points in different clusters. Moreover, this objective gives reasonable results on ground-truth inputs for hierarchical clustering. The paper builds a theoretical connection between this objective and the bisecting k-means algorithm. This paper proves that the optimal 2-means solution results in a constant approximation for the objective. This is the first paper to show the bisecting k-means algorithm optimizes a natural global objective over the entire tree.

PDF Details

NeurIPS Conference 2020 Conference Paper

Fair Hierarchical Clustering

  • Sara Ahmadian
  • Alessandro Epasto
  • Marina Knittel
  • Ravi Kumar
  • Mohammad Mahdian
  • Benjamin Moseley
  • Philip Pham
  • Sergei Vassilvitskii

As machine learning has become more prevalent, researchers have begun to recognize the necessity of ensuring machine learning systems are fair. Recently, there has been an interest in defining a notion of fairness that mitigates over-representation in traditional clustering. In this paper we extend this notion to hierarchical clustering, where the goal is to recursively partition the data to optimize a specific objective. For various natural objectives, we obtain simple, efficient algorithms to find a provably good fair hierarchical clustering. Empirically, we show that our algorithms can find a fair hierarchical clustering, with only a negligible loss in the objective.

PDF Details

SODA Conference 2020 Conference Paper

Online Scheduling via Learned Weights

  • Silvio Lattanzi
  • Thomas Lavastida
  • Benjamin Moseley
  • Sergei Vassilvitskii

Online algorithms are a hallmark of worst case optimization under uncertainty. On the other hand, in practice, the input is often far from worst case, and has some predictable characteristics. A recent line of work has shown how to use machine learned predictions to circumvent strong lower bounds on competitive ratios in classic online problems such as ski rental and caching. We study how predictive techniques can be used to break through worst case barriers in online scheduling. The makespan minimization problem with restricted assignments is a classic problem in online scheduling theory. Worst case analysis of this problem gives Ω(log m ) lower bounds on the competitive ratio in the online setting. We identify a robust quantity that can be predicted and then used to guide online algorithms to achieve better performance. Our predictions are compact in size, having dimension linear in the number of machines, and can be learned using standard off the shelf methods. The performance guarantees of our algorithms depend on the accuracy of the predictions, given predictions with error η, we show how to construct O (log η ) competitive fractional assignments. We then give an online algorithm that rounds any fractional assignment into an integral schedule. Our algorithm is O ((log log m ) 3 )-competitive and we give a nearly matching Ω(log log m ) lower bound for online rounding algorithms. 1 Altogether, we give algorithms that, equipped with predictions with error η, achieve O (log η (log log m ) 3 ) competitive ratios, breaking the Ω(log m ) lower bound even for moderately accurate predictions.

Details

NeurIPS Conference 2019 Conference Paper

Backprop with Approximate Activations for Memory-efficient Network Training

  • Ayan Chakrabarti
  • Benjamin Moseley

Training convolutional neural network models is memory intensive since back-propagation requires storing activations of all intermediate layers. This presents a practical concern when seeking to deploy very deep architectures in production, especially when models need to be frequently re-trained on updated datasets. In this paper, we propose a new implementation for back-propagation that significantly reduces memory usage, by enabling the use of approximations with negligible computational cost and minimal effect on training performance. The algorithm reuses common buffers to temporarily store full activations and compute the forward pass exactly. It also stores approximate per-layer copies of activations, at significant memory savings, that are used in the backward pass. Compared to simply approximating activations within standard back-propagation, our method limits accumulation of errors across layers. This allows the use of much lower-precision approximations without affecting training accuracy. Experiments on CIFAR-10, CIFAR-100, and ImageNet show that our method yields performance close to exact training, while storing activations compactly with as low as 4-bit precision.

PDF Details

NeurIPS Conference 2019 Conference Paper

Cost Effective Active Search

  • Shali Jiang
  • Roman Garnett
  • Benjamin Moseley

We study a special paradigm of active learning, called cost effective active search, where the goal is to find a given number of positive points from a large unlabeled pool with minimum labeling cost. Most existing methods solve this problem heuristically, and few theoretical results have been established. We adopt a principled Bayesian approach for the first time. We first derive the Bayesian optimal policy and establish a strong hardness result: the optimal policy is hard to approximate, with the best-possible approximation ratio lower bounded by $\Omega(n^{0. 16})$. We then propose an efficient and nonmyopic policy using the negative Poisson binomial distribution. We propose simple and fast approximations for computing its expectation, which serves as an essential role in our proposed policy. We conduct comprehensive experiments on various domains such as drug and materials discovery, and demonstrate that our proposed search procedure is superior to the widely used greedy baseline.

PDF Details

NeurIPS Conference 2018 Conference Paper

Efficient nonmyopic batch active search

  • Shali Jiang
  • Gustavo Malkomes
  • Matthew Abbott
  • Benjamin Moseley
  • Roman Garnett

Active search is a learning paradigm for actively identifying as many members of a given class as possible. A critical target scenario is high-throughput screening for scientific discovery, such as drug or materials discovery. In these settings, specialized instruments can often evaluate \emph{multiple} points simultaneously; however, all existing work on active search focuses on sequential acquisition. We bridge this gap, addressing batch active search from both the theoretical and practical perspective. We first derive the Bayesian optimal policy for this problem, then prove a lower bound on the performance gap between sequential and batch optimal policies: the ``cost of parallelization. '' We also propose novel, efficient batch policies inspired by state-of-the-art sequential policies, and develop an aggressive pruning technique that can dramatically speed up computation. We conduct thorough experiments on data from three application domains: a citation network, material science, and drug discovery, testing all proposed policies (14 total) with a wide range of batch sizes. Our results demonstrate that the empirical performance gap matches our theoretical bound, that nonmyopic policies usually significantly outperform myopic alternatives, and that diversity is an important consideration for batch policy design.

PDF Details

NeurIPS Conference 2017 Conference Paper

Approximation Bounds for Hierarchical Clustering: Average Linkage, Bisecting K-means, and Local Search

  • Benjamin Moseley
  • Joshua Wang

Hierarchical clustering is a data analysis method that has been used for decades. Despite its widespread use, the method has an underdeveloped analytical foundation. Having a well understood foundation would both support the currently used methods and help guide future improvements. The goal of this paper is to give an analytic framework to better understand observations seen in practice. This paper considers the dual of a problem framework for hierarchical clustering introduced by Dasgupta. The main result is that one of the most popular algorithms used in practice, average linkage agglomerative clustering, has a small constant approximation ratio for this objective. Furthermore, this paper establishes that using bisecting k-means divisive clustering has a very poor lower bound on its approximation ratio for the same objective. However, we show that there are divisive algorithms that perform well with respect to this objective by giving two constant approximation algorithms. This paper is some of the first work to establish guarantees on widely used hierarchical algorithms for a natural objective function. This objective and analysis give insight into what these popular algorithms are optimizing and when they will perform well.

PDF Details

AAMAS Conference 2017 Conference Paper

Cooperative Set Function Optimization Without Communication or Coordination

  • Gustavo Malkomes
  • Kefu Lu
  • Blakeley Hoffman
  • Roman Garnett
  • Benjamin Moseley
  • Richard Mann

We introduce a new model for cooperative agents that seek to optimize a common goal without communication or coordination. Given a universe of elements V, a set of agents, and a set function f, we ask each agent i to select a subset Si ⊂ V such that the size of Si is constrained (i. e. , |Si| < k). The goal is for the agents to cooperatively choose the sets Si to maximize the function evaluated at the union of these sets, ∪iSi; we seek max f(∪iSi). We assume the agents can neither communicate nor coordinate how they choose their sets. This model arises naturally in many real-world settings such as swarms of surveillance robots and colonies of foraging insects. Even for simple classes of set functions, there are strong lower bounds on the achievable performance of coordinating deterministic agents. We show, surprisingly, that for the fundamental class of submodular set functions, there exists a near-optimal distributed algorithm for this problem that does not require communication. We demonstrate that our algorithm performs nearly as well as recently published algorithms that allow full coordination.

PDF

STOC Conference 2017 Conference Paper

Efficient massively parallel methods for dynamic programming

  • Sungjin Im
  • Benjamin Moseley
  • Xiaorui Sun

Modern science and engineering is driven by massively large data sets and its advance heavily relies on massively parallel computing platforms such as Spark, MapReduce, and Hadoop. Theoretical models have been proposed to understand the power and limitations of such platforms. Recent study of developed theoretical models has led to the discovery of new algorithms that are fast and efficient in both theory and practice, thereby beginning to unlock their underlying power. Given recent promising results, the area has turned its focus on discovering widely applicable algorithmic techniques for solving problems efficiently.

Details

ICML Conference 2017 Conference Paper

Efficient Nonmyopic Active Search

  • Shali Jiang 0001
  • Gustavo Malkomes
  • Geoff Converse
  • Alyssa Shofner
  • Benjamin Moseley
  • Roman Garnett

Active search is an active learning setting with the goal of identifying as many members of a given class as possible under a labeling budget. In this work, we first establish a theoretical hardness of active search, proving that no polynomial-time policy can achieve a constant factor approximation ratio with respect to the expected utility of the optimal policy. We also propose a novel, computationally efficient active search policy achieving exceptional performance on several real-world tasks. Our policy is nonmyopic, always considering the entire remaining search budget. It also automatically and dynamically balances exploration and exploitation consistent with the remaining budget, without relying on a parameter to control this tradeoff. We conduct experiments on diverse datasets from several domains: drug discovery, materials science, and a citation network. Our efficient nonmyopic policy recovers significantly more valuable points with the same budget than several alternatives from the literature, including myopic approximations to the optimal policy.

Details

SODA Conference 2017 Conference Paper

Fair Scheduling via Iterative Quasi-Uniform Sampling

  • Sungjin Im
  • Benjamin Moseley

In the paper we consider minimizing the ℓ k -norms of flow time on a single machine offline using a preemptive scheduler for k ≥ 1. We show the first O ( 1)- approximation for the problem, improving upon the previous best O (log log P)-approximation by Bansal and Pruhs (FOCS 09 and SICOMP 14) where P is the ratio of the maximum job size to the minimum. Our main technical ingredient is a novel combination of quasi-uniform sampling and iterative rounding, which is of interest in its own right.

Details

SODA Conference 2016 Conference Paper

Scheduling Parallel DAG Jobs Online to Minimize Average Flow Time

  • Kunal Agrawal 0001
  • Jing Li 0025
  • Kefu Lu
  • Benjamin Moseley

In this work, we study the problem of scheduling parallelizable jobs online with an objective of minimizing average flow time. Each parallel job is modeled as a DAG where each node is a sequential task and each edge represents dependence between tasks. Previous work has focused on a model of parallelizability known as the arbitrary speed-up curves setting where a scalable algorithm is known. However, the DAG model is more widely used by practitioners, since many jobs generated from parallel programming languages and libraries can be represented in this model. However, little is known for this model in the online setting with multiple jobs. The DAG model and the speed-up curve models are incomparable and algorithmic results from one do not immediately imply results for the other. Previous work has left open the question of whether an online algorithm can be O (1)-competitive with O (1)-speed for average flow time in the DAG setting. In this work, we answer this question positively by giving a scalable algorithm which is (1 + ∊)-speed -competitive for any ∊ > 0. We further introduce the first greedy algorithm for scheduling parallelizable jobs — our algorithm is a generalization of the shortest jobs first algorithm. Greedy algorithms are among the most useful in practice due to their simplicity. We show that this algorithm is (2 + ∊)-speed -competitive for any ∊ > 0.

Details

SODA Conference 2015 Conference Paper

A Dynamic Programming Framework for Non-Preemptive Scheduling Problems on Multiple Machines [Extended Abstract]

  • Sungjin Im
  • Shi Li 0001
  • Benjamin Moseley
  • Eric Torng

In this paper, we consider a variety of scheduling problems where n jobs with release times are to be scheduled non-preemptively on a set of m identical machines. The problems considered are machine minimization, (weighted) throughput maximization and min-sum objectives such as (weighted) flow time and (weighted) tardiness. We develop a novel quasi-polynomial time dynamic programming framework that gives O (l)-speed O (l)-approximation algorithms for the offline versions of machine minimization and min-sum problems. For the weighted throughput problem, the framework gives a (1 + ε)-speed (1 – ε)-approximation algorithm. The generic DP is based on improving a naïve exponential time DP by developing a sketching scheme that compactly and accurately approximates parameters used in the DP states. We show that the loss of information due to the sketching scheme can be offset with limited resource augmentation. This framework is powerful and flexible, allowing us to apply it to this wide range of scheduling objectives and settings. We also provide new insight into the relative power of speed augmentation versus machine augmentation for non-preemptive scheduling problems; specifically, we give new evidence for the power and importance of extra speed for some non-preemptive scheduling problems. This novel DP framework leads to many new algorithms with improved results that solve many open problems, albeit with quasi-polynomial running times. We highlight our results as follows. For the problems with min-sum objectives, we give the first O (l)-speed O (l)-approximation algorithms for the multiple-machine setting. Even for the single machine case, we reduce both the resource augmentation required and the approximation ratios. In particular, our approximation ratios are either 1 or 1 + ε. Most of our algorithms use speed 1 + e or 2 + ε. We also resolve an open question (albeit with a quasi-polynomial time algorithm) of whether less than 2-speed could be used to achieve an O (1)-approximation for flow time. New techniques are needed to address this open question since it was proven that previous techniques are insufficient. We answer this open question by giving an algorithm that achieves a (1 + ε)-speed 1-approximation for flow time and (1 + ε)-speed (1 + ε)-approximation for weighted flow time. For the machine minimization problem, we give the first result using constant resource augmentation by showing a (1 + ε)-speed 2-approximation, and the first result only using speed augmentation and no additional machines by showing a (2 + ε)-speed 1-approximation. We complement our positive results for machine minimization by considering the discrete variant of the problem and show that no algorithm can use speed augmentation less than 2 log 1–ε and achieve approximation less than O (log log n ) for any constant ε > 0 unless NP admits quasi-polynomial time optimal algorithms. Thus, our results show a stark contrast between the two settings. In one, constant speed augmentation is sufficient whereas in the other, speed augmentation is essentially not effective.

Details

NeurIPS Conference 2015 Conference Paper

Fast Distributed k-Center Clustering with Outliers on Massive Data

  • Gustavo Malkomes
  • Matt Kusner
  • Wenlin Chen
  • Kilian Weinberger
  • Benjamin Moseley

Clustering large data is a fundamental problem with a vast number of applications. Due to the increasing size of data, practitioners interested in clustering have turned to distributed computation methods. In this work, we consider the widely used k-center clustering problem and its variant used to handle noisy data, k-center with outliers. In the noise-free setting we demonstrate how a previously-proposed distributed method is actually an O(1)-approximation algorithm, which accurately explains its strong empirical performance. Additionally, in the noisy setting, we develop a novel distributed algorithm that is also an O(1)-approximation. These algorithms are highly parallel and lend themselves to virtually any distributed computing framework. We compare both empirically against the best known noisy sequential clustering methods and show that both distributed algorithms are consistently close to their sequential versions. The algorithms are all one can hope for in distributed settings: they are fast, memory efficient and they match their sequential counterparts.

PDF Details

SODA Conference 2014 Conference Paper

New Approximations for Reordering Buffer Management

  • Sungjin Im
  • Benjamin Moseley

In this paper we consider the buffer reordering management problem. In this model there are n elements that arrive over time with different colors. There is a buffer that can store up to k elements and when the buffer becomes full an element must be output. If an element is output that has a color different from the previous element, a cost depending on the color must be paid. This cost could be uniform or non-uniform over colors; these are called unweighted and weighted cases, respectively. The goal is to reorder elements within the buffer before outputting them to minimize the total cost incurred. There has been a search over the last decade to resolve the complexity of this problem online and offline. Very recently, there has been substantial progress for the unweighted case – an O (1)-approximation algorithm and an O (log log k )-competitive randomized algorithm were given [6, 7]. These results resolve the complexity of the unweighted buffer problem, up to constant factors, since the problem is NP-Hard and there is a matching lower bound on the competitive ratio. However, the progress for the weighted case has not been as satisfactory as for the unweighted case. Our main result is a randomized O (loglog kγ )-approximation for the weighted case, which gives an exponential improvement over the previously best known result of O ( y /l ogk ) which assumed γ = poly( k ). Here γ is the ratio of the maximum to minimum weight. We also revisit the unweighted case and give an improved randomized 66. 0823-approximation which improves (modestly) upon the approximation guarantee given in [6]. The algorithm and analysis we use for the unweighted case was done independently of [6]. We believe that our new interpretation of the problem and our analysis of an underlying random process could be of potential use in other settings.

Details

IJCAI Conference 2013 Conference Paper

Bargaining for Revenue Shares on Tree Trading Networks

  • Arpita Ghosh
  • Satyen Kale
  • Kevin Lang
  • Benjamin Moseley

We study trade networks with a tree structure, where a seller with a single indivisible good is connected to buyers, each with some value for the good, via a unique path of intermediaries. Agents in the tree make multiplicative revenue share offers to their parent nodes, who choose the best offer and offer part of it to their parent, and so on; the winning path is determined by who finally makes the highest offer to the seller. In this paper, we investigate how these revenue shares might be set via a natural bargaining process between agents on the tree, specifically, egalitarian bargaining between endpoints of each edge in the tree. We investigate the fixed point of this system of bargaining equations and prove various desirable for this solution concept, including (i) existence, (ii) uniqueness, (iii) efficiency, (iv) membership in the core, (v) strict monotonicity, (vi) polynomial-time computability to any given accuracy. Finally, we present numerical evidence that asynchronous dynamics with randomly ordered updates always converges to the fixed point, indicating that the fixed point shares might arise from decentralized bargaining amongst agents on the trade network.

PDF Details DOI