31:
3024:-approximation algorithm which was a significant improvement on the previously known approximation guarantees. The improved algorithm works by rounding an optimal fractional solution of a linear programming relaxation and using the properties of the optimal solutions of the linear program and a generalization of a decomposition technique.
835:
of the linear program deterministically. Algorithm for the generalized assignment problem is based on a similar LP through parametric pruning and then using a new rounding technique on a carefully designed bipartite graph. We now state the LP formulation and briefly describe the rounding technique.
3048:(2013), the Daniel H. Wagner Prize for Excellence in the Practice of Advanced Analytics and Operations Research (2018), and the Khachiyan Prize of the INFORMS Optimization Society (2022), which is awarded annually for life-time achievements in the area of optimization.
1345:
225:
problems. He is known for his pioneering research on providing first constant factor performance guarantee for several scheduling and clustering problems including the k-center and k-median problems and the generalized assignment problem.
3326:
2215:
968:
1146:
1231:
2476:
2970:
called the randomized rounding with a backup, since a backup solution is incorporated to correct for the fact that the ordinary randomized rounding rarely generates a feasible solution to the associated
1052:
1745:
3044:(INFORMS) (2013). He has received the Sonny Yau Excellence in Teaching Award three times from Cornell's College of Engineering, and has been awarded a NSF Presidential Young Investigator Award, the
1568:
550:
2318:
1627:
259:
3321:
1951:
1836:
238:
for data-driven models in a broad cross-section of areas, including COVID epidemiological modeling, congressional districting, transportation, and IoT network design. Shmoys is married to
2913:
2040:
2800:
798:
3022:
2716:
2374:
2096:
1448:
800:. ``In other words, generalized assignment problem is to find a schedule of minimum cost subject to the constraint that the makespan, that the maximum machine load is at most
730:
630:
2850:
3041:
1395:
1238:
2574:
419:
2506:
2245:
1981:
1677:
2655:
1772:
2964:
832:
74:
2940:
2736:
2617:
2594:
2549:
2529:
1856:
1647:
857:
818:
670:
650:
570:
439:
386:
366:
346:
326:
306:
828:
3311:
81:
827:
and Tardos cited here gives a 2 approximation algorithm for the unit cost case. The algorithm is based on a clever design of linear program using
2943:
195:
2815:
3306:
3301:
864:
1059:
2101:
1153:
2853:
288:
The generalized assignment problem can be viewed as the following problem of scheduling unrelated parallel machine with costs. Each of
191:
978:
2379:
1682:
1453:
444:
227:
3331:
3316:
3296:
1573:
203:
57:
1861:
1777:
2250:
732:. By scaling the processing times, we can assume, without loss of generality, that the machine load bounds satisfy
2859:
105:
2978:
For the incapacitated version of the facility location problem, again in a joint work with Chudak he obtained a
255:
3045:
67:
2744:
735:
2981:
2599:
Now considering the ordering of processing times of the jobs on the machines nodes during construction of
1986:
1353:
The obtained LP solution is then rounded to an integral solution as follows. A weighted bipartite graph
2660:
2323:
2045:
1400:
368:). Unrelated implies same job might take different amount of processing time on different machines. Job
235:
1340:{\displaystyle x_{ij}=0\qquad {\text{if}}\qquad p_{ij}\geq T,\qquad i=1,\ldots ,m,\quad j=1,\ldots ,n}
675:
575:
2919:
2825:
270:
234:
problems have found applications in many subsequent works. His current research includes stochastic
3201:
1356:
218:
128:
Approximation
Algorithms for Problems in Sequencing, Scheduling, and Communication Network Design
3291:
3196:
231:
207:
3236:(2003). "Improved Approximation Algorithms for the Uncapacitated Facility Location Problem".
391:
280:
2481:
2220:
1956:
1652:
3286:
2942:
approximation algorithm for the capacitated facility location problem. The joint work with
2628:
1750:
52:
3068:; Tardos, É. (1993). "An approximation algorithm for the generalized assignment problem".
2949:
8:
3184:
2967:
3187:(2004). "Improved approximation algorithms for capacitated facility location problems".
2554:
3214:
3128:
3085:
2925:
2721:
2602:
2579:
2534:
2514:
1841:
1632:
842:
803:
655:
635:
555:
424:
371:
351:
331:
311:
291:
242:, who is the Jacob Gould Schurman Professor of Computer Science at Cornell University.
214:
199:
3132:
824:
3218:
672:
its load, the total processing time required for the jobs assigned to it is at most
3245:
3206:
3163:
3120:
3089:
3077:
138:
101:
3271:
2811:
153:
3249:
3210:
3280:
2966:
approximation for the same problem. Their algorithm is based on a variant of
143:
3327:
Fellows of the
Institute for Operations Research and the Management Sciences
2819:
239:
3168:
3151:
2657:
has a feasible solution then a schedule can be constructed with makespan
859:
and write the following LP. This technique is known as parametric pruning.
3266:
2619:
and using an easy charging argument, the following theorem can be proved:
281:
Generalized
Assignment Problem & Unrelated Parallel Machine Scheduling
168:
3037:
2217:. This ensures that the total weight of the edges incident on the vertex
2596:
and thus it can be rounded to obtain an integral matching of same cost.
1397:
is constructed. One side of the bipartite graph contains the job nodes,
3124:
3081:
3033:
1629:. To construct the edges to machine nodes corresponding to say machine
963:{\displaystyle LP(T)::\sum _{i=1}^{m}\sum _{j=1}^{n}c_{ij}x_{ij}\leq C}
632:, we wish to decide if there exists a schedule with total cost at most
2551:
has edges with total weight at most 1 incident on it. Thus the vector
2531:
has a total edge weight of 1 incident on it, and each machine node in
3109:"Approximation algorithms for scheduling unrelated parallel machines"
2972:
2856:
problem. This was the first paper to break the previously best known
1141:{\displaystyle \sum _{i=1}^{m}p_{ij}x_{ij}\leq T\qquad i=1,\ldots ,m}
266:
3152:"A Constant-Factor Approximation Algorithm for the k-Median Problem"
2210:{\displaystyle x'_{v_{i1}j_{1}}=1-\sum _{i=1}^{j_{1}-1}x'_{v_{i1}j}}
1450:, and the other side contains several copies of each machine node,
1226:{\displaystyle x_{ij}\geq 0\qquad i=1,\ldots ,m,\quad j=1,\ldots ,n}
1649:, first jobs are arranged in decreasing order of processing time
222:
115:
122:
30:
3108:
3322:
Fellows of the
Society for Industrial and Applied Mathematics
3042:
Institute for
Operations Research and the Management Sciences
1047:{\displaystyle \sum _{i=1}^{m}x_{ij}=1\qquad j=1,\ldots ,n}
2805:
285:
The paper is a joint work by David Shmoys and Eva Tardos.
192:
School of
Operations Research and Information Engineering
3145:
2471:{\displaystyle x'_{v_{i2}j_{1}}=x_{ij}-x'_{v_{i1}j_{1}}}
1740:{\displaystyle p_{i1}\geq p_{i2}\geq \ldots \geq p_{in}}
1563:{\displaystyle V=\{v_{i,s}|i=1,2,..,m;s=1,2,..,k_{i}\}}
2511:
In the bipartite graph thus created, each job node in
2984:
2952:
2928:
2862:
2828:
2747:
2724:
2663:
2631:
2605:
2582:
2557:
2537:
2517:
2484:
2382:
2326:
2253:
2223:
2104:
2048:
1989:
1959:
1864:
1844:
1780:
1753:
1685:
1655:
1635:
1576:
1456:
1403:
1359:
1241:
1156:
1062:
981:
867:
845:
806:
738:
678:
658:
638:
578:
558:
545:{\displaystyle c_{i,j},i=1,2,..,m;j=1,2,..,n;n\geq m}
447:
427:
394:
374:
354:
334:
314:
294:
213:
In particular, his work has highlighted the role of
206:
in 1984. His major focus has been in the design and
3102:
1622:{\displaystyle k_{i}=\lceil \sum _{j}x_{ij}\rceil }
3016:
2958:
2934:
2907:
2844:
2794:
2730:
2710:
2649:
2611:
2588:
2568:
2543:
2523:
2500:
2470:
2368:
2312:
2239:
2209:
2090:
2034:
1975:
1945:
1850:
1830:
1766:
1739:
1671:
1641:
1621:
1562:
1442:
1389:
1339:
1225:
1140:
1046:
962:
851:
812:
792:
724:
664:
644:
624:
564:
544:
433:
413:
380:
360:
340:
320:
300:
277:These contributions are described briefly below:
3278:
3182:
2922:problem. His recent results include obtaining a
254:Constant factor approximation algorithm for the
2946:, has resulted in improving the previous known
1946:{\displaystyle (w_{j},v_{i1},j=1,2,..,j_{1}-1)}
1831:{\displaystyle \sum _{j=1}^{j_{1}}x_{ij}\geq 1}
2313:{\displaystyle x'_{v_{i1}j_{1}}<x_{ij_{1}}}
3231:
3064:
2908:{\displaystyle O(\log {k}\ \log {\log {k}})}
1616:
1590:
1557:
1463:
1437:
1410:
265:Constant factor approximation algorithm for
2918:Shmoys has also worked extensively on the
2576:is an instance of a fractional matching on
3096:
29:
3200:
3167:
3058:
328:) have to be processed by exactly one of
3312:American theoretical computer scientists
3156:Journal of Computer and System Sciences
2806:K-medians and Facility Location Problem
839:We guess the optimum value of makespan
3279:
3027:
2795:{\displaystyle max_{i,j}p_{i,j}\leq T}
793:{\displaystyle T_{1}=T_{2}=..=T_{m}=T}
3139:
421:time units when processed by machine
348:unrelated parallel machines (denoted
260:Unrelated Parallel Machine Scheduling
228:Polynomial-time approximation schemes
3307:21st-century American mathematicians
3302:20th-century American mathematicians
3146:Charikar, M.; Guha, S.; Tardos, É.;
3017:{\displaystyle (1+2/e)\approx 1.736}
245:
210:for discrete optimization problems.
2478:. Continue with assigning edges to
2035:{\displaystyle x'_{v_{i1}j}=x_{ij}}
13:
3225:
3176:
2711:{\displaystyle T+max_{i,j}p_{i,j}}
2369:{\displaystyle (w_{j_{1}},v_{i2})}
2091:{\displaystyle (w_{j_{1}},v_{i1})}
1443:{\displaystyle W=\{w_{j}|j\in J\}}
204:University of California, Berkeley
190:(born 1959) is a Professor in the
58:University of California, Berkeley
14:
3343:
3260:
2802:, a 2 approximation is obtained.
250:Two of his key contributions are
202:. He obtained his Ph.D. from the
2822:and David Shmoys. They obtain a
725:{\displaystyle T_{i},i=1,2,..,m}
625:{\displaystyle T_{i},i=1,2,..,m}
2845:{\displaystyle 6{\frac {2}{3}}}
1315:
1290:
1267:
1261:
1201:
1176:
1116:
1022:
106:Computational complexity theory
3005:
2985:
2902:
2866:
2644:
2638:
2363:
2327:
2085:
2049:
1940:
1865:
1483:
1424:
1384:
1366:
880:
874:
256:Generalized Assignment Problem
196:Department of Computer Science
1:
3051:
3046:Frederick W. Lanchester Prize
2810:The paper is a joint work by
1747:. Now find the minimum index
1390:{\displaystyle G=(W\cup V,E)}
68:Frederick W. Lanchester Prize
2852:approximation to the metric
7:
1679:. For simplicity, suppose,
652:such that for each machine
44:1959 (age 64–65)
10:
3348:
3332:21st-century American Jews
3317:Jewish American scientists
3297:Cornell University faculty
308:independent jobs (denoted
3250:10.1137/S0097539703405754
3238:SIAM Journal on Computing
3211:10.1007/s10107-004-0524-9
1983:and set their weights to
271:Facility location problem
163:
159:
149:
137:
121:
111:
97:
90:
63:
48:
40:
28:
21:
3267:David Shmoys's home page
3189:Mathematical Programming
3113:Mathematical Programming
3070:Mathematical Programming
823:The work of Shmoys with
219:approximation algorithms
414:{\displaystyle p_{i,j}}
3272:Éva Tardos's home page
3169:10.1006/jcss.2002.1882
3040:, and a Fellow of the
3018:
2960:
2936:
2909:
2846:
2796:
2732:
2712:
2651:
2613:
2590:
2570:
2545:
2525:
2502:
2501:{\displaystyle v_{i2}}
2472:
2370:
2320:, then create an edge
2314:
2241:
2240:{\displaystyle v_{i1}}
2211:
2180:
2098:and set its weight to
2092:
2036:
1977:
1976:{\displaystyle x_{ij}}
1947:
1852:
1832:
1808:
1768:
1741:
1673:
1672:{\displaystyle p_{ij}}
1643:
1623:
1564:
1444:
1391:
1341:
1227:
1142:
1083:
1048:
1002:
964:
927:
906:
853:
833:extreme point solution
814:
794:
726:
666:
646:
626:
566:
546:
435:
415:
382:
362:
342:
322:
302:
230:that he developed for
208:analysis of algorithms
75:Daniel H. Wagner Prize
16:American mathematician
3107:; Tardos, É. (1990).
3019:
2961:
2937:
2910:
2847:
2797:
2733:
2713:
2652:
2650:{\displaystyle LP(T)}
2614:
2591:
2571:
2546:
2526:
2503:
2473:
2371:
2315:
2242:
2212:
2147:
2093:
2037:
1978:
1948:
1853:
1833:
1781:
1769:
1767:{\displaystyle j_{1}}
1742:
1674:
1644:
1624:
1565:
1445:
1392:
1342:
1228:
1143:
1063:
1049:
982:
965:
907:
886:
854:
831:and then rounding an
815:
795:
727:
667:
647:
627:
567:
547:
436:
416:
383:
363:
343:
323:
303:
2982:
2959:{\displaystyle 5.69}
2950:
2926:
2860:
2826:
2745:
2722:
2661:
2629:
2603:
2580:
2555:
2535:
2515:
2482:
2380:
2324:
2251:
2221:
2102:
2046:
1987:
1957:
1862:
1842:
1778:
1751:
1683:
1653:
1633:
1574:
1454:
1401:
1357:
1239:
1154:
1060:
979:
865:
843:
804:
736:
676:
656:
636:
576:
556:
445:
425:
392:
372:
352:
332:
312:
292:
188:David Bernard Shmoys
3032:David Shmoys is an
3028:Awards & honors
2968:randomized rounding
2467:
2415:
2286:
2206:
2137:
2015:
3232:Chudak, F. N. A.;
3183:Chudak, F. N. A.;
3125:10.1007/BF01585745
3082:10.1007/BF01585178
3014:
2956:
2932:
2905:
2842:
2792:
2728:
2708:
2647:
2609:
2586:
2569:{\displaystyle x'}
2566:
2541:
2521:
2508:in a similar way.
2498:
2468:
2435:
2383:
2366:
2310:
2254:
2237:
2207:
2181:
2105:
2088:
2042:. Create the edge
2032:
1990:
1973:
1943:
1848:
1828:
1764:
1737:
1669:
1639:
1619:
1602:
1560:
1440:
1387:
1337:
1223:
1138:
1044:
960:
849:
829:parametric pruning
810:
790:
722:
662:
642:
622:
562:
542:
441:and incurs a cost
431:
411:
378:
358:
338:
318:
298:
215:linear programming
200:Cornell University
3185:Williamson, D. P.
2935:{\displaystyle 3}
2920:facility location
2882:
2840:
2731:{\displaystyle C}
2612:{\displaystyle G}
2589:{\displaystyle G}
2544:{\displaystyle V}
2524:{\displaystyle W}
2247:is at most 1. If
1851:{\displaystyle E}
1642:{\displaystyle i}
1593:
1265:
852:{\displaystyle T}
813:{\displaystyle T}
665:{\displaystyle i}
645:{\displaystyle C}
565:{\displaystyle C}
434:{\displaystyle i}
381:{\displaystyle j}
361:{\displaystyle M}
341:{\displaystyle m}
321:{\displaystyle J}
301:{\displaystyle n}
246:Key contributions
217:in the design of
185:
184:
150:Doctoral students
92:Scientific career
86:
79:
72:
3339:
3254:
3253:
3229:
3223:
3222:
3204:
3180:
3174:
3173:
3171:
3143:
3137:
3136:
3119:(1–3): 259–271.
3103:Lenstra, J. K.;
3100:
3094:
3093:
3076:(1–3): 461–474.
3062:
3023:
3021:
3020:
3015:
3001:
2965:
2963:
2962:
2957:
2941:
2939:
2938:
2933:
2914:
2912:
2911:
2906:
2901:
2900:
2880:
2879:
2851:
2849:
2848:
2843:
2841:
2833:
2801:
2799:
2798:
2793:
2785:
2784:
2769:
2768:
2737:
2735:
2734:
2729:
2717:
2715:
2714:
2709:
2707:
2706:
2691:
2690:
2656:
2654:
2653:
2648:
2618:
2616:
2615:
2610:
2595:
2593:
2592:
2587:
2575:
2573:
2572:
2567:
2565:
2550:
2548:
2547:
2542:
2530:
2528:
2527:
2522:
2507:
2505:
2504:
2499:
2497:
2496:
2477:
2475:
2474:
2469:
2463:
2462:
2461:
2452:
2451:
2431:
2430:
2411:
2410:
2409:
2400:
2399:
2375:
2373:
2372:
2367:
2362:
2361:
2346:
2345:
2344:
2343:
2319:
2317:
2316:
2311:
2309:
2308:
2307:
2306:
2282:
2281:
2280:
2271:
2270:
2246:
2244:
2243:
2238:
2236:
2235:
2216:
2214:
2213:
2208:
2202:
2198:
2197:
2179:
2172:
2171:
2161:
2133:
2132:
2131:
2122:
2121:
2097:
2095:
2094:
2089:
2084:
2083:
2068:
2067:
2066:
2065:
2041:
2039:
2038:
2033:
2031:
2030:
2011:
2007:
2006:
1982:
1980:
1979:
1974:
1972:
1971:
1952:
1950:
1949:
1944:
1933:
1932:
1893:
1892:
1877:
1876:
1857:
1855:
1854:
1849:
1837:
1835:
1834:
1829:
1821:
1820:
1807:
1806:
1805:
1795:
1773:
1771:
1770:
1765:
1763:
1762:
1746:
1744:
1743:
1738:
1736:
1735:
1714:
1713:
1698:
1697:
1678:
1676:
1675:
1670:
1668:
1667:
1648:
1646:
1645:
1640:
1628:
1626:
1625:
1620:
1615:
1614:
1601:
1586:
1585:
1569:
1567:
1566:
1561:
1556:
1555:
1486:
1481:
1480:
1449:
1447:
1446:
1441:
1427:
1422:
1421:
1396:
1394:
1393:
1388:
1346:
1344:
1343:
1338:
1280:
1279:
1266:
1263:
1254:
1253:
1232:
1230:
1229:
1224:
1169:
1168:
1147:
1145:
1144:
1139:
1109:
1108:
1096:
1095:
1082:
1077:
1053:
1051:
1050:
1045:
1015:
1014:
1001:
996:
969:
967:
966:
961:
953:
952:
940:
939:
926:
921:
905:
900:
858:
856:
855:
850:
819:
817:
816:
811:
799:
797:
796:
791:
783:
782:
761:
760:
748:
747:
731:
729:
728:
723:
688:
687:
671:
669:
668:
663:
651:
649:
648:
643:
631:
629:
628:
623:
588:
587:
571:
569:
568:
563:
551:
549:
548:
543:
463:
462:
440:
438:
437:
432:
420:
418:
417:
412:
410:
409:
387:
385:
384:
379:
367:
365:
364:
359:
347:
345:
344:
339:
327:
325:
324:
319:
307:
305:
304:
299:
181:
178:
176:
174:
172:
170:
139:Doctoral advisor
133:
102:Computer Science
84:
77:
70:
33:
19:
18:
3347:
3346:
3342:
3341:
3340:
3338:
3337:
3336:
3277:
3276:
3263:
3258:
3257:
3230:
3226:
3181:
3177:
3144:
3140:
3101:
3097:
3063:
3059:
3054:
3030:
2997:
2983:
2980:
2979:
2951:
2948:
2947:
2927:
2924:
2923:
2915:approximation.
2896:
2889:
2875:
2861:
2858:
2857:
2832:
2827:
2824:
2823:
2808:
2774:
2770:
2758:
2754:
2746:
2743:
2742:
2723:
2720:
2719:
2696:
2692:
2680:
2676:
2662:
2659:
2658:
2630:
2627:
2626:
2604:
2601:
2600:
2581:
2578:
2577:
2558:
2556:
2553:
2552:
2536:
2533:
2532:
2516:
2513:
2512:
2489:
2485:
2483:
2480:
2479:
2457:
2453:
2444:
2440:
2439:
2423:
2419:
2405:
2401:
2392:
2388:
2387:
2381:
2378:
2377:
2354:
2350:
2339:
2335:
2334:
2330:
2325:
2322:
2321:
2302:
2298:
2294:
2290:
2276:
2272:
2263:
2259:
2258:
2252:
2249:
2248:
2228:
2224:
2222:
2219:
2218:
2190:
2186:
2185:
2167:
2163:
2162:
2151:
2127:
2123:
2114:
2110:
2109:
2103:
2100:
2099:
2076:
2072:
2061:
2057:
2056:
2052:
2047:
2044:
2043:
2023:
2019:
1999:
1995:
1994:
1988:
1985:
1984:
1964:
1960:
1958:
1955:
1954:
1928:
1924:
1885:
1881:
1872:
1868:
1863:
1860:
1859:
1843:
1840:
1839:
1813:
1809:
1801:
1797:
1796:
1785:
1779:
1776:
1775:
1758:
1754:
1752:
1749:
1748:
1728:
1724:
1706:
1702:
1690:
1686:
1684:
1681:
1680:
1660:
1656:
1654:
1651:
1650:
1634:
1631:
1630:
1607:
1603:
1597:
1581:
1577:
1575:
1572:
1571:
1551:
1547:
1482:
1470:
1466:
1455:
1452:
1451:
1423:
1417:
1413:
1402:
1399:
1398:
1358:
1355:
1354:
1272:
1268:
1262:
1246:
1242:
1240:
1237:
1236:
1161:
1157:
1155:
1152:
1151:
1101:
1097:
1088:
1084:
1078:
1067:
1061:
1058:
1057:
1007:
1003:
997:
986:
980:
977:
976:
945:
941:
932:
928:
922:
911:
901:
890:
866:
863:
862:
844:
841:
840:
805:
802:
801:
778:
774:
756:
752:
743:
739:
737:
734:
733:
683:
679:
677:
674:
673:
657:
654:
653:
637:
634:
633:
583:
579:
577:
574:
573:
557:
554:
553:
452:
448:
446:
443:
442:
426:
423:
422:
399:
395:
393:
390:
389:
373:
370:
369:
353:
350:
349:
333:
330:
329:
313:
310:
309:
293:
290:
289:
283:
248:
167:
131:
82:Khachiyan Prize
80:
73:
56:
49:Alma mater
36:
24:
17:
12:
11:
5:
3345:
3335:
3334:
3329:
3324:
3319:
3314:
3309:
3304:
3299:
3294:
3289:
3275:
3274:
3269:
3262:
3261:External links
3259:
3256:
3255:
3224:
3202:10.1.1.53.5219
3175:
3138:
3095:
3056:
3055:
3053:
3050:
3029:
3026:
3013:
3010:
3007:
3004:
3000:
2996:
2993:
2990:
2987:
2955:
2931:
2904:
2899:
2895:
2892:
2888:
2885:
2878:
2874:
2871:
2868:
2865:
2839:
2836:
2831:
2812:Moses Charikar
2807:
2804:
2791:
2788:
2783:
2780:
2777:
2773:
2767:
2764:
2761:
2757:
2753:
2750:
2727:
2705:
2702:
2699:
2695:
2689:
2686:
2683:
2679:
2675:
2672:
2669:
2666:
2646:
2643:
2640:
2637:
2634:
2608:
2585:
2564:
2561:
2540:
2520:
2495:
2492:
2488:
2466:
2460:
2456:
2450:
2447:
2443:
2438:
2434:
2429:
2426:
2422:
2418:
2414:
2408:
2404:
2398:
2395:
2391:
2386:
2365:
2360:
2357:
2353:
2349:
2342:
2338:
2333:
2329:
2305:
2301:
2297:
2293:
2289:
2285:
2279:
2275:
2269:
2266:
2262:
2257:
2234:
2231:
2227:
2205:
2201:
2196:
2193:
2189:
2184:
2178:
2175:
2170:
2166:
2160:
2157:
2154:
2150:
2146:
2143:
2140:
2136:
2130:
2126:
2120:
2117:
2113:
2108:
2087:
2082:
2079:
2075:
2071:
2064:
2060:
2055:
2051:
2029:
2026:
2022:
2018:
2014:
2010:
2005:
2002:
1998:
1993:
1970:
1967:
1963:
1942:
1939:
1936:
1931:
1927:
1923:
1920:
1917:
1914:
1911:
1908:
1905:
1902:
1899:
1896:
1891:
1888:
1884:
1880:
1875:
1871:
1867:
1858:all the edges
1847:
1827:
1824:
1819:
1816:
1812:
1804:
1800:
1794:
1791:
1788:
1784:
1761:
1757:
1734:
1731:
1727:
1723:
1720:
1717:
1712:
1709:
1705:
1701:
1696:
1693:
1689:
1666:
1663:
1659:
1638:
1618:
1613:
1610:
1606:
1600:
1596:
1592:
1589:
1584:
1580:
1559:
1554:
1550:
1546:
1543:
1540:
1537:
1534:
1531:
1528:
1525:
1522:
1519:
1516:
1513:
1510:
1507:
1504:
1501:
1498:
1495:
1492:
1489:
1485:
1479:
1476:
1473:
1469:
1465:
1462:
1459:
1439:
1436:
1433:
1430:
1426:
1420:
1416:
1412:
1409:
1406:
1386:
1383:
1380:
1377:
1374:
1371:
1368:
1365:
1362:
1351:
1350:
1349:
1348:
1336:
1333:
1330:
1327:
1324:
1321:
1318:
1314:
1311:
1308:
1305:
1302:
1299:
1296:
1293:
1289:
1286:
1283:
1278:
1275:
1271:
1260:
1257:
1252:
1249:
1245:
1234:
1222:
1219:
1216:
1213:
1210:
1207:
1204:
1200:
1197:
1194:
1191:
1188:
1185:
1182:
1179:
1175:
1172:
1167:
1164:
1160:
1149:
1137:
1134:
1131:
1128:
1125:
1122:
1119:
1115:
1112:
1107:
1104:
1100:
1094:
1091:
1087:
1081:
1076:
1073:
1070:
1066:
1055:
1043:
1040:
1037:
1034:
1031:
1028:
1025:
1021:
1018:
1013:
1010:
1006:
1000:
995:
992:
989:
985:
959:
956:
951:
948:
944:
938:
935:
931:
925:
920:
917:
914:
910:
904:
899:
896:
893:
889:
885:
882:
879:
876:
873:
870:
848:
809:
789:
786:
781:
777:
773:
770:
767:
764:
759:
755:
751:
746:
742:
721:
718:
715:
712:
709:
706:
703:
700:
697:
694:
691:
686:
682:
661:
641:
621:
618:
615:
612:
609:
606:
603:
600:
597:
594:
591:
586:
582:
561:
541:
538:
535:
532:
529:
526:
523:
520:
517:
514:
511:
508:
505:
502:
499:
496:
493:
490:
487:
484:
481:
478:
475:
472:
469:
466:
461:
458:
455:
451:
430:
408:
405:
402:
398:
377:
357:
337:
317:
297:
282:
279:
275:
274:
263:
247:
244:
183:
182:
165:
161:
160:
157:
156:
154:Clifford Stein
151:
147:
146:
141:
135:
134:
125:
119:
118:
113:
109:
108:
99:
95:
94:
88:
87:
65:
61:
60:
50:
46:
45:
42:
38:
37:
34:
26:
25:
22:
15:
9:
6:
4:
3:
2:
3344:
3333:
3330:
3328:
3325:
3323:
3320:
3318:
3315:
3313:
3310:
3308:
3305:
3303:
3300:
3298:
3295:
3293:
3292:Living people
3290:
3288:
3285:
3284:
3282:
3273:
3270:
3268:
3265:
3264:
3251:
3247:
3243:
3239:
3235:
3234:Shmoys, D. B.
3228:
3220:
3216:
3212:
3208:
3203:
3198:
3194:
3190:
3186:
3179:
3170:
3165:
3161:
3157:
3153:
3149:
3148:Shmoys, D. B.
3142:
3134:
3130:
3126:
3122:
3118:
3114:
3110:
3106:
3105:Shmoys, D. B.
3099:
3091:
3087:
3083:
3079:
3075:
3071:
3067:
3066:Shmoys, D. B.
3061:
3057:
3049:
3047:
3043:
3039:
3035:
3025:
3011:
3008:
3002:
2998:
2994:
2991:
2988:
2976:
2974:
2969:
2953:
2945:
2944:Fabian Chudak
2929:
2921:
2916:
2897:
2893:
2890:
2886:
2883:
2876:
2872:
2869:
2863:
2855:
2837:
2834:
2829:
2821:
2817:
2813:
2803:
2789:
2786:
2781:
2778:
2775:
2771:
2765:
2762:
2759:
2755:
2751:
2748:
2739:
2725:
2703:
2700:
2697:
2693:
2687:
2684:
2681:
2677:
2673:
2670:
2667:
2664:
2641:
2635:
2632:
2624:
2620:
2606:
2597:
2583:
2562:
2559:
2538:
2518:
2509:
2493:
2490:
2486:
2464:
2458:
2454:
2448:
2445:
2441:
2436:
2432:
2427:
2424:
2420:
2416:
2412:
2406:
2402:
2396:
2393:
2389:
2384:
2358:
2355:
2351:
2347:
2340:
2336:
2331:
2303:
2299:
2295:
2291:
2287:
2283:
2277:
2273:
2267:
2264:
2260:
2255:
2232:
2229:
2225:
2203:
2199:
2194:
2191:
2187:
2182:
2176:
2173:
2168:
2164:
2158:
2155:
2152:
2148:
2144:
2141:
2138:
2134:
2128:
2124:
2118:
2115:
2111:
2106:
2080:
2077:
2073:
2069:
2062:
2058:
2053:
2027:
2024:
2020:
2016:
2012:
2008:
2003:
2000:
1996:
1991:
1968:
1965:
1961:
1953:with nonzero
1937:
1934:
1929:
1925:
1921:
1918:
1915:
1912:
1909:
1906:
1903:
1900:
1897:
1894:
1889:
1886:
1882:
1878:
1873:
1869:
1845:
1838:. Include in
1825:
1822:
1817:
1814:
1810:
1802:
1798:
1792:
1789:
1786:
1782:
1774:, such that
1759:
1755:
1732:
1729:
1725:
1721:
1718:
1715:
1710:
1707:
1703:
1699:
1694:
1691:
1687:
1664:
1661:
1657:
1636:
1611:
1608:
1604:
1598:
1594:
1587:
1582:
1578:
1552:
1548:
1544:
1541:
1538:
1535:
1532:
1529:
1526:
1523:
1520:
1517:
1514:
1511:
1508:
1505:
1502:
1499:
1496:
1493:
1490:
1487:
1477:
1474:
1471:
1467:
1460:
1457:
1434:
1431:
1428:
1418:
1414:
1407:
1404:
1381:
1378:
1375:
1372:
1369:
1363:
1360:
1334:
1331:
1328:
1325:
1322:
1319:
1316:
1312:
1309:
1306:
1303:
1300:
1297:
1294:
1291:
1287:
1284:
1281:
1276:
1273:
1269:
1258:
1255:
1250:
1247:
1243:
1235:
1220:
1217:
1214:
1211:
1208:
1205:
1202:
1198:
1195:
1192:
1189:
1186:
1183:
1180:
1177:
1173:
1170:
1165:
1162:
1158:
1150:
1135:
1132:
1129:
1126:
1123:
1120:
1117:
1113:
1110:
1105:
1102:
1098:
1092:
1089:
1085:
1079:
1074:
1071:
1068:
1064:
1056:
1041:
1038:
1035:
1032:
1029:
1026:
1023:
1019:
1016:
1011:
1008:
1004:
998:
993:
990:
987:
983:
975:
974:
973:
972:
971:
957:
954:
949:
946:
942:
936:
933:
929:
923:
918:
915:
912:
908:
902:
897:
894:
891:
887:
883:
877:
871:
868:
860:
846:
837:
834:
830:
826:
821:
807:
787:
784:
779:
775:
771:
768:
765:
762:
757:
753:
749:
744:
740:
719:
716:
713:
710:
707:
704:
701:
698:
695:
692:
689:
684:
680:
659:
639:
619:
616:
613:
610:
607:
604:
601:
598:
595:
592:
589:
584:
580:
559:
539:
536:
533:
530:
527:
524:
521:
518:
515:
512:
509:
506:
503:
500:
497:
494:
491:
488:
485:
482:
479:
476:
473:
470:
467:
464:
459:
456:
453:
449:
428:
406:
403:
400:
396:
375:
355:
335:
315:
295:
286:
278:
272:
268:
264:
261:
257:
253:
252:
251:
243:
241:
237:
233:
229:
224:
220:
216:
211:
209:
205:
201:
197:
193:
189:
180:
166:
162:
158:
155:
152:
148:
145:
144:Eugene Lawler
142:
140:
136:
129:
126:
124:
120:
117:
114:
110:
107:
103:
100:
96:
93:
89:
83:
76:
69:
66:
62:
59:
54:
51:
47:
43:
39:
32:
27:
20:
3241:
3237:
3233:
3227:
3192:
3188:
3178:
3159:
3155:
3147:
3141:
3116:
3112:
3104:
3098:
3073:
3069:
3065:
3060:
3031:
2977:
2973:set covering
2917:
2816:Sudipto Guha
2809:
2740:
2622:
2621:
2598:
2510:
2376:with weight
1352:
861:
838:
822:
287:
284:
276:
249:
236:optimization
212:
187:
186:
127:
112:Institutions
91:
35:David Shmoys
23:David Shmoys
3287:1959 births
3162:: 129–149.
3038:SIAM Fellow
3281:Categories
3195:(2): 207.
3052:References
3034:ACM Fellow
2820:Éva Tardos
240:Éva Tardos
232:scheduling
3197:CiteSeerX
3133:206799898
3009:≈
2975:problem.
2894:
2887:
2873:
2854:k medians
2787:≤
2718:and cost
2433:−
2174:−
2149:∑
2145:−
1935:−
1823:≥
1783:∑
1722:≥
1719:…
1716:≥
1700:≥
1617:⌉
1595:∑
1591:⌈
1432:∈
1373:∪
1329:…
1304:…
1282:≥
1215:…
1190:…
1171:≥
1130:…
1111:≤
1065:∑
1036:…
984:∑
955:≤
909:∑
888:∑
537:≥
267:k-Medians
53:Princeton
3244:: 1–25.
3219:40133143
3150:(2002).
2623:Theorem:
2563:′
2465:′
2413:′
2284:′
2204:′
2135:′
2013:′
1570:, where
552:. Given
194:and the
173:.cornell
3090:9027754
825:Lenstra
223:NP-hard
177:/shmoys
164:Website
116:Cornell
3217:
3199:
3131:
3088:
2881:
2741:Since
388:takes
169:people
132:(1984)
130:
123:Thesis
98:Fields
85:(2022)
78:(2018)
71:(2013)
64:Awards
3215:S2CID
3129:S2CID
3086:S2CID
3012:1.736
171:.orie
3036:, a
2954:5.69
2288:<
572:and
269:and
258:and
221:for
175:.edu
41:Born
3246:doi
3207:doi
3193:102
3164:doi
3121:doi
3078:doi
2891:log
2884:log
2870:log
2625:If
820:".
198:at
3283::
3242:33
3240:.
3213:.
3205:.
3191:.
3160:65
3158:.
3154:.
3127:.
3117:46
3115:.
3111:.
3084:.
3074:62
3072:.
2818:,
2814:,
2738:.
1264:if
970:;
884:::
104:,
55:,
3252:.
3248::
3221:.
3209::
3172:.
3166::
3135:.
3123::
3092:.
3080::
3006:)
3003:e
2999:/
2995:2
2992:+
2989:1
2986:(
2930:3
2903:)
2898:k
2877:k
2867:(
2864:O
2838:3
2835:2
2830:6
2790:T
2782:j
2779:,
2776:i
2772:p
2766:j
2763:,
2760:i
2756:x
2752:a
2749:m
2726:C
2704:j
2701:,
2698:i
2694:p
2688:j
2685:,
2682:i
2678:x
2674:a
2671:m
2668:+
2665:T
2645:)
2642:T
2639:(
2636:P
2633:L
2607:G
2584:G
2560:x
2539:V
2519:W
2494:2
2491:i
2487:v
2459:1
2455:j
2449:1
2446:i
2442:v
2437:x
2428:j
2425:i
2421:x
2417:=
2407:1
2403:j
2397:2
2394:i
2390:v
2385:x
2364:)
2359:2
2356:i
2352:v
2348:,
2341:1
2337:j
2332:w
2328:(
2304:1
2300:j
2296:i
2292:x
2278:1
2274:j
2268:1
2265:i
2261:v
2256:x
2233:1
2230:i
2226:v
2200:j
2195:1
2192:i
2188:v
2183:x
2177:1
2169:1
2165:j
2159:1
2156:=
2153:i
2142:1
2139:=
2129:1
2125:j
2119:1
2116:i
2112:v
2107:x
2086:)
2081:1
2078:i
2074:v
2070:,
2063:1
2059:j
2054:w
2050:(
2028:j
2025:i
2021:x
2017:=
2009:j
2004:1
2001:i
1997:v
1992:x
1969:j
1966:i
1962:x
1941:)
1938:1
1930:1
1926:j
1922:,
1919:.
1916:.
1913:,
1910:2
1907:,
1904:1
1901:=
1898:j
1895:,
1890:1
1887:i
1883:v
1879:,
1874:j
1870:w
1866:(
1846:E
1826:1
1818:j
1815:i
1811:x
1803:1
1799:j
1793:1
1790:=
1787:j
1760:1
1756:j
1733:n
1730:i
1726:p
1711:2
1708:i
1704:p
1695:1
1692:i
1688:p
1665:j
1662:i
1658:p
1637:i
1612:j
1609:i
1605:x
1599:j
1588:=
1583:i
1579:k
1558:}
1553:i
1549:k
1545:,
1542:.
1539:.
1536:,
1533:2
1530:,
1527:1
1524:=
1521:s
1518:;
1515:m
1512:,
1509:.
1506:.
1503:,
1500:2
1497:,
1494:1
1491:=
1488:i
1484:|
1478:s
1475:,
1472:i
1468:v
1464:{
1461:=
1458:V
1438:}
1435:J
1429:j
1425:|
1419:j
1415:w
1411:{
1408:=
1405:W
1385:)
1382:E
1379:,
1376:V
1370:W
1367:(
1364:=
1361:G
1347:;
1335:n
1332:,
1326:,
1323:1
1320:=
1317:j
1313:,
1310:m
1307:,
1301:,
1298:1
1295:=
1292:i
1288:,
1285:T
1277:j
1274:i
1270:p
1259:0
1256:=
1251:j
1248:i
1244:x
1233:;
1221:n
1218:,
1212:,
1209:1
1206:=
1203:j
1199:,
1196:m
1193:,
1187:,
1184:1
1181:=
1178:i
1174:0
1166:j
1163:i
1159:x
1148:;
1136:m
1133:,
1127:,
1124:1
1121:=
1118:i
1114:T
1106:j
1103:i
1099:x
1093:j
1090:i
1086:p
1080:m
1075:1
1072:=
1069:i
1054:;
1042:n
1039:,
1033:,
1030:1
1027:=
1024:j
1020:1
1017:=
1012:j
1009:i
1005:x
999:m
994:1
991:=
988:i
958:C
950:j
947:i
943:x
937:j
934:i
930:c
924:n
919:1
916:=
913:j
903:m
898:1
895:=
892:i
881:)
878:T
875:(
872:P
869:L
847:T
808:T
788:T
785:=
780:m
776:T
772:=
769:.
766:.
763:=
758:2
754:T
750:=
745:1
741:T
720:m
717:,
714:.
711:.
708:,
705:2
702:,
699:1
696:=
693:i
690:,
685:i
681:T
660:i
640:C
620:m
617:,
614:.
611:.
608:,
605:2
602:,
599:1
596:=
593:i
590:,
585:i
581:T
560:C
540:m
534:n
531:;
528:n
525:,
522:.
519:.
516:,
513:2
510:,
507:1
504:=
501:j
498:;
495:m
492:,
489:.
486:.
483:,
480:2
477:,
474:1
471:=
468:i
465:,
460:j
457:,
454:i
450:c
429:i
407:j
404:,
401:i
397:p
376:j
356:M
336:m
316:J
296:n
273:.
262:.
179:/
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
