Serge Plotkin
Associate Professor of Computer Science, Emeritus
Web page: http://web.stanford.edu/~plotkin
Bio
Plotkin's focus is on optimization problems that are encountered in the context of design, management, and maintenance of broadband communication networks. Currently his main effort in this area is concentrated on development of algorithms for network topology design, routing, capacity sizing, server placement, and fair resource allocation. His goal is to develop both offline strategies that can be used during network design stage, as well as online strategies that can be applied to optimize existing network infrastructure.
Professional Education

PhD, MIT (1988)
201920 Courses

Independent Studies (15)
 Advanced Reading and Research
CS 499 (Aut, Win, Spr, Sum)  Advanced Reading and Research
CS 499P (Aut, Win, Spr, Sum)  Computer Laboratory
CS 393 (Aut, Win, Spr, Sum)  Curricular Practical Training
CS 390A (Aut, Win, Spr, Sum)  Curricular Practical Training
CS 390B (Aut, Win, Spr, Sum)  Curricular Practical Training
CS 390C (Aut, Win, Spr, Sum)  Independent Database Project
CS 395 (Aut, Win, Spr, Sum)  Independent Project
CS 399 (Aut, Win, Spr, Sum)  Independent Project
CS 399P (Aut, Win, Spr, Sum)  Independent Work
CS 199 (Aut, Win, Spr, Sum)  Independent Work
CS 199P (Aut, Win, Spr, Sum)  Parttime Curricular Practical Training
CS 390D (Aut, Win, Spr)  Programming Service Project
CS 192 (Aut, Win, Spr, Sum)  Senior Project
CS 191 (Aut, Win, Spr, Sum)  Writing Intensive Senior Project (WIM)
CS 191W (Aut, Win, Spr)
 Advanced Reading and Research
Stanford Advisees

Master's Program Advisor
Christopher Salvarani
All Publications

COSTDISTANCE: TWO METRIC NETWORK DESIGN
SIAM JOURNAL ON COMPUTING
2008; 38 (4): 16481659
View details for DOI 10.1137/050629665
View details for Web of Science ID 000261891600019

An online throughputcompetitive algorithm for multicast routing and admission control
JOURNAL OF ALGORITHMS
2005; 55 (1): 120
View details for DOI 10.1016/j.jalgor.2004.11.001
View details for Web of Science ID 000228441600001

A kmedian algorithm with running time independent of data size
MACHINE LEARNING
2004; 56 (13): 6187
View details for Web of Science ID 000222264700004

Set Kcover algorithms for energy efficient monitoring in wireless sensor networks
3rd International Symposium on Information Processing in Sensor Networks
ASSOC COMPUTING MACHINERY. 2004: 424–432
View details for Web of Science ID 000222055900048
 Keeping peers honest in eigentrust. 2004
 A fast, smallspace clustering algorithm, independent of data size. Machine Learning Journal, Special Issue on Data Clustering 2004; 56: 61–87

Scheduling data transfers in a network and the set scheduling problem
JOURNAL OF ALGORITHMS
2003; 48 (2): 314332
View details for DOI 10.1016/S01966774(03)000543
View details for Web of Science ID 000184853000003

Combining fairness with throughput: Online routing with multiple objectives
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
2001; 63 (1): 6279
View details for DOI 10.1006/jcss.2001.1755
View details for Web of Science ID 000171061600005

Competitive routing of virtual circuits with unknown duration
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
2001; 62 (3): 385397
View details for Web of Science ID 000168461300001

Distributed admission control, scheduling, and routing with stale information
12th Annual ACMSIAM Symposium on Discrete Algorithms
SIAM. 2001: 611–619
View details for Web of Science ID 000177257800085
 On the integrality gap of capacitated facility location problem. GSIA Working Paper 2001
 Facility location with interference. GSIA Working Paper 2001E23 2001

Designing networks incrementally
42nd Annual Symposium on Foundations of Computer Science (FOCS 2001)
IEEE COMPUTER SOC. 2001: 406–415
View details for Web of Science ID 000172225900039

Web caching using access statistics
12th Annual ACMSIAM Symposium on Discrete Algorithms
SIAM. 2001: 354–363
View details for Web of Science ID 000177257800053
 Web caching using access statistics. 2001

