Hoffman, Alan

Alan Jerome Hoffman ( eng.  Alan Jerome Hoffman ; 30. toukokuuta 1924, New York  - 18. tammikuuta 2021 [2] ) oli amerikkalainen matemaatikko, joka työskenteli IBM T. J. Watson Research Centerissä . Lehden toimittaja ja perustaja Lineaarinen algebra ja sen sovellukset . Hän osallistui graafien kombinatoriseen optimointiin ja ominaisarvoteoriaan. Hoffman rakensi yhdessä Robert Singletonin kanssa Hoffman-Singleton-graafin , joka on ainutlaatuinen Mooren graafi , jonka aste on 7 ja halkaisija 2 [3] .  

Elämäkerta

Alan Hoffman tuli Columbian yliopistoon vuonna 1940 ja sai Pulitzer-stipendin vuonna 1940 16-vuotiaana. Toinen maailmansota keskeytti Hoffmanin opinnot, hänet kutsuttiin palvelukseen helmikuussa 1943 ja hän palveli Yhdysvaltain armeijassa vuosina 1943-1946 sekä Euroopassa että Tyynellämerellä. Ilmatorjuntatykistökoulun peruskoulutuksen aikana hän pohti mahdollisuutta kehittää ympyröiden geometrian aksioomia [2] .

Palattuaan Kolumbiaan syksyllä 1946 hän valmistui vuonna 1950 väitöskirjansa inversiogeometrian perusteista. Sen jälkeen Hoffman vietti vuoden Institute for Advanced Studyssa Princetonissa (viereisessä toimistossa oli Albert Einstein ) [2] .

Varhainen ura

Hoffmanin ensimmäinen työpaikka oli National Bureau of Standards -laitoksen Applied Mathematics Divisionissa . Bureaussa Hoffmanista tuli johtaja uudella tieteenalalla, lineaarisella ohjelmoinnilla . Hoffman oli avainjärjestäjä vaikutusvaltaisessa Second Linear Programming Symposiumissa, joka pidettiin Bureaussa tammikuussa 1955 [2] .

Vuonna 1956 Hoffman jätti toimiston ja muutti Englantiin työskentelemään viestintätutkijana Bureau of Naval Researchin Lontoon haarassa. Vuoden lähestyessä loppuaan ulkomailla Hoffmanille tarjottiin kahta työpaikkaa teollisuusyrityksissä New Yorkissa: toinen pienessä matemaattisessa tutkimusryhmässä syntyvässä IBM Research Laboratoryssa ja toinen General Electric Companyn pääkonttorissa . Hoffman valitsi roolin vakiintuneemmassa organisaatiossa. Johto antoi hänelle mahdollisuuden opiskella matematiikkaa, jos tämä ei häirinnyt hänelle annettujen tehtävien suorittamista, ja Hoffman jatkoi matemaattista tutkimustaan, joka ei liittynyt täysin hänen päätyöhönsä. Vuonna 1961 hän hyväksyi kutsun liittyä IBM:n T. J. Watson Research Centeriin 2] .

Ura IBM:ssä

Uransa aikana IBM:llä Hoffman julkaisi yli 200 tieteellistä artikkelia, joista yli kolmannes oli mukana kirjoittamassa. Hänen matemaattinen alue kattoi monia matematiikan alueita algebrasta operaatiotutkimukseen [2] .

Yhteenveto matemaattisista panoksista (hänen muistiinpanoistaan ​​Selected Papers of Alan Hoffmanissa) [4] .

Hoffmannin geometria-työ, joka alkoi hänen väitöskirjastaan ​​"Inversiogeometrian perusteista", sisälsi todisteita affiinisten tasojen ominaisuuksista sekä äärellisten projektiotasojen relaatiopisteiden, liitossäännönmukaisuuksien ehtoja kartioiden leikkauspisteistä ( johtui suurelta osin hänen yleistyksestään aikaisemmista tuloksistaan ​​todellisten matriisien arvosta). Hän esitti vaihtoehtoisen todisteen, joka perustuu joidenkin abstraktien kuperajoukkojen aksioomeihin tuloksista (Scarf ja muut) epäyhtälöiden lukumäärästä, joka tarvitaan kokonaislukuohjelmointiongelman ratkaisun määrittämiseen. Tätä abstraktia järjestelmää koskeva teoreema näyttää liittyvän läheisesti antimatroideihin (tunnetaan myös kuperaina geometrioina), vaikka yhteyttä ei olekaan täysin tutkittu.

