Serge Plotkin

We consider the problem of caching web pages with the objective of minimizing latency of access. Demands for web domains/pages are computed using access statis-tics; the frequency with which these...

Abstract (2008)

A Non-Manipulable Trust System Based on (2008)

We develop a framework that allows us to address the issues of admission control and routing in high-speed networks under the restriction that once a call is admitted and routed, it has to proceed to...

Eigentrust Zo Abrams, Zoë Abrams, Robert Mcgrew, Serge Plotkin

this paper [Z. ABRAMS and PLOTKIN 2004] was presented in the Workshop on Economics of P2P Systems 2004. This paper contains new results and focuses on the practical aspects of keeping peers honest in...

MIT (2007)

Rainer Gawlick, Anil Kamath, Serge Plotkin, K. G. Ramakrishnan

We develop a framework that allows us to address the issues of admission control and routing in high-speed networks under the restriction that once a call is admitted and routed, it has to proceed to...

z (2007)

Emerging high speed Broadband Integrated Services Digital Networks (B-ISDN) will carry traffic for services such as video-on-demand and video teleconferencing-- that require resource reservation...

z (2007)

On-Line Routing of Virtual Circuits with Applications to Load Balancing and Machine Scheduling (2007)

We study the problem of distributed online admission control and routing of permanent virtual circuits in a capacitated network. We assume that we have k distinct decision makers, each of which is...

y (2007)

Ashish Goel, Monika R. Henzinger, Google Inc, Serge Plotkin, Eva Tardos

In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of...

James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, Orli Waarts

In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-topoint and multicast) where the goal is to minimize the required bandwidth. We concentrate on the...

2 (2007)

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

x (2007)

Serge Plotkin, Eva Tardos

We consider a variant of the facility location problem with additional interference constraints of the form "not too many facilities can be close to a user". These constraints arise...

z (2007)

Zoe Abrams, Adam Meyerson, Kamesh Munagala, Serge Plotkin

We consider the facility location problem with hard non-uniform upper and lower bounds on the amount of demand that can be routed to any facility. We examine the natural integer programming...

y (2007)

Philip Klein, Serge Plotkin, Clifford Stein, Cambridge Ma, Eva Tardos

Faster approximation algorithms for the unit capacity concurrent

multicommodity (2007)

bounds on the max-flow min-cut ratio for

y (2007)

Andrew V. Goldberg, Jerey D. Oldham, Serge Plotkin, Cli Stein

Minimum-cost multicommodity flow problem is one of the classical optimization problems that arises in a variety of contexts. Applications range from finding optimal ways to route information through...

3 (2007)

Abstract. The minimum-cost multicommodity ow problem involves simultaneously shipping multiple commodities through a single network so that the total ow obeys arc capacity constraints and has minimum...

MIT (2007)

Andrew Goldberg, Jeffrey D. Oldham, Serge Plotkin, Cliff Stein

We develop a framework that allows us to address the issues of admission control and routing in high-speed networks under the restriction that once a call is admitted and routed, it has to proceed to...

3 (2007)

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

Set K-Cover Algorithms for Energy Efficient Monitoring in Wireless Sensor Networks (2003)

Abrams, Zoe, Goel, Ashish, Plotkin, Serge

Wireless sensor networks (WSNs) are emerging as an effective means for environment monitoring. This paper investigates a strategy for energy efficient monitoring in WSNs that partitions the sensors...

Approximation Algorithms for Concave Cost Network Flow Problems (2003)

Kamesh Munagala, Serge Plotkin, Rajeev Motwani

The cost structures for resource allocation in many network design problems obey economies of scale, meaning that the cost per unit resource becomes cheaper as the amount of resources allocated...

Designing networks incrementally (2001)

Web caching using access statistics (2001)

We consider the problem of incrementally designing a network to route demand to a single sink on an underlying metric space. We are given cables whose costs per unit length scale in a concave fashion...

