tailieunhanh - On the performance of a simple approximation algorithm for the longest path problem
The longest path problem is known to be NP-hard. Moreover, it cannot be approximated within a constant ratio, unless P = NP. The best known polynomial time approximation algorithms for this problem essentially find a path of length that is the logarithm of the optimum. | Journal of Computer Science and Cybernetics, , (2019), 57–68 DOI ON THE PERFORMANCE OF A SIMPLE APPROXIMATION ALGORITHM FOR THE LONGEST PATH PROBLEM 2 NGUYEN THI PHUONG1,∗ , TRAN VINH DUC1 , LE CONG THANH 1 Hanoi 2 University of Science and Technology Institute of Mathematics, VAST ∗ Abstract. The longest path problem is known to be NP-hard. Moreover, it cannot be approximated within a constant ratio, unless P = NP. The best known polynomial time approximation algorithms for this problem essentially find a path of length that is the logarithm of the optimum. In this paper we investigate the performance of an approximation algorithm for this problem in almost every case. We show that a simple algorithm, based on depth-firstpsearch, finds on almost every undirected graph G = (V,p E) a path of length more than |V | − 3 |V | log |V | and so has performance ratio less than 1 + 4 log |V |/|V |.1 Mathematics Subject Classification (2010): 68Q17. Keywords. Path; Hamiltonian path; Approximation algorithm and performance ratio. 1. INTRODUCTION A well-known problem in graph theory is the longest path problem on graphs (finite, simple, loopless and undirected), write LPath for short, ., the problem of finding in a given graph G = (V, E) a sequence v0 v1 v2 . . . vk with the largest number of distinct vertices from V such that vi−1 vi ∈ E for 1 ≤ i ≤ k. This problem is known to be NP-hard [11] and so cannot be solved in polynomial time unless P = NP. From practical requirements, the approximate approach to LPath is an effective solution. However, the problem LPath is also known to be NP-hard even in approximate solutions [16]. For convenience, we recall the concept of the performance of an approximation algorithm. The terminology and notation follow that in [11]. Performance ratios of an approximation algorithm We are interested in the performance of approximation algorithms in the worst case and also in
đang nạp các trang xem trước
