Benjamin Moseley

Benjamin Moseley

Auto-generated profile, based on publicly available information

Benjamin Moseley

Carnegie Mellon University, Pittsburgh, PA, USA

Research Focus & Metrics

Academic Career Length

19Years (2008-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 May 2020 in Mathematics of Operations Research
Verified
Journal Article
Closed access
VGVarun Gupta
Varun Gupta
BMBenjamin Moseley
Benjamin Moseley
MUMarc Uetz
Marc Uetz
QXQiaomin Xie
Qiaomin Xie
This paper establishes performance guarantees for online algorithms that schedule stochastic, nonpreemptive jobs on unrelated machines to minimize the expected total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case and required linear or convex programming relaxations for the assignment of jobs to machines. The algorithms introduced in this paper are purely combinatorial. The performance bounds are of the same order of magnitude as those of earlier work and depend linearly on an upper bound on the squared coefficient of variation of the jobs’ processing times. Specifically for deterministic processing times, without and with release times, the competitive ratios are 4 and 6, respectively. As to the technical contribution, this paper shows how dual fitting techniques can be used for stochastic and nonpreemptive scheduling problems.


1 January 2022 in Operations Research Letters
Verified
Journal Article
Open access
BMBenjamin Moseley
Benjamin Moseley
SVShai Vardi
Shai Vardi

28 September 2023 in Foundations and Trends® in Optimization
Verified
Journal Article
Open access
PDF file
SISungjin Im
Sungjin Im
RKRavi Kumar
Ravi Kumar
SLSilvio Lattanzi
Silvio Lattanzi
BMBenjamin Moseley
Benjamin Moseley
SVSergei Vassilvitskii
Sergei Vassilvitskii
The algorithms community has been modeling the underlying key features and constraints of massively parallel frameworks and using these models to discover new algorithmic techniques tailored to them. This monograph focuses on the Massively Parallel Model of Computation (MPC) framework, also known as the MapReduce model in the literature. It describes algorithmic tools that have been developed to leverage the unique features of the MPC framework. These tools were chosen for their broad applicability, as they can serve as building blocks to design new algorithms. The monograph is not exhaustive and includes topics such as partitioning and coresets, sample and prune, dynamic programming, round compression, and lower bounds.

13 June 2015
Verified
Conference Paper
Open access
SISungjin Im
Sungjin Im
JKJanardhan Kulkarni
Janardhan Kulkarni
BMBenjamin Moseley
Benjamin Moseley
Fairness is an important criterion considered in scheduling together with overall job latency. Round Robin is a popular scheduling policy that distributes resources to jobs equally at any point in time guaranteeing instantaneous fairness of jobs. In this paper we give the first analysis of Round Robin for the L_2-norm of flow time and show that it is O(1)-speed O(1)-competitive on multiple machines. The L_2-norm is a popular scheduling objective that makes a natural balance between temporal fairness and jobs latency. Prior to our work, Round Robin has not been analyzed for the L_2-norm even in the single machine setting. Our result establishes that Round Robin is fair not only instantaneously but also temporarily.

1 August 2021 in Mathematics of Operations Research
Verified
Journal Article
Closed access
VGVarun Gupta
Varun Gupta
BMBenjamin Moseley
Benjamin Moseley
MUMarc Uetz
Marc Uetz
QXQiaomin Xie
Qiaomin Xie
This corrigendum fixes an incorrect claim in the paper Gupta et al. [Gupta V, Moseley B, Uetz M, Xie Q (2020) Greed works—online algorithms for unrelated machine stochastic scheduling. Math. Oper. Res. 45(2):497–516.], which led us to claim a performance guarantee of 6 for a greedy algorithm for deterministic online scheduling with release times on unrelated machines. The result is based on an upper bound on the increase of the objective function value when adding an additional job [ ] to a machine [ ] (Gupta et al., lemma 6). It was pointed out by Sven Jäger from Technische Universität Berlin that this upper bound may fail to hold. We here present a modified greedy algorithm and analysis, which leads to a performance guarantee of 7.216 instead. Correspondingly, also the claimed performance guarantee of [ ] in theorem 4 of Gupta et al. for the stochastic online problem has to be corrected. We obtain a performance bound [ ].