Approximate majorization and fair online load balancing
12th Annual ACMSIAM Symposium on Discrete Algorithms
SIAM. 2001: 384–390
View details for Web of Science ID 000177257800056

A sublinear parallel algorithm for stable matching
THEORETICAL COMPUTER SCIENCE
2000; 233 (12): 297308
View details for Web of Science ID 000084793400019

CostDistance: Two metric network design
41st Annual Symposium on Foundations of Computer Science (FOCS 00)
IEEE COMPUTER SOC. 2000: 624–630
View details for Web of Science ID 000165964000061
 Combining fairness with throughput: Online routing with multiple objectives. 2000
 Costdistance: Two metric network design. Technical Report STANCSTN0092, Stanford 2000

Timelapse snapshots
SIAM JOURNAL ON COMPUTING
1999; 28 (5): 18481874
View details for Web of Science ID 000080710200014
 Timelapse snapshots. SIAM J. on Computing 1999; 5 (28)
 Scheduling data transfers in a network and the set scheduling problem. 1999

Routing and admission control in general topology networks with Poisson arrivals
7th Annual ACM/SIAM Symposium on Discrete Algorithms (SODA 96)
ACADEMIC PRESS INC ELSEVIER SCIENCE. 1998: 236–58
View details for Web of Science ID 000073541000004

Approximating a finite metric by a small number of tree metrics
39th Annual Symposium on Foundations of Computer Science
IEEE COMPUTER SOC. 1998: 379–388
View details for Web of Science ID 000077523900042
 Online throughputcompetitive algorithm for multicast routing and admission control. 1998

An implementation of a combinatorial approximation algorithm for minimumcost multicommodity flow
6th International Integer Programming and Combinatorial Optimization (IPCO VI)
SPRINGERVERLAG BERLIN. 1998: 338–352
View details for Web of Science ID 000077582600026
 An implementation of a combinatorial approximation algorithm for minimumcost multicommodity flow. 1998

An improved lower bound for load balancing of tasks with unknown duration
INFORMATION PROCESSING LETTERS
1997; 62 (6): 301303
View details for Web of Science ID A1997XM07100004

Online routing of virtual circuits with applications to load balancing and machine scheduling
JOURNAL OF THE ACM
1997; 44 (3): 486504
View details for Web of Science ID A1997XR56400005

Approximation algorithms for Steiner and directed multicuts
JOURNAL OF ALGORITHMS
1997; 22 (2): 241269
View details for Web of Science ID A1997WH54200003

Online load balancing of temporary tasks
JOURNAL OF ALGORITHMS
1997; 22 (1): 93110
View details for Web of Science ID A1997WH53900004
 Online machine scheduling with applications to load balancing and virtual circuit routing. J. Assoc. Comput. Mach. 1997; 3 (44): 486–504
 Online throughputcompetitive algorithm for multicast routing and admission control. Technical Report 971592, Stanford University 1997
 Improved lower bounds for load balancing of tasks with unknown duration. Information Processing Letters 1997; 62: 301–303

Local management of a global resource in a communication network
JOURNAL OF THE ACM
1996; 43 (1): 119
View details for Web of Science ID A1996UW78500001
 Routing and admission control in general topology networks with poisson arrivals. Technical Report STANCSTR961575, Stanford University 1996
 Improved lower bounds for load balancing of tasks with unknown duration. Technical Report STANCSTN9637, Stanford University 1996

Routing and admission control in general topology networks with Poisson arrivals
7th Annual ACM/SIAM Symposium on Discrete Algorithms
SIAM. 1996: 269–278
View details for Web of Science ID A1996BE98Q00031

COMPETITIVE ROUTING OF VIRTUAL CIRCUITS IN ATM NETWORKS
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS
1995; 13 (6): 11281136
View details for Web of Science ID A1995RL82200019

FAST APPROXIMATION ALGORITHMS FOR FRACTIONAL PACKING AND COVERING PROBLEMS
MATHEMATICS OF OPERATIONS RESEARCH
1995; 20 (2): 257301
View details for Web of Science ID A1995RR11200001