Approximate majorization and fair online load balancing (2001)

We consider the problem of caching web pages with the objective of minimizing latency of access. Demands for web domains/pages are computed using access statistics; the frequency with which these...

Approximate majorization and fair online load balancing (2001)

This paper revisits the greedy online load-balancing algorithm for unrelated 1-1 machines from the viewpoint of fairness. We prove that the greedy approach is globally O(log n)-fair where n is the...

Web caching using access statistics (2001)

This paper relates the notion of fairness in online routing and load balancing to vector majorization as developed by Hardy, Littlewood, and Polya [9]. We define ff-supermajorization as an...

Approximate majorization and fair online load balancing (2001)

We consider the problem of caching web pages with the objective of minimizing latency of access. Demands for web domains/pages are computed using access statistics; the frequency with which these...

This paper relates the notion of fairness in online routing and load balancing to vector majorization as developed by Hardy, Littlewood, and Polya. We define α-supermajorization as an approximate...

Abstract We present the Cost-Distance problem: finding a Steiner tree which optimizes the sum of edge costs along one metric and the sum of source-sink distances along an unrelated second metric. We...

We present the Cost-Distance problem: nding a Steiner tree which optimizes the sum of edge costs along one metric and the sum of source-sink distances along an unrelated second metric. We give the...

Combining Fairness with Throughput: Online Routing with Multiple Objectives (2000)

We present the COST-DISTANCE problem: finding a Steiner tree which optimizes the sum of edge costs along one metric and the sum of source-sink distances along an unrelated second metric. We give the...

Distributed Admission Control, Scheduling, and Routing with Stale Information (2000)

This paper presents online algorithms for routing and bandwidth allocation which simultaneously approximate fair and max-throughput solutions. In fact, the algorithms solve a more difficult problem:...

We study the problem of online admission control and routing of permanent virtual circuits in a capacitated network in the presence of several decision makers with limited communication among them....

Combining fairness with throughput: Online routing with multiple objectives (2000)

Abstract We present the Cost-Distance problem: finding a Steiner tree which optimizes the sum of edge costs along one metric and the sum of source-sink distances along an unrelated second metric. We...

