Weekly Activities

On the performance of approximating longest path
Speaker: Tran Vinh Duc

Time: 9h30, Thursday, May 11, 2017
Location: Room 201, Institute of Mathematics, 18 Hoang Quoc Viet
Abtract: We consider the problem of finding a path of maximum length in a graph. This problem is known to be NP-hard. Moreover, no polynomial-time algorithm can find a constant factor approximation to this problem unless P=NP. The best known polynomial time approximation algorithms for this problem essentially find a path of logarithmic length.
In this talk, we investigate the performance behaviour of some approximation algorithms for this problem in almost every case. We show that the simple algorithm, which is based on an well-known depth-first search, on almost every  graph G=(V,E) always finds a path of length more than |V|/2 + |V|/log |V| and so has the performance ratio less than 2.
Joint work with Nguyễn Thị Phương and Lê Công Thành.

Back