325:, Johnson showed how several basic optimization problems defined on graphs can be solved in polynomial time by reducing them to weighted matching problems. One example is finding minimum T-joins (i.e., edge sets whose only endpoints of odd degree are those in a specified vertex set T). An important special case is the seemingly difficult problem of finding a shortest tour in a graph that traverses every edge at least once, known as the Postman problem. The stark contrast between the polynomial solvability of this problem and the intractability of the
321:—which developed and extended in significant ways the group theoretic approach to integer programming pioneered by Gomory. In particular, Johnson showed how the approach can be extended to the case of mixed integer programs. As an outgrowth of this work, Johnson contributed decisively to the development of what became known as the subadditive approach to integer programming. Still in the seventies, in a seminal paper co-authored with
314:. Their work combines theory with algorithm development, computational testing, and solution of hard real-world problems in the best tradition of Operations Research and the Management Sciences. In their joint work with Crowder and in subsequent work with others, they showed how to formulate and solve efficiently very large-scale practical 0-1 programs with important applications in industry and transportation.
1039:
329:
in which the tour is supposed to traverse vertices rather than edges, helped focus attention on the phenomenon so typical of combinatorial structures: two seemingly very similar problems turn out in reality to be vastly different.
1044:
488:
354:
137:
229:
Johnson's research interests in logistics include crew scheduling and real-time repair, fleet assignment and routing, distribution planning, network problems, and combinatorial optimization.
481:
474:
222:
From 1990 to 1993, Johnson began teaching and conducting research at
Georgia Tech, where he co-founded and co-directed the Logistics Engineering Center with Professor
1049:
242:
317:
The selection committee cited among
Johnson's contribution three important and influential papers he produced in the early seventies—two of them with
159:
for fundamental contributions to discrete optimization and software design, and its practical applications to distribution and manufacturing systems.
350:
434:
409:
172:
64:
287:
121:
264:
216:
196:
156:
141:
117:
60:
1024:
715:
497:
299:
254:
1019:
962:
675:
834:
326:
311:
78:
188:
113:
50:
866:
826:
270:
906:
1029:
1014:
986:
731:
814:
786:
770:
1054:
1034:
535:
149:
858:
854:
663:
358:
954:
818:
810:
794:
307:
168:
74:
902:
438:
990:
950:
754:
413:
303:
281:
208:
203:, where he founded and managed the Optimization Center from 1982 until 1990, when he was named
970:
938:
782:
707:
659:
587:
583:
918:
914:
874:
635:
563:
539:
388:
277:
223:
200:
187:
In the 1950s, Dr. Ellis
Johnson served as director of the Operations Research Office of the
942:
926:
886:
878:
671:
643:
579:
547:
527:
519:
192:
86:
379:
Flagle, Charles D. (2002). "Some
Origins of Operations Research in the Health Services".
978:
894:
842:
723:
559:
511:
176:
1008:
930:
802:
683:
627:
619:
595:
571:
103:
774:
691:
651:
611:
603:
460:
322:
318:
82:
466:
392:
167:
Johnson received a B.A. in mathematics at
Georgia Tech and earned his Ph.D. in
762:
699:
555:
204:
1040:
Fellows of the
Institute for Operations Research and the Management Sciences
846:
248:
212:
145:
463:
from the
Institute for Operations Research and the Management Sciences
136:
is the
Professor Emeritus and the Coca-Cola Chaired Professor in the
237:
Johnson has received a number of awards, including the following:
470:
456:
H. Milton
Stewart School of Industrial and Systems Engineering
455:
355:
H. Milton
Stewart School of Industrial and Systems Engineering
138:
H. Milton Stewart School of Industrial and Systems Engineering
1045:
Members of the United States National Academy of Engineering
743:
504:
306:in recognition of his fundamental contributions to
109:
99:
70:
56:
46:
28:
21:
243:Society for Industrial and Applied Mathematics
226:. He joined the Georgia Tech faculty in 1994.
482:
155:In 1988, Johnson was elected a member of the
8:
273:for his research in mathematical programming
435:"ISyE Faculty Named Inaugural SIAM Fellows"
351:"Ellis Johnson: Deep Roots at Georgia Tech"
489:
475:
467:
18:
410:"H.Milton Stewart School of ISyE Faculty"
404:
402:
345:
343:
339:
1050:John von Neumann Theory Prize winners
7:
207:. In 1980-1981, Johnson visited the
173:University of California at Berkeley
65:University of California at Berkeley
14:
288:Alexander von Humboldt Foundation
122:Thomas J. Watson Research Center
280:for his paper with Crowder and
265:National Academy of Engineering
217:Humboldt Senior Scientist Award
197:IBM T.J. Watson Research Center
157:National Academy of Engineering
142:Georgia Institute of Technology
118:Georgia Institute of Technology
61:Georgia Institute of Technology
191:. Later, after three years at
1:
498:John von Neumann Theory Prize
461:Biography of Ellis L. Johnson
300:John von Neumann Theory Prize
294:John von Neumann Theory Prize
286:1980 Senior Scientist Award,
255:John von Neumann Theory Prize
357:. 2010-09-07. Archived from
16:American industrial engineer
175:in 1965. He was student of
1071:
393:10.1287/opre.50.1.52.17805
327:traveling salesman problem
312:combinatorial optimization
79:Combinatorial optimization
127:
92:
189:Johns Hopkins University
163:Early life and education
114:Johns Hopkins University
271:George B. Dantzig Prize
987:Christos Papadimitriou
827:Arthur F. Veinott, Jr.
732:R. Tyrrell Rockafellar
215:, as recipient of the
907:Jean Bernard Lasserre
298:Johnson received the
195:, Johnson joined the
1025:Georgia Tech faculty
1020:Georgia Tech alumni
819:Alexander Schrijver
795:J. Michael Harrison
381:Operations Research
308:integer programming
169:operations research
75:Integer programming
991:Mihalis Yannakakis
951:Dimitris Bertsimas
771:Donald L. Iglehart
755:Manfred W. Padberg
304:Manfred W. Padberg
282:Manfred W. Padberg
209:University of Bonn
134:Ellis Lane Johnson
1002:
1001:
995:
983:
975:
971:Alexander Shapiro
967:
959:
947:
939:Dimitri Bertsekas
935:
923:
911:
899:
891:
883:
871:
867:Gérard Cornuéjols
863:
851:
839:
831:
823:
807:
799:
791:
783:Arkadi Nemirovski
779:
767:
759:
736:
728:
720:
712:
708:Peter C. Fishburn
704:
696:
688:
680:
668:
660:Richard E. Barlow
656:
648:
640:
632:
624:
616:
608:
600:
592:
588:Richard J. Duffin
584:William W. Cooper
576:
568:
552:
544:
532:
524:
516:
233:Awards and honors
131:
130:
94:Scientific career
1062:
993:
981:
973:
965:
957:
945:
933:
921:
919:Ruth J. Williams
915:Martin I. Reiman
909:
897:
889:
881:
875:George Nemhauser
869:
861:
849:
837:
829:
821:
811:Martin Grötschel
805:
797:
789:
777:
765:
757:
751:Ellis L. Johnson
734:
726:
718:
710:
702:
694:
686:
678:
666:
654:
646:
638:
636:Herbert A. Simon
630:
622:
614:
606:
598:
590:
574:
566:
564:Albert W. Tucker
550:
542:
540:Carlton E. Lemke
530:
522:
514:
491:
484:
477:
468:
443:
442:
437:. Archived from
431:
425:
424:
422:
421:
412:. Archived from
406:
397:
396:
376:
370:
369:
367:
366:
347:
278:Lanchester Prize
224:George Nemhauser
201:Yorktown Heights
42:
38:
36:
19:
1070:
1069:
1065:
1064:
1063:
1061:
1060:
1059:
1005:
1004:
1003:
998:
943:John Tsitsiklis
927:Donald Goldfarb
887:Michel Balinski
879:Laurence Wolsey
787:Michael J. Todd
739:
672:Alan J. Hoffman
644:Harry Markowitz
580:Abraham Charnes
548:David Blackwell
528:Felix Pollaczek
520:Richard Bellman
500:
495:
452:
447:
446:
433:
432:
428:
419:
417:
408:
407:
400:
378:
377:
373:
364:
362:
349:
348:
341:
336:
296:
260:1990 IBM Fellow
235:
193:Yale University
185:
165:
120:
116:
87:Crew scheduling
85:
81:
77:
63:
57:Alma mater
40:
34:
32:
24:
17:
12:
11:
5:
1068:
1066:
1058:
1057:
1052:
1047:
1042:
1037:
1032:
1027:
1022:
1017:
1007:
1006:
1000:
999:
997:
996:
984:
979:Vijay Vazirani
976:
968:
960:
948:
936:
924:
912:
900:
895:Nimrod Megiddo
892:
884:
872:
864:
859:Peter W. Glynn
855:Søren Asmussen
852:
843:Yurii Nesterov
840:
832:
824:
808:
800:
792:
780:
768:
760:
747:
745:
741:
740:
738:
737:
729:
724:Fred W. Glover
721:
713:
705:
697:
689:
681:
669:
664:Frank Proschan
657:
649:
641:
633:
625:
617:
609:
601:
593:
577:
569:
560:Harold W. Kuhn
553:
545:
533:
525:
517:
512:George Dantzig
508:
506:
502:
501:
496:
494:
493:
486:
479:
471:
465:
464:
458:
451:
450:External links
448:
445:
444:
441:on 2012-02-20.
426:
398:
371:
338:
337:
335:
332:
295:
292:
291:
290:
284:
274:
267:
261:
258:
251:
245:
234:
231:
184:
181:
177:George Dantzig
164:
161:
129:
128:
125:
124:
111:
107:
106:
101:
97:
96:
90:
89:
72:
71:Known for
68:
67:
58:
54:
53:
48:
44:
43:
30:
26:
25:
22:
15:
13:
10:
9:
6:
4:
3:
2:
1067:
1056:
1053:
1051:
1048:
1046:
1043:
1041:
1038:
1036:
1033:
1031:
1030:IBM employees
1028:
1026:
1023:
1021:
1018:
1016:
1015:Living people
1013:
1012:
1010:
992:
988:
985:
980:
977:
972:
969:
964:
961:
956:
955:Jong-Shi Pang
952:
949:
944:
940:
937:
932:
931:Jorge Nocedal
928:
925:
920:
916:
913:
908:
904:
903:Vašek Chvátal
901:
896:
893:
888:
885:
880:
876:
873:
868:
865:
860:
856:
853:
848:
844:
841:
836:
833:
828:
825:
820:
816:
815:László Lovász
812:
809:
804:
803:Robert Aumann
801:
796:
793:
788:
784:
781:
776:
772:
769:
764:
761:
756:
752:
749:
748:
746:
742:
733:
730:
725:
722:
717:
716:Peter Whittle
714:
709:
706:
701:
698:
693:
690:
685:
684:Robert Herman
682:
677:
673:
670:
665:
661:
658:
653:
650:
645:
642:
637:
634:
629:
628:Samuel Karlin
626:
621:
620:Kenneth Arrow
618:
613:
610:
605:
602:
597:
596:Herbert Scarf
594:
589:
585:
581:
578:
573:
572:Lloyd Shapley
570:
565:
561:
557:
554:
549:
546:
541:
537:
534:
529:
526:
521:
518:
513:
510:
509:
507:
503:
499:
492:
487:
485:
480:
478:
473:
472:
469:
462:
459:
457:
454:
453:
449:
440:
436:
430:
427:
416:on 2009-10-14
415:
411:
405:
403:
399:
394:
390:
386:
382:
375:
372:
361:on 2010-09-29
360:
356:
352:
346:
344:
340:
333:
331:
328:
324:
320:
315:
313:
309:
305:
302:jointly with
301:
293:
289:
285:
283:
279:
275:
272:
268:
266:
262:
259:
256:
252:
250:
247:2002 Fellow,
246:
244:
241:2009 Fellow,
240:
239:
238:
232:
230:
227:
225:
220:
218:
214:
210:
206:
202:
198:
194:
190:
182:
180:
178:
174:
170:
162:
160:
158:
153:
151:
147:
143:
139:
135:
126:
123:
119:
115:
112:
108:
105:
104:Mathematician
102:
98:
95:
91:
88:
84:
80:
76:
73:
69:
66:
62:
59:
55:
52:
49:
45:
41:(age 86)
39:July 26, 1938
31:
27:
23:Ellis Johnson
20:
963:Adrian Lewis
775:Cyrus Derman
750:
744:2000–present
692:Lajos Takacs
676:Philip Wolfe
652:Richard Karp
612:Jack Edmonds
604:Ralph Gomory
536:John F. Nash
439:the original
429:
418:. Retrieved
414:the original
384:
380:
374:
363:. Retrieved
359:the original
323:Jack Edmonds
319:Ralph Gomory
316:
297:
236:
228:
221:
186:
166:
154:
133:
132:
110:Institutions
93:
83:Cyclic group
1055:1937 births
1035:IBM Fellows
835:Frank Kelly
47:Citizenship
1009:Categories
763:Ward Whitt
700:Egon Balas
556:David Gale
420:2009-11-20
365:2011-07-09
334:References
205:IBM Fellow
35:1938-07-26
505:1975–1999
387:: 52–60.
257:, INFORMS
171:from the
847:Yinyu Ye
51:American
249:INFORMS
213:Germany
150:Georgia
146:Atlanta
994:(2023)
982:(2022)
974:(2021)
966:(2020)
958:(2019)
946:(2018)
934:(2017)
922:(2016)
910:(2015)
898:(2014)
890:(2013)
882:(2012)
870:(2011)
862:(2010)
850:(2009)
838:(2008)
830:(2007)
822:(2006)
806:(2005)
798:(2004)
790:(2003)
778:(2002)
766:(2001)
758:(2000)
735:(1999)
727:(1998)
719:(1997)
711:(1996)
703:(1995)
695:(1994)
687:(1993)
679:(1992)
667:(1991)
655:(1990)
647:(1989)
639:(1988)
631:(1987)
623:(1986)
615:(1985)
607:(1984)
599:(1983)
591:(1982)
575:(1981)
567:(1980)
551:(1979)
543:(1978)
531:(1977)
523:(1976)
515:(1975)
183:Career
100:Fields
276:1983
269:1985
263:1988
253:2000
310:and
29:Born
389:doi
199:in
144:in
140:at
1011::
989:/
953:/
941:/
929:/
917:/
905:/
877:/
857:/
845:/
817:/
813:/
785:/
773:/
753:/
674:/
662:/
586:/
582:/
562:/
558:/
538:/
401:^
385:50
383:.
353:.
342:^
219:.
211:,
179:.
152:.
148:,
37:)
490:e
483:t
476:v
423:.
395:.
391::
368:.
33:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.