FAST APPROXIMATION ALGORITHMS FOR MULTICOMMODITY FLOW PROBLEMS
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
1995; 50 (2): 228243
View details for Web of Science ID A1995QU27800005
 Routing and admission control in general topology networks. Technical Report STANCSTR951548, Stanford University 1995
 Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows. 1995
 Fast approximation algorithm for mincost multicommodity flow. Technical Report STANCSTN9519, Stanford University 1995

FAST APPROXIMATION ALGORITHM FOR MINIMUM COST MULTICOMMODITY FLOW
6th Annual ACM/SIAM Symposium on Discrete Algorithms
SIAM. 1995: 493–501
View details for Web of Science ID A1995BC77V00054

IMPROVED BOUNDS ON THE MAXFLOW MINCUT RATIO FOR MULTICOMMODITY FLOWS
COMBINATORICA
1995; 15 (3): 425434
View details for Web of Science ID A1995RW18000010

FASTER APPROXIMATION ALGORITHMS FOR THE UNIT CAPACITY CONCURRENT FLOW PROBLEM WITH APPLICATIONS TO ROUTING AND FINDING SPARSE CUTS
SIAM JOURNAL ON COMPUTING
1994; 23 (3): 466487
View details for Web of Science ID A1994NN24400002

A PARALLEL ALGORITHM FOR RECONFIGURING A MULTIBUTTERFLY NETWORK WITH FAULTY SWITCHES
IEEE TRANSACTIONS ON COMPUTERS
1994; 43 (3): 321326
View details for Web of Science ID A1994ND51700006

SHALLOW EXCLUDED MINORS AND IMPROVED GRAPH DECOMPOSITIONS
5th Annual ACMSIAM Symposium on Discrete Algorithms
SIAM. 1994: 462–470
View details for Web of Science ID A1994BA19U00051
 A sublinear parallel algorithm for stable matching. 1994
 Improved approximation algorithms for network design problems. 1994
 Distributed routing and admission control of virtual circuits in general topology networks. Technical Report BL01121294081919TM, AT&T Bell Laboratories 1994
 Competitive routing of virtual circuits with unknown duration. 1994

POLYNOMIAL DUAL NETWORK SIMPLEX ALGORITHMS
MATHEMATICAL PROGRAMMING
1993; 60 (3): 255276
View details for Web of Science ID A1993LV54400001

APPROXIMATING MATCHINGS IN PARALLEL
INFORMATION PROCESSING LETTERS
1993; 46 (3): 115118
View details for Web of Science ID A1993LK18100002

SUBLINEARTIME PARALLEL ALGORITHMS FOR MATCHING AND RELATED PROBLEMS
JOURNAL OF ALGORITHMS
1993; 14 (2): 180213
View details for Web of Science ID A1993KM60500002
 A sublinear parallel algorithm for stable matching. Technical Report RJ 9327 (82440), IBM Almaden Research Center 1993
 Throughput competitive online routing. 1993
 Online load balancing of temporary tasks. 1993
 Planar graphs, multicommodity flow, and network decomposition. 1993
 Online machine scheduling with applications to load balancing and virtual circuit routing. 1993
 Improved bounds on the maxflow mincut ratio for multicommodity flows. 1993
 Bounds on the maxflow mincut ratio for directed multicommodity flows. Technical Report CS9330, Brown University 1993

USING SEPARATION ALGORITHMS IN FIXED DIMENSION
1ST ANNUAL SYMP ON DISCRETE ALGORITHMS ( SODA )
ACADEMIC PRESS INC JNLCOMP SUBSCRIPTIONS. 1992: 79–98
View details for Web of Science ID A1992HB82700005

USING INTERIORPOINT METHODS FOR FAST PARALLEL ALGORITHMS FOR BIPARTITE MATCHING AND RELATED PROBLEMS
SIAM JOURNAL ON COMPUTING
1992; 21 (1): 140150
View details for Web of Science ID A1992HE39700011

