Secure Network Coding via Filtered Secret Sharing ∗ (2009)
Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein
We study the problem of using a multicast network code to transmit information securely in the presence of a “wire-tap ” adversary who can eavesdrop on a bounded number of network edges. We...
Jon Feldman, Cliff Stein, Tal Malkin, Rocco A. Servedio, Martin J. Wainwright
We show that for low-density parity-check (LDPC) codes with sufficient expansion, the
On the Capacity of Secure Network Coding (2008)
Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein
We consider the problem of using a multicast network code to transmit information securely in the presence of a "wire-tap " adversary who can eavesdrop on a bounded number of...
On Distributing Symmetric Streaming Computations (2008)
Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein
A common approach for dealing with large data sets is to stream over the input in one pass, and perform computations using sublinear resources. For truly massive data sets, however, even making a...
On Distributing Symmetric Streaming Computations (2008)
Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein
A common approach for dealing with large data sets is to stream over the input in one pass, and perform computations using sublinear resources. For truly massive data sets, however, even making a...
Scheduling an Industrial Production Facility (2008)
Eyjolfur Asgeirsson, Jonathan Berry, Cynthia A. Phillips, David J, Cliff Stein, Joel Wein
Abstract. Managing an industrial production facility requires carefully allocating limited resources, and gives rise to large, potentially complicated scheduling problems. In this paper we consider a...
Vertex Cover Approximations on Random Graphs. (2008)
Eyjolfur Asgeirsson, Cliff Stein
Abstract. The vertex cover problem is a classical NP-complete problem for which the best worst-case approximation ratio is 2 − o(1). In this paper, we use a collection of simple graph...
Existence Theorems, Lower Bounds and Algorithms for Scheduling to Meet Two Objectives (2008)
April Ilasala, Cliff Stein, Eric Torng, Patchrawat Uthaisombut
1 Introduction Speed Scaling for Weighted Flow Time (2008)
Nikhil Bansal, Kirk Pruhs, Cliff Stein
In addition to the traditional goal of efficiently managing time and space, many computers now need to
© 2004 INFORMS Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut (2008)
David R. Karger, Philip Klein, Cliff Stein, Mikkel Thorup, Neal E. Young
Given an undirected graph with edge costs and a subset of k ≥ 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others....
Mitigating the Effect of Free-Riders in BitTorrent using Trusted Agents (2008)
Sherman, Alex, Stavrou, Angelos, Nieh, Jason, Stein, Cliff
Even though Peer-to-Peer (P2P) systems present a cost-effective and scalable solution to content distribution, most entertainment, media and software, content providers continue to rely on expensive,...
David R. Karger, Philip Klein, Cliff Stein, Mikkel Thorup, Neal E. Young
Given an undirected graph with edge costs and a subset of
Optimal Time-Critical Scheduling Via Resource Augmentation (2007)
Extend Ed, Cynthia A. Phillips, Cliff Stein, Eric Torng, Joel Wein
) Cynthia A. Phillips Cliff Stein y Eric Torng z Joel Wein x Abstract We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting,...
Andrew V. Goldberg, Jeffrey D. Oldham, Serge Plotkin, Cliff Stein
Abstract. The minimum-cost multicommodity flow problem involves simultaneously shipping multiple commodities through a single network so that the total flow obeys arc capacity constraints and has...
David R. Karger, Philip Klein, Cliff Stein, Mikkel Thorup, Neal E. Young
Given an undirected graph with edge costs and a subset of k 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others. The...
Andrew Goldberg, Jeffrey D. Oldham, Serge Plotkin, Cliff Stein
The minimum-cost multicommodity flow problem involves simultaneously shipping multiple commodities through a single network so that the total flow obeys arc capacity constraints and has minimum cost....
Aequitas: A Trusted P2P System for Paid Content Delivery (2007)
Sherman, Alex, Chawla, Japinder, Nieh, Jason, Stein, Cliff, Sarma, Justin
P2P file-sharing has been recognized as a powerful and efficient distribution model due to its ability to leverage users' upload bandwidth. However, companies that sell digital content on-line are...
Can P2P Replace Direct Download for Content Distribution (2007)
Sherman, Alex, Stavrou, Angelos, Nieh, Jason, Stein, Cliff, Keromytis, Angelos D.
While peer-to-peer (P2P) file-sharing is a powerful and cost-effective content distribution model, most paid-for digital-content providers (CPs) rely on direct download to deliver their content. CPs...
Budget Optimization in Search-Based Advertising Auctions (2006)
Feldman, Jon, Muthukrishnan, S., Pal, Martin, Stein, Cliff
Internet search companies sell advertisement slots based on users' search queries via an auction. While there has been a lot of attention on the auction process and its game-theoretic aspects, our...
A Case for P2P Delivery of Paid Content (2006)
Sherman, Alex, Stavrou, Angelos, Nieh, Jason, Stein, Cliff, Keromytis, Angelos D.
P2P file sharing provides a powerful content distribution model by leveraging users' computing and bandwidth resources. However, companies have been reluctant to rely on P2P systems for paid content...
On the Complexity of Processing Massive, Unordered, Distributed Data (2006)
Feldman, Jon, Muthukrishnan, S., Sidiropoulos, Anastasios, Stein, Cliff, Svitkina, Zoya
An existing approach for dealing with massive data sets is to stream over the input in few passes and perform computations with sublinear resources. This method does not work for truly massive data...
On the complexity of processing massive, unordered, distributed data (2006)
Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein, Zoya Svitkina
The popular model for processing massive data sets is the streaming model in which the processor makes a pass over the input with polylog(n)-space. However, with current data sets, even making a...
LP decoding achieves capacity (2005)
We give a linear programming (LP) decoder that achieves the capacity (optimal rate) of a wide range of probabilistic binary communication channels. This is the first such result for LP decoding. More...
LP Decoding Achieves Capacity (2004)
We give a linear programming (LP) decoder that achieves the capacity (optimal rate) of a wide range of probabilistic binary communication channels. This is the first such result for LP decoding. More...
LP decoding corrects a constant fraction of errors (2004)
Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein, Martin J. Wainwright
Abstract—We show that for low-density parity-check (LDPC) codes whose Tanner graphs have sufficient expansion, the linear programming (LP) decoder of Feldman, Karger, and Wainwright can correct a...
On the capacity of secure network coding (2004)
Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein
We consider the problem of using a multicast network code to transmit information securely in the presence of a “wire-tap ” adversary who can eavesdrop on a bounded number of network edges. Cai...
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut (2002)
Karger, David, Klein, Phil, Stein, Cliff, Thorup, Mikkel, Young, Neal E.
The multiway-cut problem is, given a weighted graph and k >= 2 terminal nodes, to find a minimum-weight set of edges whose removal separates all the terminals. The problem is NP-hard, and even...
Improved Bicriteria Existence Theorems for Scheduling (2002)
Aslam, Javed, Rasala, April, Stein, Cliff, Young, Neal
Two common objectives for evaluating a schedule are the makespan, or schedule length, and the average completion time. This short note gives improved bounds on the existence of schedules that...
Reducing mass degeneracy in SAR by MS by stable isotopic labeling (2000)
Chris Bailey-kellogg, Cliff Stein, Bruce Randall Donald
Mass spectrometry (MS) promises to be an invaluable tool for functional genomics, by supporting low-cost, high-throughput experiments. However, large-scale MS faces the potential problem of mass...
Approximation algorithms for the minimum bends traveling salesman problem (2000)
The problem of traversing a set of points in the order that minimizes the total distance traveled (traveling salesman problem) is one of the most famous and well-studied problems in combinatorial...
Reducing Mass Degeneracy in SAR by MS by Stable Isotopic Labeling (2000)
Chris Bailey-kellogg, John J. Kelley, Cliff Stein, Bruce Randall Donald
Mass spectrometry (MS) promises to be an invaluable tool for functional genomics, by supporting lowcost, high-throughput experiments. However, largescale MS faces the potential problem of mass...
Approximation algorithms for the minimum bends traveling salesman problem (2000)
The problem of traversing a set of points in the order that minimizes the total distance traveled (traveling salesman problem) is one of the most famous and well-studied problems in combinatorial...
Approximation algorithms for the minimum bends traveling salesman problem (2000)
The problem of traversing a set of points in the order that minimizes the total distance traveled (traveling salesman problem) is one of the most famous and well-studied problems in combinatorial...
Improved bicriteria existence theorems for scheduling (1999)
Javed Aslam, April Rasala, Cliff Stein, Neal Young
Two common objectives for evaluating a scheduleare the makespan, or schedule length, and the average completion time. In this note, we give improved boundson the existence of schedules that...
Approximation schemes for minimizing average weighted completion time with release dates (1999)
Foto Afrati, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, ...
We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation...
Rounding algorithms for a geometric embedding of minimum multiway cut (1999)
David R. Karger, Philip Klein, Cliff Stein, Mikkel Thorup, Neal E. Young
Given an undirected graph with edge costs and a subset of k 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others. The...
Approximation schemes for minimizing average weighted completion time with release dates (1999)
Foto Afrati, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, ...
We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation...
Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates (1999)
Foto Afrati Evripidis, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, ...
We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation...
Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates (1999)
Foto Afrati, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, ...
We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation...
Improved bicriteria existence theorems for scheduling (1999)
Javed Aslam, April Rasala, Cliff Stein, Neal Young
Two common objectives for evaluating a schedule are the makespan, or schedule length, and the average completion time. In this note, we give improved bounds on the existence of schedules that...
Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem (1998)
Cynthia Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, Joel Wein
We consider the problem of scheduling n jobs with release dates on m identical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average completion...
Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem (1998)
Cynthia Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, Joel Wein
We consider the problem of scheduling n jobs with release dates on m identical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average completion...
Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem (1998)
Cynthia Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, Joel Wein
We consider the problem of scheduling n jobs with release dates on m identical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average completion...
Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem (1998)
Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, Joel Wein
We consider the problem of scheduling n jobs with release dates on m identical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average completion...
Andrew Goldberg, Jeffrey D. Oldham, Serge Plotkin, Cliff Stein
The minimum-cost multicommodity flow problem involves simultaneously shipping multiple commodities through a single network so that the total flow obeys arc capacity constraints and has minimum cost....
Improved bounds on relaxations of a parallel machine scheduling problem (1998)
Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein
Abstract. We consider the problem of scheduling n jobs with release dates on m identical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average...
Improved bounds on relaxations of a parallel machine scheduling problem (1998)
Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, Joel Wein
Abstract We consider the problem of scheduling n jobs with release dates on m identical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average...
Experimental study of minimum cut algorithms (1997)
Chandra S. Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, Cliff Stein
Recently, several new algorithms have been developed for the minimum cut problem. These algorithms are very different from the earlier ones and from each other and substantially improve worst-case...
We give a simple proof that, for any instance of a very general class of scheduling problems, there exists a schedule of makespan at most twice that of the optimal possible and of total weighted...
Optimal Time-Critical Scheduling Via Resource Augmentation (1997)
Cynthia A. Phillips, Cliff Stein, Eric Torng, Joel Wein
We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting, and scheduling to provide good response time in a number of scheduling...
Experimental Study of Minimum Cut Algorithms (1997)
Chandra S. Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, Cliff Stein
Recently, several new algorithms have been developed for the minimum cut problem. These algorithms are very different from the earlier ones and from each other and substantially improve the...
We give a simple proof that, for any instance of a very general class of scheduling problems, there exists a schedule of makespan at most twice that of the optimal possible and of total weighted...
Optimal Time-Critical Scheduling Via Resource Augmentation (Extended Abstract) (1997)
Cynthia A. Phillips, Cliff Stein, Eric Torng, Joel Wein
) Cynthia A. Phillips Cliff Stein y Eric Torng z Joel Wein x Abstract We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting,...
Experimental Study of Minimum Cut Algorithms (1997)
Chandra S. Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, Cliff Stein
Recently, several new algorithms have been developed for the minimum cut problem. These algorithms are very different from the earlier ones and from each other and substantially improve worst-case...
David Karger, Cliff Stein, Joel Wein
Introduction Scheduling theory is concerned with the optimal allocation of scarce resources to activities over time. The practice of this field dates to the first time two humans contended for a...
Experimental Study of Minimum Cut Algorithms (1997)
Chandra Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, Cliff Stein
Recently, several new algorithms have been developed for the minimum cut problem. These algorithms are very different from the earlier ones and from each other and substantially improve worst-case...
We give a simple proof that, for any instance of a very general class of scheduling problems, there exists a schedule of makespan at most twice that of the optimal possible and of total weighted...
Optimal Time-Critical Scheduling Via Resource Augmentation (Extended Abstract) (1997)
Cynthia A. Phillips, Cliff Stein, Eric Torng, Joel Wein
We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting, and scheduling to provide good response time in a number of scheduling...
Optimal time-critical scheduling via resource augmentation (1997)
Cynthia A. Phillips, Cliff Stein, Eric Torng, Joel Wein
Abstract We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting, and scheduling to provide good response time in a number of...
Optimal time-critical scheduling via resource augmentation (1997)
Cynthia A. Phillips, Cliff Stein, Eric Torng, Joel Wein
Abstract We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting, and scheduling to provide good response time in a number of...
Improved scheduling algorithms for minsum criteria (1996)
Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, Joel Wein
Abstract. We consider the problem of finding near-optimal solutions for a variety of NP-hard scheduling problems for which the objective is to minimize the total weighted completion time. Recent work...
Improved Scheduling Algorithms for Minsum Criteria (1996)
Exte Nd Ed, Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, ...
) Soumen Chakrabarti ? Cynthia A. Phillips ?? Andreas S. Schulz ??? David B. Shmoys y Cliff Stein z Joel Wein x Abstract. We consider the problem of finding near-optimal solutions for a variety of...
Improved Scheduling Algorithms for Minsum Criteria (1996)
Extend Ed, Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, ...
) Soumen Chakrabarti ? Cynthia A. Phillips ?? Andreas S. Schulz ??? David B. Shmoys y Cliff Stein z Joel Wein x Abstract. We consider the problem of finding near-optimal solutions for a variety of...
Improved Scheduling Algorithms for Minsum Criteria (Extended Abstract) (1996)
Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, Joel Wein
We consider the problem of finding near-optimal solutions for a variety of NP-hard scheduling problems for which the objective is to minimize the total weighted completion time. Recent work has led...