Shayan Oveis Gharan găsește cea mai scurtă cale către succes

Shayan Oveis Gharan, 30 de ani
Informatician teoretic
Universitatea din Washington

Este o problemă care sună simplă, dar cele mai bune minți din matematică au nedumerit-o de generații: un vânzător vrea să-și vândă mărfurile în mai multe orașe și să se întoarcă acasă când a terminat. Dacă vizitează doar o mână de locuri, îi este ușor să-și programeze vizitele pentru a crea cel mai scurt traseu dus-întors. Dar sarcina devine rapid greoaie pe măsură ce numărul de destinații crește, sporind numărul de rute posibile.

Informaticianul teoretician Shayan Oveis Gharan, profesor asistent la Universitatea Washington din Seattle, a făcut progrese record în acest puzzle, cunoscut sub numele de problema vânzătorului ambulant. Problema este renumită în cercurile matematice pentru că este înșelător de ușor de descris, dar dificil de rezolvat. Dar Oveis Gharan a persistat. „Este necruțător”, spune Amin Saberi de la Universitatea Stanford, fostul doctorat al lui Oveis Gharan. consilier. „Pur și simplu nu renunță.”

Concentrarea neclintită a lui Oveis Gharan i-a permis să identifice conexiuni între domenii aparent neînrudite ale matematicii și informaticii. El examinează munca celor mai strălucite minți din domeniu și adaptează aceste tehnici pentru a se potrivi scopurilor sale. Această strategie – aducerea de noi instrumente la problemele vechi – stă la baza salturilor pe care le-a făcut în două variante ale problemei vânzătorului ambulant.

„Dacă vrei să construiești o casă, trebuie să ai un baros și o nivelă, o cheie, o bandă de măsură”, spune el. „Trebuie să ai o mulțime de instrumente și să le folosești unul după altul.” Oveis Gharan, în vârstă de 30 de ani, își adaugă setul de instrumente cu cele mai recente progrese în domenii cu nume care sună obscur, inclusiv teoria grafurilor spectrale, teoria poliedrică și geometria polinoamelor. Și într-o întorsătură pe care doar Oveis Gharan a văzut-o venind, o soluție recentă la o problemă de lungă durată, originară din mecanica cuantică, s-a dovedit a fi piesa lipsă dintr-un aspect al puzzle-ului vânzătorului.

Pentru turul unui vânzător în cinci orașe, există doar 12 rute posibile; este destul de ușor să-l alegeți pe cel care va economisi cel mai mult gaz. Dar pentru 20 de orașe, există 60 de cvadrilioane de posibilități, iar pentru 80 de orașe, există mai multe rute decât numărul de atomi din universul observabil. Bazarea pe forța brută – calcularea distanțelor tuturor rutelor posibile – este insolubilă pentru toate cazurile, cu excepția celor mai ușoare. Cu toate acestea, nimeni nu a găsit o metodă simplă care să găsească rapid calea cea mai scurtă pentru orice număr și aranjament de orașe. Dilema are o importanță reală: companii precum Amazon și Uber, de exemplu, doresc să transporte mărfuri și oameni către multe destinații în cel mai eficient mod posibil.

Crescând în țara sa natală, Iran, Oveis Gharan a descoperit o apreciere naturală pentru puzzle-urile provocatoare. În gimnaziu, a dobândit o carte de probleme de la competițiile olimpiadelor de matematică din Uniunea Sovietică. Ca student, „Am tendința de a fi unul dintre cei mai lenți”, spune Oveis Gharan, observând că de obicei nu a fost primul care a înțeles o nouă teoremă. Dar, în câțiva ani, el a analizat cu îndârjire cartea de 200 de pagini.

De asemenea, efortul i-a oferit lui Oveis Gharan primul gust în colecția de instrumente, prin colaborarea cu colegii de clasă care i s-au alăturat în rezolvarea problemelor de matematică. Oveis Gharan a descoperit că soluțiile vin mai ușor atunci când multe minți contribuie. „Fiecare persoană gândește și rezolvă problemele în mod diferit”, spune el. „Odată ce cineva este expus la multe idei și moduri diferite de a gândi cu privire la o problemă, asta va ajuta foarte mult la creșterea lărgirii direcțiilor de atacare a problemei.”