TIMELAPSE SNAPSHOTS
LECTURE NOTES IN COMPUTER SCIENCE
1992; 601: 154170
View details for Web of Science ID A1992LF68200016
 Timelapse snapshots. 1992
 Timelapse snapshots. Technical Report STANCS 921423, Department of Computer Science, Stanford University 1992
 A parallel algorithm for reconfiguring a multibutterfly network with faulty switches. Technical Report STANCS921427, Department of Computer Science, Stanford University 1992
 Lecture Notes: Topics in Combinatorial Optimization. Technical Report STANCS921447, Department of Computer Science, Stanford University 1992
 Fast approximation algorithms for fractional packing and covering problems. Technical Report STANCS921419, Department of Computer Science, Stanford University 1992

COMPARISON OF ACELLULAR AND WHOLECELL PERTUSSISCOMPONENT DIPHTHERIATETANUSPERTUSSIS VACCINES IN INFANTS
JOURNAL OF PEDIATRICS
1991; 119 (2): 194204
View details for Web of Science ID A1991FZ69200006

COMBINATORIAL ALGORITHMS FOR THE GENERALIZED CIRCULATION PROBLEM
MATHEMATICS OF OPERATIONS RESEARCH
1991; 16 (2): 351381
View details for Web of Science ID A1991FM19800008

A controlled trial comparing vidarabine with acyclovir in neonatal herpes simplex virus infection. Infectious Diseases Collaborative Antiviral Study Group.
New England journal of medicine
1991; 324 (7): 444449
Abstract
Despite the use of vidarabine, herpes simplex virus (HSV) infection in neonates continues to be a disease of high morbidity and mortality. We undertook a controlled trial comparing vidarabine with acyclovir for the treatment of neonatal HSV infection.Babies less than one month of age with virologically confirmed HSV infection were randomly and blindly assigned to receive either intravenous vidarabine (30 mg per kilogram of body weight per day; n = 95) or acyclovir (30 mg per kilogram per day; n = 107) for 10 days. Actuarial rates of mortality and morbidity among the survivors after one year were compared overall and according to the extent of the disease at entry into the study (infection confined to the skin, eyes, or mouth; encephalitis; or disseminated disease).After adjustment for differences between groups in the extent of disease, there was no difference between vidarabine and acyclovir in either morbidity (P = 0.83) or mortality (P = 0.27). None of the 85 babies with disease confined to the skin, eyes, or mouth died. Of the 31 babies in this group who were treated with vidarabine and followed for a year, 88 percent (22 of 25) were judged to be developing normally after one year, as compared with 98 percent (45 of 46) of the 54 treated with acyclovir (95 percent confidence interval for the difference, 4 to 24). For the 71 babies with encephalitis, mortality was 14 percent with vidarabine (5 of 36) and with acyclovir (5 of 35); of the survivors, 43 percent (13 of 30) and 29 percent (8 of 28), respectively, were developing normally after one year (95 percent confidence interval for the difference, 11 to 39). For the 46 babies with disseminated disease, mortality was 50 percent (14 of 28) with vidarabine and 61 percent (11 of 18) with acyclovir (95 percent confidence interval for the difference, 20 to 40); of the survivors, 58 percent (7 of 12) and 60 percent (3 of 5), respectively, were judged to be developing normally after one year (95 percent confidence interval for the difference, 40 to 50). Both medications were without serious toxic effects.In this multicenter, randomized, blinded study there were no differences in outcome between vidarabine and acyclovir in the treatment of neonatal HSV infection. The study lacked statistical power to determine whether there were sizable differences within the subgroups of those with localized HSV, encephalitis, or disseminated disease.
View details for PubMedID 1988829

