Neke od vas moglo bi zanimati (kao što je mene zanimalo) koliko će vam znanje algoritama, napose onih s natjecanja, pomoći u “stvarnom svijetu” tj. u radu u znanosti ili softverskoj industriji. Dok je grubi i vrlo načelan odgovor taj da će pomoći jako, ali možda više neizravno (u načinu razmišljanja i programiranja) nego izravno, za primjenu u znanosti odgovorit ću navodeći primjere onih svojih članaka koji su s takvim, kombinatornim algoritmima povezani na očitiji način. Krenimo redom, kronološki.

1. Još 2012., kao student preddiplomskog studija na PMF-u, s profesorom Željkom Ilićem s FER-a napisao sam članak iz telekomunikacija gdje smo definirali odgovarajući problem tako da se može riješiti dinamičkim programiranjem. Evo ukratko o čemu se radi. U nekim bežičnim mrežama (OFDMA) signal se šalje većem broju korisnika na način da ga svaki korisnik sluša na svojim frekvencijskim potkanalima. Postavlja se pitanje podjele potkanala na korisnike (za svaki potkanal odlučiti kojem korisniku ide) ako znamo koliko kojem korisniku “paše” neki potkanal (kapacitet/brzina tj. data rate); te podatke možemo promatrati kao matricu dimenzija broj potkanala × broj korisnika. E sad, uvedemo li ograničenje da svaki korisnik mora dobiti uzastopni niz potkanala ili slot (što se opravdava potrebom za manjom količinom signalizacije i realnom sličnošću vrijednosti susjednih potkanala), ukupni maksimum dobije se jednostavnom dinamikom gdje dp(k, m) označava optimalnu podjelu prvih m potkanala na prvih k korisnika, gdje su korisnici prethodno heuristički sortirani.
2. Drugi članak s istom tematikom radio sam s još jednim algoritmašem, prijateljem Marinom Smiljanićem (i spomenutim prof. Ilićem). Ovdje smo razmatrali i fairness tj. potrebu da korisnici budu zadovoljeni u određenim omjerima, što smo riješili pohlepnom heuristikom – evo “screenshota” iz članka (chunk je unaprijed fiksiran skup uzastopnih potkanala): Potom treba rasporediti snagu po potkanalima da se maksimizira ukupna brzina. Nakon malo matematike to se svodi na jednadžbu oblika f(x) = P, gdje je P ukupna snaga koju raspoređujemo. Budući da je f rastuća, jednadžba se riješi binarnim pretraživanjem.
3. Navest ću i konferencijski članak čiji sam koautor, a glavni je i najzaslužniji autor moj kolega Petar Afrić. Riječ je o kombinatornom problemu vezanom uz grafove, tzv. school bus routing problem, gdje (pojednostavljeno rečeno) učenici trebaju biti dodijeljeni potencijalnim autobusnim postajama te se trebaju konstruirati rute autobusa tako da se svi učenici prevezu do škole uz što manju ukupnu udaljenost. Problem u praksi nije optimalno rješiv jer je NP-težak. Afrić je smislio vrlo zanimljiv heuristički algoritam; ovdje ga ne opisujem jer bi zauzeo previše mjesta.
4. U članku koji je dio mog doktorata (pod mentorstvom prof. Marina Šilića) bavim se problemom odabira instanci web usluga u oblaku: koja instanca će odgovoriti na koji zahtjev (request) u određenom trenutku, a da se nijedna ne preoptereti i da se zadovolje određena ograničenja na kvalitetu usluge? Vrlo pojednostavljeno, to je nekakav višekriterijski matching. Taj sam problem, uz određene heurističke definicije cijene i drugih varijabli, sveo na kombinatorni transportation problem koji je poseban slučaj minimum-cost maximum-flow problema i rješava se poznatim algoritmima.

Nije mi poznato primjenjuje li se neki od ovih algoritama u praksi: znanost predlaže modele, a industrija ih može i ne mora pratiti i implementirati. U nedostatku aktualne primjene valja se prisjetiti da je doprinos znanosti vrlo rijetko izravan: jedan rad se nadovezuje na drugi, drugi na treći, treći na četvrti i tako dalje, u nadi za konvergencijom u nešto što će ljudima olakšati život. Ako vam to ne zvuči uvjerljivo, možda biste trebali ići u industriju; tamo je i više novaca. Zbog uobičajene politike znanstvenih časopisa koji zarađuju na pretplatama, ovi članci nisu javno dostupni pa ih ne smijem ni javno objaviti. Ako je netko zainteresiran da ih pročita, neka mi se slobodno javi preko kontakt forme. Ono što mogu objaviti je prezentacija u kojoj je velik dio posvećen radu pod brojem 4, te Afrićeva prezentacija o radu pod brojem 3.