A díjgyűjtő utazó ügynök probléma

Témavezető:	Király Tamás
	ELTE TTK, Operációkutatási Tsz.
email:	tamas.kiraly@ttk.elte.hu

Projekt leírás

A klasszikus utazó ügynök probléma díjgyűjtő változatában az ügynöknek nem kell a gráf összes csúcsát meglátogatnia, de a meglátogatott csúcsok után különböző értékű díjakat kap. Erre a problémára sokáig nem volt ismert olyan közelítő algoritmus, ami kétszeresnél lényegesen jobb garantált közelítést adna. Nemrég azonban Blauth és Nägele felfedezett egy 1,774-közelítő algoritmust, és ezt Klein-nel továbbfejlesztették 1,599-közelítéssé. A feladat az ezekben a cikkekben szereplő új technikák megismerése és speciális esetek vizsgálata.

Előfeltételek

Előzetes egyeztetés

Hivatkozások

Blauth, J., & Nägele, M. (2023, June). An improved approximation guarantee for Prize-Collecting TSP. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (pp. 1848-1861).

Blauth, J., Klein, N., & Nägele, M. (2023). A Better-Than-1.6-Approximation for Prize-Collecting TSP. arXiv preprint arXiv:2308.06254.