Hoffmanin kombinatoriikkatyö on laajentanut ymmärrystämme useista graafiluokista. G. Hajosin luento intervallikaavioista vuonna 1956 johti Hoffmanin luonnehtimiseen vertailukelpoisuuskaavioista ja myöhemmin, yhteistyössä Paul Gilmourin kanssa, GH-lauseeseen (joka johtuu myös A. Guia-Urysta). Edmondin sovitusalgoritmin innoittamana Hoffman teki yhteistyötä Ray Fulkersonin ja M. McAndrew Hoffmanin kanssa luonnehtiakseen kokonaislukujoukkoja, jotka voisivat sopia tällaisen graafin kunkin kärkiparin potenssit ja rajat. Lisäksi he pohtivat, mitkä kaikkien graafien luokan graafit, joilla on tietty joukko asteita ja reunojen lukumäärän rajat, voidaan muuntaa tietyllä vaihtojoukolla mihin tahansa muuhun luokan joukkoon. Todistukset liittyvät läheisesti tärkeään Hilbert-perustan käsitykseen. Artikkeli itseortogonaalisista latinalaisista neliöistä, joka on kirjoitettu yhdessä IBM:n kirjoittajien Don Coppersmithin ja R. Brightonin kanssa, sai inspiraationsa pyynnöstä ajoittaa sekanelinpeliä välttävä puoliso paikalliseen mailakerhoon. Se eroaa siitä, että se on ainoa paperi, josta Hoffman on keskustellut matemaattisen yhteisön ulkopuolella.

Osittain tilatut sarjat ovat olleet Hoffmanille usein opiskeluaihe. D. E. Schwartzin kanssa vuonna 1977 julkaistussa artikkelissa käytetään lineaarista ohjelmoinnin kaksinaisuutta yleistääkseen Greenin ja Kleitmanin vuonna 1976 tekemän yleistyksen Dilworthin dekompositiolauseesta poseteille, toinen esimerkki kaksinaisuuden yhdistävästä roolista monissa kombinatorisissa tuloksissa.

Hoffman on koko uransa ajan etsinyt yksinkertaisia ​​ja tyylikkäitä vaihtoehtoisia todisteita vakiintuneille lauseille. Nämä vaihtoehtoiset todisteet johtivat usein yleistyksiin ja laajennuksiin. 1990-luvun lopulla hän teki yhteistyötä Caon, Chvatalin ja Vincen kanssa vaihtoehtoisen todistuksen kehittämiseksi käyttämällä alkeismenetelmiä lineaarisen algebran tai Reiserin 0-1 neliömatriisilauseen sijaan.

Hoffmanin työ matriisiepäyhtälöistä ja ominaisarvoista on minkä tahansa matriisiteorian kurssin perusta. Erityisen viehätyksensä, hänen mieltymyksensä yhdistäviin lähestymistapoihin, on hänen vuodelta 1975 julkaistu lineaarisia G-funktioita käsittelevä artikkeli. Vaikka tämän Gershgorin-muunnelman todistus on pidempi ja monimutkaisempi kuin muut, se kattaa kaikki Ostrovski-muunnelmat ja monet lisämuunnelmat erikoistapauksina.

Hoffman oli inspiroiva vanhin, mutta ei osallistunut aktiivisesti IBM:n useiden lineaari- ja kokonaislukuohjelmointituotteiden kehittämiseen. Hän jatkoi kuitenkin lineaarisen ohjelmoinnin ja lineaarisen epätasa-arvon kombinatoristen ja algebrallisten näkökohtien tutkimista, mukaan lukien ihastuttava abstraktio lineaarisen ohjelmoinnin kaksinaisuudesta (1963). Hän jatkoi myös lineaaristen epäyhtälöiden ominaisuuksien käyttöä todistaakseen (tai tyylikkäämmin uudelleen) konveksiteettitulokset.