For the case where the algorithm assigns bandwidths, we present an O(log 2 n log

y (2000)

Information

Scheduling data transfers in a network and the set scheduling problem (1999)

We present the Cost-Distance problem: finding a Steiner tree which optimizes the sum of edge costs along one metric and the sum of source-sink distances along an unrelated second metric. We give the...

Goel, Ashish, Henzinger, Monika R., Plotkin, Serge, Tardos, Eva

In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of...

Scheduling data transfers in a network and the set scheduling problem (1999)

Ashish Goel, Monika R. Henzinger, Serge Plotkin, Eva Tardos

In this paper we consider the online ftp problem. The goal is to service a sequence of le transfer requests given bandwidth constraints of the underlying communication network. The main result of the...

Combining Fairness with Throughput: Online Routing with Multiple Objectives (1999)

Scheduling Data Transfers in a Network and the Set Scheduling Problem (1999)

This paper presents online algorithms for routing and bandwidth allocation which simultaneously approximate fair and max-throughput solutions. In fact, the algorithms solve a more difficult problem:...

Ashish Goel, Monika R. Henzinger, Serge Plotkin, Eva Tardos

In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of...

Scheduling Data Transfers in a Network and the Set Scheduling Problem (1999)

Ashish Goel, Monika R. Henzinger, Serge Plotkin, Eva Tardos

In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of...

Scheduling data transfers in a network and the set scheduling problem (1999)

Scheduling data transfers in a network and the set scheduling problem (1999)

In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of...

Fast Approximation Algorithms for Multicommodity Flow Problems, (1998)

In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of...

Leighton, Tom, Makedon, Fillia, Plotkin, Serge, Stein, Clifford, Tardos, Eva, Tragoudas, Spyros

In this paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem. Our algorithms are significantly faster than the best...

Research in Graph Algorithms and Combinatorial Optimization. (1998)

Plotkin, Serge

This project focused on designing fast algorithms for basic combinational optimization problems, including maximum flow, matching, multicommodity flow, and generalized flow. Many important...

Combinatorial Optimization with Applications to Resource Management in Communications Networks (1998)

Plotkin, Serge

The main goal of this project is to develop fundamental algorithmic techniques that can be applied to problems that arise in the context of high speed communications networks. The emphasis is on...

Optimization Problems in High-Speed Networks (1998)

Plotkin, Serge

The main goal of this project is to develop fundamental algorithmic techniques that can be applied to problems that arise in the context of high-speed communication networks. The explosion in the...

Online throughput-competitive algorithm for multicast routing and admission control (1998)

Goel, Ashish, Henzinger, Monika R., Plotkin, Serge

We present the first polylog-competitive online algorithm for the general multicast problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to...

Online throughput-competitive algorithm for multicast routing and admission control (1998)

Scheduling Data Transfers in a Network and the Set Scheduling Problem (1998)

We present the first polylog-competitive online algorithm for the general multicast problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to...

Ashish Goel, Monika R. Henzinger, Serge Plotkin, Eva Tardos

In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of...

Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control (1998)

Ashish Goel, Monika Rauch Henzinger, Serge Plotkin

We present the first polylog-competitive online algorithm for the general multicast problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to...

Scheduling Data Transfers in a Network and the Set Scheduling Problem (1998)

Ashish Goel, Monika R. Henzinger, Serge Plotkin, Eva Tardos

In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of...

An Online Throughput-Competitive Algorithm For Multicast Routing And Admission Control (1998)

Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control (1998)

. We present the first polylog-competitive online algorithm for the general multicast problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to...

An implementation of a combinatorial approximation algorithm for minimum-cost multicommodity flow (1998)

We present the first polylog-competitive online algorithm for the general multicast problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to...

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

Online throughput-competitive algorithm for multicast routing and admission control (1998)

Ashish Goel, Monika R. Henzinger, Google Inc, Serge Plotkin

We present the first polylog-competitive online algorithm for the general multicast admission control and routing problem in the throughput model. The ratio of the number of requests accepted by the...

Online throughput-competitive algorithm for multicast routing and admission control (1998)

Ashish Goel, Monika Rauch Henzinger, Serge Plotkin

We present the first polylog-competitive online algorithm for the general multicast problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to...

Online throughput-competitive algorithm for multicast routing and admission control (1998)

Ashish Goel, Monika Rauch Henzinger, Serge Plotkin

We present the first polylog-competitive online algorithm for the general multicast problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to...

A Parallel Algorithm for Reconfiguring a Multibutterfly Network with Faulty Switches, (1997)

Goldberg, Andrew, Maggs, Bruce, Plotkin, Serge

This paper describes a deterministic algorithm for reconfiguring a multibutterfly network with faulty switches. Unlike previous reconfiguration algorithms, the algorithm is performed entirely by the...

On-Line Routing of Virtual Circuits with Applications to Load Balancing and Machine Scheduling (1997)

James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, Orli Waarts

. In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-to-point and multicast) where the goal is to route all requests while minimizing the required...

On-Line Routing of Virtual Circuits with Applications to Load Balancing and Machine Scheduling (1997)

James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, Orli Waarts

In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-to-point and multicast) where the goal is to route all requests while minimizing the required...

On-Line Routing of Virtual Circuits with Applications to Load Balancing and Machine Scheduling (1997)

James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, Orli Waarts

In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-to-point and multicast) where the goal is to minimize the required bandwidth. We concentrate on the...

Routing and Admission Control in General Topology Networks with Poisson Arrivals (1996)

Andrew V. Goldberg, Serge Plotkin

Emerging high speed networks will carry traffic for services such as video-on-demand and video teleconferencing -- that require resource reservation along the path on which the traffic is sent. High...