Predictors of morbidity and mortality in neonates with herpes simplex virus infections. The National Institute of Allergy and Infectious Diseases Collaborative Antiviral Study Group.
New England journal of medicine
1991; 324 (7): 450454
Abstract
In a controlled trial comparing acyclovir with vidarabine in the treatment of neonatal herpes simplex virus (HSV) infection, we found no significant difference between the treatments in adjusted mortality and morbidity. Hence, we sought to define for the entire cohort (n = 202) the clinical characteristics that best predicted the eventual outcome in these neonates.Data were gathered prospectively at 27 centers between 1981 and 1988 in infants less than one month of age who had virologically confirmed HSV infection. We examined the outcomes by multivariate analyses of 24 variables. Disease was classified in one of three categories based on the extent of the involvement at entry into the trial: infection confined to skin, eyes, or mouth; encephalitis; or disseminated infection.There were no deaths among the 85 infants with localized HSV infection. The mortality rate was significantly higher in the 46 neonates with disseminated infection (57 percent) than in the 71 with encephalitis (15 percent). In addition, the risk of death was increased in neonates who were in or near coma at entry (relative risk, 5.2), had disseminated intravascular coagulopathy (relative risk, 3.8), or were premature (relative risk, 3.7). In babies with disseminated disease, HSV pneumonitis was also associated with greater mortality (relative risk, 3.6). In the survivors, morbidity was most frequent in infants with encephalitis (relative risk, 4.4), disseminated infection (relative risk, 2.1), seizures (relative risk, 3.0), or infection with HSV type 2 (relative risk, 4.9). With HSV infection limited to the skin, eyes, or mouth, the presence of three or more recurrences of vesicles was associated with an increased risk of neurologic impairment as compared with two or fewer recurrences.
View details for PubMedID 1988830
 Approximating matching in parallel. Technical Report STANCS911369, Department of Computer Science, Stanford University 1991
 Fast approximation algorithms for multicommodity flow problem. 1991
 Fast approximation algorithms for fractional packing and covering problems. 1991
 Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. Technical Report 961, School of Operations Research and Industrial Engineering, Cornell University 1991
 Polynomial Dual Network Simplex. Technical Report STANCS911374, Department of Computer Science, Stanford University 1991
 Fast approximation algorithms for multicommodity flow problem. Technical Report STANCS911375, Department of Computer Science, Stanford University 1991
 Improved Dual Network Simplex. 1990
 Using Separation Algorithms in Fixed Dimension. 1990
 Interior Point Methods in Parallel Computation. Technical Report STANCS891259, Stanford University 1989
 Sticky Bits and Universality of Consensus. 1989
 Interior Point Methods in Parallel Computation. 1989
 Network Decomposition and Locality in Distributed Computation. 1989
 Using Separation Algorithms in Fixed Dimension. Technical Report 866, School of Oper. Res. and Ind. Eng., Cornell University 1989
 Sticky Bits and Universality of Consensus. Technical Report STANCS891280, Stanford University 1989
 MinimumCost Spanning Tree as a PathFinding Problem in a Closed Semiring. Information Processing Letters 1988; 6 (26): 291–293
 Theory of parallel and VLSI computation: Lecture notes for 18.435/6.848. 1988
 SublinearTime Parallel Algorithms for Matching and Related Problems. 1988
 Advanced parallel and VLSI computation: Lecture notes for 6.849/18.436. 1988
 Combinatorial Algorithms for the Generalized Circulation Problem. 1988
 SublinearTime Parallel Algorithms for Matching and Related Problems. Technical Report MIT/LCS/TM357, M.I.T. 1988
 Combinatorial Algorithms for the Generalized Circulation Problem. Technical Report MIT/LCS/TM358, M.I.T. 1988
 Parallel Symmetry Breaking in Sparse Graphs. SIAM J. on Discrete Mathematics 1988; 4 (1): 434–446
 Efficient Parallel Algorithms for (Δ+1)Coloring and Maximal Independent Set Problems. Technical Report MIT/LCS/TM320, M.I.T. 1987
 Parallel Symmetry Breaking in Sparse Graphs. 1987
 Local Management of a Global Resource in a Communication Network. 1987
 Parallel (Δ+1) Coloring of ConstantDegree Graphs. Information Processing Letters 1987; 4 (25): 241–245
 Approximating the size of a dynamically growing distributed network. Technical Report MIT/LCS/TM328, M.I.T. 1987
 A TreeStructured Architecture for Semantic Gap Reduction. Computer Architecture News 1983; 11: 34–44
 Modular, ObjectOriented Microcomputer Architecture. Microprocessing and Microprogramming 1983; 12: 153–157
 An Adaptive Approach to Suppress Powerful Impulsive Interference. Signal Processing 1982; 1: 1–9
 Real Ray Tracing in an Unmagnetized Absorptive Ionosphere. Israel Journal of Technology 1980; 18: 319–325