Yhteistyössä Shmuel Winogradin kanssa, joka on myös IBM-stipendiaatti matematiikan osastolla, kehitettiin tehokas algoritmi kaikkien lyhimpien etäisyyksien löytämiseksi suunnatussa verkossa matriisin näennäismultiointia käyttäen. Sarja artikkeleita hilapolyhedraista (joissakin Don Schwartsilla) esitteli hilapolyhedran käsitteen, mikä johti jälleen uuteen esimerkkiin kombinatorisesta kaksinaisuudesta.

Tehtyään yhteistyötä Ray Fulkersonin ja Rosa Oppenheimin kanssa tasapainotettujen matriisien parissa Hoffman yleisti Ford-Fulkersonin maksimivirtaus-minimileikkaustuloksen muihin tapauksiin (virtaus solmuissa, suuntaamattomat kaaret jne.), mikä osoitti, että kaikki aiemmin tunnetut tapaukset olivat erikoistapauksia. tapauksia. Tässä artikkelissa esiteltiin myös täydellisen kaksoiskokonaisluvun käsite (mutta ei taaskaan nimi), idea useimpien lineaarisen ohjelmoinnin sovellusten takana todistaa äärimmäisiä kombinatorisia lauseita.

Hoffman opiskeli koko uransa aikana kokonaislukuohjelmointiongelmia, jotka voitaisiin ratkaista maksimoimalla muuttujat peräkkäin jossain järjestyksessä. Yksi tällainen esimerkki on täydellinen kuljetusongelma, kun kustannustekijässä on erityinen ominaisuus, jonka ranskalainen matemaatikko Gaspard Monge löysi yli sata vuotta sitten. Tätä lähestymistapaa, jota Hoffmanin paperissa kutsutaan yksinkertaisesti "yksinkertaiseksi", Edmonds ja Fulkerson pitivät myöhemmin "ahneena". Monge-ominaisuus synnyttää antimatroidin, ja tämän antimatroidin käytön ansiosta Hoffmanin tulos voidaan helposti laajentaa epätäydellisiin kuljetusongelmiin. Hoffman käytti uudelleen termiä "ahne" kuvaamaan 0-1 matriisien alaluokkaa, jolle kaksoislineaarinen ohjelma voidaan ratkaista ahneella algoritmilla kaikille oikealle puolelle ja kaikille tavoitefunktioille, joissa on pienenevät (muuttujaindeksin mukaan) kertoimet. . Yhdessä Kolenin ja Sakarovichin kanssa hän osoitti, että näille matriiseille vastaavalla kokonaislukuohjelmalla on kokonaislukuoptimaalinen ratkaisu kokonaislukudatalle. Tyylikäs ja ytimekäs paperi vuodelta 1992 luonnehtii 0-1 matriiseja, joiden pakkaus- ja päällystysongelmat voidaan ratkaista ahneella lähestymistavalla. Se tarjoaa tulosten yhdistämisen lyhimmän polun ja pienimmän virittävän puun ongelmille. Hänen viimeinen artikkelinsa aiheesta "Ahneista algoritmeista, osittain järjestetyistä sarjoista ja submodulaarisista funktioista", joka on kirjoittanut yhdessä Dietrichin kanssa, ilmestyi vuonna 2003.

Hoffman rakensi yhdessä Robert Singletonin kanssa Hoffman-Singleton-graafin [5] , joka on ainutlaatuinen Mooren graafi , jonka aste on 7 ja halkaisija 2 [3] . Vuonna 1963 hän rakensi Hoffman -graafin , joka, vaikka onkin kospektraalinen neliulotteisen hyperkuution Q 4 [6] graafin kanssa , mutta jonka säde on 3 (on sellaisia ​​pisteitä, joiden lyhin polku mihin tahansa muuhun kärkeen kuvaajan säde koostuu enintään kolmesta reunasta), kun taas hyperkuutiograafin Q 4 säde on 4 [7] .