By (1995)

ii

Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows (1995)

David Karger, Serge Plotkin

Minimum cost multicommodity flow is an instance of a simpler problem (multicommodity flow) to which a cost constraint has been added. In this paper we present a general scheme for solving a large...

Competitive Routing of Virtual Circuits in ATM networks (1995)

Serge Plotkin

Classical routing and admission control strategies achieve provably good performance by relying on an assumption that the virtual circuits arrival pattern can be described by some a priori known...

Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows (1995)

David Karger, Serge Plotkin

Minimum cost multicommodity flow is an instance of a simpler problem (multicommodity flow) to which a cost constraint has been added. In this paper we present a general scheme for solving a large...

Competitive Routing of Virtual Circuits with Unknown Duration (1995)

Baruch Awerbuch, Yossi Azar, Serge Plotkin, Orli Waarts

In this paper we present a strategy to route unknown duration virtual circuits in a highspeed communication network. Previous work on virtual circuit routing concentrated on the case where the call...

Local Management of a Global Resource in a Communication Network (1995)

Yehuda Afek, Baruch Awerbuch, Serge Plotkin, Michael Saks

This paper introduces a new distributed data object called Resource Controller which provides an abstraction for managing the consumption of a global resource in a distributed system. Examples of...

Fast Approximation Algorithm for Minimum Cost Multicommodity Flow (1995)

RANDOM SAMPLING IN GRAPH OPTIMIZATION PROBLEMS (1995)

Minimum-cost multicommodity flow problem is one of the classical optimization problems that arises in a variety of contexts. Applications range from finding optimal ways to route information through...

Serge Plotkin, Andrew Goldberg

ii

Competitive Routing of Virtual Circuits with Unknown Duration (1994)

Baruch Awerbuch, Yossi Azar, Serge Plotkin, Orli Waarts

In this paper we present a strategy to route unknown duration virtual circuits in a highspeed communication network. Previous work on virtual circuit routing concentrated on the case where the call...

Fast approximation algorithms for multicommodity flow problems (1994)

Tom Leighton, Fillia Makedon, Serge Plotkin, Clifford Stein, Eva Tardos, Spyros Tragoudas

z

Shallow excluded minors and improved graph decompositions (1994)

Serge Plotkin, Satish Rao, Warren D. Smith

In this paper we introduce the notion of the limited-depth minor exclusion and show that graphs that exclude small limited-depth minors have relatively small separators. In particular, we prove that...

Competitive Routing of Virtual Circuits with Unknown Duration (1994)

Baruch Awerbuch, Yossi Azar, Serge Plotkin, Orli Waarts

In this paper we present a strategy to route unknown duration virtual circuits in a highspeed communication network. Previous work on virtual circuit routing concentrated on the case where the call...

Routing and Admission Control of Virtual Circuits in General Topology Networks (1994)

Rainer Gawlick, Anil Kamath, Serge Plotkin, K. G. Ramakrishnan

Emerging high speed Broadband Integrated Services Digital Networks (B-ISDN) are expected to carry traffic for services like video-on-demand and video teleconferencing which will require resource...

Shallow Excluded Minors and Improved Graph Decompositions (1994)

Serge Plotkin, Satish Rao, Warren D. Smith

In this paper we introduce the notion of the limiteddepth minor exclusion and show that graphs that exclude small limited-depth minors have relatively small separators. In particular, we prove that...

Competitive Routing of Virtual Circuits with Unknown Duration (1994)

Baruch Awerbuch, Yossi Azar, Serge Plotkin, Orli Waarts

In this paper we present a strategy to route unknown duration virtual circuits in a highspeed communication network. Previous work on virtual circuit routing concentrated on the case where the call...

On-line Load Balancing of Temporary Tasks (1993)

Yossi Azar, Bala Kalyanasundaram, Serge Plotkin, Kirk R. Pruhs, Orli Waarts

