Serge A. Plotkin

According to our database, Serge A. Plotkin authored at least 50 papers between 1987 and 2008.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2008

Cost-Distance: Two Metric Network Design.

Adam Meyerson, Kamesh Munagala, Serge A. Plotkin

SIAM J. Comput., 2008

2005

Approximate majorization and fair online load balancing.

Ashish Goel, Adam Meyerson, Serge A. Plotkin

ACM Trans. Algorithms, 2005

A non-manipulable trust system based on EigenTrust.

Zoë Abrams, Robert McGrew, Serge A. Plotkin

SIGecom Exch., 2005

An online throughput-competitive algorithm for multicast routing and admission control.

Ashish Goel, Monika Rauch Henzinger, Serge A. Plotkin

J. Algorithms, 2005

2004

A <i>k</i>-Median Algorithm with Running Time Independent of Data Size.

Adam Meyerson, Liadan O'Callaghan, Serge A. Plotkin

Mach. Learn., 2004

Set k-cover algorithms for energy efficient monitoring in wireless sensor networks.

Zoë Abrams, Ashish Goel, Serge A. Plotkin

Proceedings of the Third International Symposium on Information Processing in Sensor Networks, 2004

2003

Scheduling data transfers in a network and the set scheduling problem.

Ashish Goel, Monika Rauch Henzinger, Serge A. Plotkin, Éva Tardos

J. Algorithms, 2003

2001

Combining Fairness with Throughput: Online Routing with Multiple Objectives.

Ashish Goel, Adam Meyerson, Serge A. Plotkin

J. Comput. Syst. Sci., 2001

Competitive Routing of Virtual Circuits with Unknown Duration.

Baruch Awerbuch, Yossi Azar, Serge A. Plotkin, Orli Waarts

J. Comput. Syst. Sci., 2001

Web caching using access statistics.

Adam Meyerson, Kamesh Munagala, Serge A. Plotkin

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Distributed admission control, scheduling, and routing with stale information.

Ashish Goel, Adam Meyerson, Serge A. Plotkin

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Designing Networks Incrementally.

Adam Meyerson, Kamesh Munagala, Serge A. Plotkin

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

A sublinear parallel algorithm for stable matching.

Tomás Feder, Nimrod Megiddo, Serge A. Plotkin

Theor. Comput. Sci., 2000

1999

Time-Lapse Snapshots.

Cynthia Dwork, Maurice Herlihy, Serge A. Plotkin, Orli Waarts

SIAM J. Comput., 1999

1998

Routing and Admission Control in General Topology Networks with Poisson Arrivals.

Anil Kamath, Omri Palmon, Serge A. Plotkin

J. Algorithms, 1998

Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control.

Ashish Goel, Monika Rauch Henzinger, Serge A. Plotkin

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flow.

Andrew V. Goldberg, Jeffrey D. Oldham, Serge A. Plotkin, Clifford Stein

Proceedings of the Integer Programming and Combinatorial Optimization, 1998

Approximating a Finite Metric by a Small Number of Tree Metrics.

Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, Serge A. Plotkin

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997

Approximation Algorithms for Steiner and Directed Multicuts.

Philip N. Klein, Serge A. Plotkin, Satish Rao, Éva Tardos

J. Algorithms, 1997

On-Line Load Balancing of Temporary Tasks.

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

J. Algorithms, 1997

On-line routing of virtual circuits with applications to load balancing and machine scheduling.

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

J. ACM, 1997

An Improved Lower Bound for Load Balancing of Tasks with Unknown Duration.

Yuan Ma, Serge A. Plotkin

Inf. Process. Lett., 1997

1996

Local Management of a Global Resource in a Communication Network.

Yehuda Afek, Baruch Awerbuch, Serge A. Plotkin, Michael E. Saks

J. ACM, 1996

1995

Fast Approximation Algorithms for Fractional Packing and Covering Problems.

Serge A. Plotkin, David B. Shmoys, Éva Tardos

Math. Oper. Res., 1995

Competitive Routing of Virtual Circuits in ATM Networks.

Serge A. Plotkin

IEEE J. Sel. Areas Commun., 1995

Fast Approximation Algorithms for Multicommodity Flow Problems.

Frank Thomson Leighton, Fillia Makedon, Serge A. Plotkin, Clifford Stein, Éva Tardos, Spyros Tragoudas

J. Comput. Syst. Sci., 1995

Improved Bounds on the Max-Flow Min-Cut Ratio for Multicommodity Flows.

Serge A. Plotkin, Éva Tardos

Comb., 1995

Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows.

David R. Karger, Serge A. Plotkin

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Fast Approximation Algorithm for Minimum Cost Multicommodity Flow.

Anil Kamath, Omri Palmon, Serge A. Plotkin

Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

1994

A Parallel Algorithm for Reconfiguring a Multibutterfly Network with Faulty Switches.

Andrew V. Goldberg, Bruce M. Maggs, Serge A. Plotkin

IEEE Trans. Computers, 1994

Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts.

Philip N. Klein, Serge A. Plotkin, Clifford Stein, Éva Tardos

SIAM J. Comput., 1994

Shallow Excluded Minors and Improved Graph Decompositions.

Serge A. Plotkin, Satish Rao, Warren D. Smith

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Improved Approximation Algorithms for Network Design Problems.

Michel X. Goemans, Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos, David P. Williamson

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993

Polynomial dual network simplex algorithms.

James B. Orlin, Serge A. Plotkin, Éva Tardos

Math. Program., 1993

Sublinear-Time Parallel Algorithms for Matching and Related Problems.

Andrew V. Goldberg, Serge A. Plotkin, Pravin M. Vaidya

J. Algorithms, 1993

Approximating Matchings in Parallel.

Ted Fischer, Andrew V. Goldberg, David J. Haglin, Serge A. Plotkin

Inf. Process. Lett., 1993

Online Load Balancing of Temporary Tasks.

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

Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

Excluded minors, network decomposition, and multicommodity flow.

Philip N. Klein, Serge A. Plotkin, Satish Rao

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

On-line load balancing with applications to machine scheduling and virtual circuit routing.

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

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Throughput-Competitive On-Line Routing

Baruch Awerbuch, Yossi Azar, Serge A. Plotkin

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

Using Interior-Point Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems.

Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos

SIAM J. Comput., 1992

Using Separation Algorithms in Fixed Dimension.

Carolyn Haibt Norton, Serge A. Plotkin, Éva Tardos

J. Algorithms, 1992

1991

Combinatorial Algorithms for the Generalized Circulation Problem.

Andrew V. Goldberg, Serge A. Plotkin, Éva Tardos

Math. Oper. Res., 1991

1990

Improved Dual Network Simplex.

Serge A. Plotkin, Éva Tardos

Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

1989

Sticky Bits and Universality of Consensus.

Serge A. Plotkin

Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, 1989

Interior-Point Methods in Parallel Computation

Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Network Decomposition and Locality in Distributed Computation

Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, Serge A. Plotkin

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988

Parallel Symmetry-Breaking in Sparse Graphs.

Andrew V. Goldberg, Serge A. Plotkin, Gregory E. Shannon

SIAM J. Discret. Math., 1988

Minimum-Cost Spanning Tree as a Path-Finding Problem.

Bruce M. Maggs, Serge A. Plotkin

Inf. Process. Lett., 1988

1987

Parallel ((Greek D)D+1)-Coloring of Constant-Degree Graphs.

Andrew V. Goldberg, Serge A. Plotkin

Inf. Process. Lett., 1987