Search

Abstract: The minimum clique partitioning problem in weighted interval graphs (MCPI) is defined as follows. Given an interval graph with nonnegative node weights, the problem is to partition the nodes into a set of cliques such that the sum of node weights in each clique is no more than a given bound. The objective of the problem is to minimize the number of cliques. Recently, Chen et al. [M. Chen, J. Li, J. Li, W. Li, and L. Wang, Some approximation algorithms for the clique partitioning problem in weighted interval graphs, Theoretical Computer Science 381 (2007), 124–133] proposed three approximation algorithms having constant factors 3, 2.5 and 2, and a linear time optimal algorithm for the case with identical weights. In this paper, we show that their factor 2 algorithm does not achieve the expected approximation ratio and the linear time algorithm cannot give an optimal solution for the identical weights case. We also develop an approximation algorithm with factor 2 for the variable weights case and an exact algorithm for the identical weights case. [Copyright &y& Elsevier]

Abstract: In this paper, we study the approximability properties of symmetric TSP under an approximation measure called the differential ratio. More precisely, we improve up to (for any ) the best differential ratio of known so far, given in Hassin and Khuller, [R. Hassin, S. Khuller, z-approximations, J. Algorithms, 41 (2) (2001) 429–442]. [Copyright &y& Elsevier]

Abstract: For MAX SAT, which is a well-known NP-hard problem, many approximation algorithms have been proposed. Two types of best approximation algorithms for MAX SAT were proposed by Asano and Williamson: one with best proven performance guarantee 0.7846 and the other with performance guarantee 0.8331 if the performance guarantee of the Zwick''s algorithm for MAX SAT is as conjectured. Both algorithms are based on their sharpened analysis of Goemans and Williamson''s LP-relaxation for MAX SAT. In this paper, we present an improved analysis which is simpler than the previous analysis. Furthermore, algorithms based on this analysis will play a role as a better building block in designing an improved approximation algorithm for MAX SAT. Actually we show an example that algorithms based on this analysis lead to approximation algorithms with performance guarantee 0.7877 and conjectured performance guarantee 0.8353 which are slightly better than the best known corresponding performance guarantees 0.7846 and 0.8331, respectively. [Copyright &y& Elsevier]

Abstract: Given a set of positive numbers, the max–min partition problem asks for a k-partition such that the minimum part is maximized. The min–ratio partition problem has the similar definition but the objective is to minimize the ratio of the maximum to the minimum parts. In this paper, we analyze the performances of the longest processing time (LPT) algorithm for the two problems. We show that the tight bounds of the LPT are, respectively and . [Copyright &y& Elsevier]

Abstract: It has been a challenging open problem whether there is a polynomial time approximation algorithm for the VERTEX COVER problem whose approximation ratio is bounded by a constant less than 2. In this paper, we study the VERTEX COVER problem on graphs with perfect matching (shortly, VC-PM). We show that if the VC-PM problem has a polynomial time approximation algorithm with approximation ratio bounded by a constant less than 2, then so does the VERTEX COVER problem on general graphs. Approximation algorithms for VC-PM are developed, which induce improvements over previously known algorithms on sparse graphs. For example, for graphs of average degree 5, the approximation ratio of our algorithm is 1.414, compared with the previously best ratio 1.615 by Halldórsson and Radhakrishnan. [Copyright &y& Elsevier]