This paper considers the non-preemptive on-line load balancing problem where tasks have limited duration in time. Upon arrival, each task has to be immediately assigned to one of the machines,...

On-line Load Balancing of Temporary Tasks (1993)

Yossi Azar, Bala Kalyanasundaram, Serge Plotkin, Kirk R. Pruhs, Orli Waarts

This paper considers the non-preemptive on-line load balancing problem where tasks have limited duration in time. Upon arrival, each task has to be immediately assigned to one of the machines,...

Throughput-Competitive On-Line Routing (1993)

Improved Bounds on the Max-Flow Min-Cut Ratio for Multicommodity Flows (1993)

We develop a framework that allows us to address the issues of admission control and routing in high-speed networks under the restriction that once a call is admitted and routed, it has to proceed to...

Serge Plotkin, Éva Tardos, Eva Tardos

In this paper we consider the worst case ratio between the capacity of min-cuts and the value of max-flow for multicommodity flow problems. We improve the best known bounds for the mincut max-flow...

Fast Approximation Algorithms for Multicommodity Flow Problems (1993)

Tom Leighton, Fillia Makedon, Serge Plotkin, Clifford Stein, Eva Tardos, Spyros Tragoudas

All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming. The best of these algorithms [15] uses a fast matrix multiplication...

Throughput-Competitive On-Line Routing (1993)

On-line Load Balancing of Temporary Tasks (1993)

We develop a framework that allows us to address the issues of admission control and routing in high-speed networks under the restriction that once a call is admitted and routed, it has to proceed to...

Yossi Azar, Bala Kalyanasundaram, Serge Plotkin, Kirk R. Pruhs, Orli Waarts

This paper considers the non-preemptive on-line load balancing problem where tasks have limited duration in time. Upon arrival, each task has to be immediately assigned to one of the machines,...

Throughput-Competitive On-Line Routing (1993)

Time-Lapse snapshots (1992)

We develop a framework that allows us to address the issues of admission control and routing in high-speed networks under the restriction that once a call is admitted and routed, it has to proceed to...

Cynthia Dwork, Maurice Herlihy, Serge Plotkin, Orli Waarts

A snapshot scan algorithm takes an "instantaneous " picture of a region of shared memory that may be updated by concurrent processes. Many complex shared memory algorithms can be...

Topics in Analysis of Algorithms (1992)

Andrew Goldberg, Serge Plotkin

Contents 1 Preliminaries 4 1.1 The Fundamental Theorem of Linear Inequalities : : : : : : : : : : : : : : : : : : 4 1.1.1 Definitions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :...

Fast Approximation Algorithms for Multicommodity Flow Problems (1991)

Tom Leighton, Fillia Makedon, Serge Plotkin, Clifford Stein, Eva Tardos, Spyros Tragoudas

All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming. The best of these algorithms [15] uses a fast matrix multiplication...

Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem With Applications to Routing and Finding Sparse Cuts (1990)

Philip Klein Computer, Philip Klein, Serge Plotkin, Clifford Stein, Cambridge Ma, Eva Tardos

In this paper, we describe new algorithms for approximately solving the concurrent multicommodity flow problem with uniform capacities. Our algorithms are much faster than previously known...

Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem With Applications to Routing and Finding Sparse Cuts (1990)

Philip Klein, Serge Plotkin, Clifford Stein, Éva Tardos, Cambridge Ma, Eva Tardos

In this paper, we describe new algorithms for approximately solving the concurrent multicommodity flow problem with uniform capacities. Our algorithms are much faster than previously known...

Local Management of a Global Resource in a Communication Network (1987)

Yehuda Afek Baruch, Baruch Awerbuch, Serge Plotkin, Michael Saks

This paper introduces a new distributed data object called Resource Controller which provides an abstraction for managing the consumption of a global resource in a distributed system. Examples of...

Simple and Fast Distributed Multicommodity Flow Algorithm