Palkinnot ja tunnustukset

Hoffman valittiin National Academy of Sciences -akatemiaan vuonna 1982 [1] , American Academy of Arts and Sciences -akatemiaan vuonna 1987 [1] ja Institution for Operations Research and Management Sciences (INFORMS) ensimmäiseksi jäseneksi vuonna 2002. [8] . Vuonna 1992 hänelle myönnettiin John von Neumannin teoreettinen palkinto yhdessä Philip Wolfin (myös IBM:ltä) kanssa [1] . Tieteiden kunniatohtori Technionista (Israel Institute of Technology) vuodesta 1986.

Pitkän uransa aikana Hoffman toimi yhdentoista aikakauslehden toimituksessa ja oli englanninkielisen lehden päätoimittaja ja perustaja.  Lineaarinen algebra ja sen sovellukset [1] . Uriel Rothblum kirjoitti Hoffmanin 65-vuotispäivän numerossa julkaistussa elämäkerrassa, että "Tieteellisten ja ammatillisten saavutustensa lisäksi Hoffmanilla on vertaansa vailla oleva kyky nauttia kaikesta tekemästään. Hän rakastaa laulamista, pingistä, sanaleikkejä, nokkelia tarinoita ja ehkä enemmän kuin mitään muuta matematiikkaa .

Valitut julkaisut

• Hoffman AJ, Jacobs W. Smooth patterns of production  //  Management Science. - 1954. - Voi. 1 , iss. 1 . — s. 86–91 .
• Hoffman, AJ, Singleton, RR Moore-graafit, joiden halkaisija on 2 ja 3 // IBM Journal of Research and Development. - 1960. - V. 5 , no. 4 . — S. 497–504 . - doi : 10.1147/rd.45.0497 .
• Hoffman AJ Graafin polynomista   // Amer . Matematiikka. Kuukausittain. - 1963. - Voi. 70 . - s. 30-36 .
• Hoffman AJ, Wolfe P. History of Traveling Salesman problem // The Travelling Salesman Problem  (Eng.) / Lawler EL, Lenstra JK, Rinnooy Kan AHG, & Shmoys DB, toim. - John Wiley, 1985.

Täydellinen luettelo julkaisuista on henkilökohtaisella sivulla [1] .

Muistiinpanot

1. ↑ 1 2 3 4 5 6 Henkilökohtainen sivu, IBM. Alan Hoffman  . IBM:n tutkimus. Haettu 14. marraskuuta 2011. Arkistoitu alkuperäisestä 14. maaliskuuta 2012.
2. ↑ 1 2 3 4 5 6 7 Alan J. Hoffmanin elämäkerta
3. ↑ 12 A.E. _ Brouwer ja JH van Lint. Voimakkaasti säännölliset kaaviot ja osittaiset geometriat // Enumeration and Design  (englanniksi) / DH Jackson, & SA Vanstone (Toim.). – Academic Press Inc. - s. 85-122.
4. ↑ Hoffman, AJ (Alan Jerome), 1924-. Valitut Alan Hoffmanin artikkelit kommentteineen . - River Edge, NJ: World Scientific, 2003. - ISBN 978-981-279-693-6 .
5. ↑ Hoffman, AJ, Singleton, R. R. Moore-graafit, joiden halkaisija on 2 ja 3, 1960 .
6. ↑ Hoffman, A.J. On the Polynomial of a Graph, 1963 .
7. ↑ Weisstein, Eric W. Hoffman  - kaavio Wolfram MathWorld -verkkosivustolla .
8. ↑ Fellows: Aakkosellinen  luettelo . Toiminnantutkimuksen ja johtamistieteiden laitos. Haettu: 9.10.2019.

Temaattiset sivustot	Matemaattinen sukututkimus zbMATH Avoinna
Bibliografisissa luetteloissa GND : 1103166549 ISNI : 0000 0001 1463 2648 J9U : 987007431043105171 LCCN : n78042498 NLG : 221689 NTA : 07088692X NUKAT : n2006011297 SUDOC : 164195823 VIAF : 110277368 WorldCat VIAF : 110277368