Oveis Gharan a urmat cursurile Universității de Tehnologie Sharif din Teheran înainte de a face primele descoperiri în problema vânzătorului ambulant ca student absolvent la Universitatea Stanford. El a petrecut peste un an dând doar o fațetă spinoasă, înainte de a trece la o bursă postdoctorală la Universitatea din California, Berkeley.

Un tur la Seattle

Pentru un tur al șapte destinații, există 360 de rute posibile. Această hartă arată cea mai scurtă rută (măsurată în timpul de călătorie) între șapte locații din Seattle pe care le vizitează Shayan Oveis Gharan.

În loc să atace problema frontal, Oveis Gharan lucrează la soluții aproximative – rute care sunt puțin mai lungi decât calea optimă, dar care pot fi calculate într-un timp rezonabil. Din anii 1970, informaticienii cunosc o strategie pentru a găsi rapid o rută care este cu cel mult 50 la sută mai lungă decât cea mai scurtă cale posibilă. Recordul s-a menținut timp de zeci de ani, până când Oveis Gharan l-a abordat împreună cu Saberi și Mohit Singh, pe atunci de la Universitatea McGill din Montreal.

Într-o lucrare publicată în 2011, echipa a făcut ceea ce ar putea părea o îmbunătățire infinitezimală, micșorând cifra de 50 la sută cu patru sutimi de trilionime de trilionime de trilionime de trilionime de trilionime de punct procentual. „Oamenii își bat joc de lucrarea noastră din cauza acestei mici îmbunătățiri”, spune Oveis Gharan, „dar problema este că în zona noastră, numărul real nu este întrebarea majoră”.

În schimb, scopul este de a dezvolta noi idei care să poată începe să rezolve problema, spune Luca Trevisan, un informatician la Berkeley. „Ceea ce este atât de important nu este algoritmul specific pe care l-a conceput, ci faptul că există un set complet nou de tehnici care pot fi aplicate la alte probleme.” În urma progresului, alți oameni de știință au revizuit problema vânzătorului ambulant și au scăzut semnificativ numărul; ruta selectată este acum cu cel mult 40 la sută mai lungă decât cea optimă.

Pentru a-și face descoperirile, Oveis Gharan urmărește literatura științifică dintr-o varietate de domenii matematice. „De fiecare dată când apar lucrări noi sau tehnici noi, el este unul dintre primii oameni care vor ridica lucrarea și o vor citi”, spune Saberi. Pentru a descoperi instrumente în afara ariilor sale de expertiză, Oveis Gharan pune bucăți din problemă cercetătorilor din alte domenii.

În 2015, Oveis Gharan și informaticianul Nima Anari, atunci la Berkeley, au făcut progrese suplimentare în ceea ce privește o soluție aproximativă pentru o versiune mai generală și mai provocatoare a problemei vânzătorului ambulant. În această versiune, distanța de mers de la punctul A la punctul B ar putea să nu fie aceeași cu a merge în direcția opusă – o situație plauzibilă în orașele cu multe străzi cu sens unic. Cercetătorii au avut o modalitate de a estima durata optimă a turului, dar nu au înțeles cât de bună era estimarea. Oveis Gharan și Anari au arătat că a fost exponențial mai bun decât se știa anterior.

Pentru a face acest progres, Oveis Gharan a dezvăluit conexiunile cu o problemă aparent fără legătură în matematică și mecanică cuantică, cunoscută sub numele de problema Kadison-Singer. „A fost cu adevărat surprinzător”, spune informaticianul Daniel Spielman de la Universitatea Yale, parte dintr-o echipă care a rezolvat problema Kadison-Singer în 2013. „Nu a existat nicio legătură evidentă”, spune el. „Shayan este incredibil de genial și incredibil de creativ.”

Oveis Gharan este acum concentrat pe o cucerire ulterioară a acestei versiuni a problemei vânzătorului ambulant. Deși noul său avans ajută la aproximarea duratei optime a turului, nu poate identifica ruta corespunzătoare. În continuare, Oveis Gharan ar dori să producă un algoritm care poate naviga pe cursul corect.

Puteți paria că va continua să adauge la colecția sa de instrumente prin eșantionare din câmpurile matematice și computaționale conexe. „Marele plan este: Încercați să înțelegeți mai bine modul în care aceste zone diferite sunt conectate între ele”, spune Oveis Gharan. „Există multe probleme mari deschise în această intersecție.”