Seminar za teorijsko računarstvo
U sklopu poslijediplomskog Seminara za teorijsko računarstvo
u ponedjeljak 24. studenog 2014. u 15 sati, predavaonica 104 PMF-MO,
Ante Ćustić, doktorand TU Graz, održat će predavanje pod naslovom:
"Geometrijska verzija 3-dimezionalnog problema dodjeljivanja".
Sažetak: Proučavamo složenost specijalnog slučaja 3-dimenzionalnog problema
dodjeljivanja. Zadan je skup točaka u Kartezijevom prostoru u tri boje.
Udaljenost među točkama definirana je normom s proizvoljnom jediničnom
kuglom. Cilj nam je particionalizirati zadane točke u trobojne trokute tako
da je suma opsega trokuta minimalna (ili maksimalna). (Svi prezentirani
rezultati vrijedit će i za jednobojnu verziju problema.) Glavni rezultati
koji će se prezentirani su sljedeći: Minimalizirajuća verzija problema je
NP-teška za svaku takvu normu, čak i ako su točke u dvodimenzionalnom
prostoru. Suprotno tome, maksimizirajuća verzija je polinomijalno rješiva
ako je jedinična kugla politop.
Pozivaju se svi članovi seminara kao i ostali zainteresirani da prisustvuju
ovom predavanju.
Robert Manger