Seminar za teorijsko računarstvo

lokacija: 
PMF Matematički odsjek
vrijeme: 
24.11.2014 - 15:00 - 17:00

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

Share this