Benjamin Moseley

Benjamin Moseley
Are you Benjamin Moseley?

Claim your profile, edit publications, add additional information:

Contact Details

Name
Benjamin Moseley
Affiliation
Location

Pubs By Year

Pub Categories

 
Computer Science - Data Structures and Algorithms (8)
 
Computer Science - Distributed; Parallel; and Cluster Computing (1)
 
Computer Science - Databases (1)
 
Computer Science - Artificial Intelligence (1)
 
Computer Science - Computer Science and Game Theory (1)

Publications Authored By Benjamin Moseley

We derive the first performance guarantees for a combinatorial online algorithm that schedules stochastic, non-preemptive jobs on unrelated machines to minimize the expectation of the total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case, and required sophisticated linear or convex programming relaxations for the assignment of jobs to machines. Our algorithm is purely combinatorial, and therefore it also works for the online setting. Read More

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. Read More

We consider computing optimal k-norm preemptive schedules of jobs that arrive over time. In particular, we show that computing the optimal k-norm of flow schedule, is strongly NP-hard for k in (0, 1) and integers k in (1, infinity). Further we show that computing the optimal k-norm of stretch schedule, is strongly NP-hard for k in (0, 1) and integers k in (1, infinity). Read More

Over half a century old and showing no signs of aging, k-means remains one of the most popular data processing algorithms. As is well-known, a proper initialization of k-means is crucial for obtaining a good final solution. The recently proposed k-means++ initialization algorithm achieves this, obtaining an initial set of centers that is provably close to the optimum solution. Read More

Clustering problems have numerous applications and are becoming more challenging as the size of the data increases. In this paper, we consider designing clustering algorithms that can be used in MapReduce, the most popular programming environment for processing large datasets. We focus on the practical and popular clustering problems, $k$-center and $k$-median. Read More

Due to its optimality on a single machine for the problem of minimizing average flow time, Shortest-Remaining-Processing-Time (\srpt) appears to be the most natural algorithm to consider for the problem of minimizing average flow time on multiple identical machines. It is known that $\srpt$ achieves the best possible competitive ratio on multiple machines up to a constant factor. Using resource augmentation, $\srpt$ is known to achieve total flow time at most that of the optimal solution when given machines of speed $2- \frac{1}{m}$. Read More

In this paper we initiate the study of minimizing power consumption in the broadcast scheduling model. In this setting there is a wireless transmitter. Over time requests arrive at the transmitter for pages of information. Read More

We consider online algorithms for broadcast scheduling. In the pull-based broadcast model there are $n$ unit-sized pages of information at a server and requests arrive online for pages. When the server transmits a page $p$, all outstanding requests for that page are satisfied. Read More

We consider online algorithms for pull-based broadcast scheduling. In this setting there are n pages of information at a server and requests for pages arrive online. When the server serves (broadcasts) a page p, all outstanding requests for that page are satisfied. Read More

In this paper two scheduling models are addressed. First is the standard model (unicast) where requests (or jobs) are independent. The other is the broadcast model where broadcasting a page can satisfy multiple outstanding requests for that page. Read More