In the bottleneck multiple knapsack problem, we are given a set of items and a set of knapsacks, where each item has a profit and a weight, and each knapsack has a capacity. Our goal is to assign items to knapsacks so as to maximize the minimum profit received by any knapsack subject to the capacity constraint. When all knapsacks have identical capacity, we give a (2/3 - ε)-approximation algorithm for any constant ε > 0. This result almost matches the (2/3 + ε) inapproximability bound for the bottleneck multiple subset sum problem (Caprara et al., 2000). When the knapsacks can have arbitrary capacities, we propose a (1/2 - ε)-approximation algorithm for any constant ε > 0. We also prove a hardness bound of (1/2 + ε) for any constant ε > 0.

For a positive integer k ≥ 1 , a k -star ( k + -star, k − -star, respectively) is a connected graph containing a degree- ℓ vertex and ℓ degree-1 vertices, where ℓ = k ( ℓ ≥ k , 1 ≤ ℓ ≤ k , respectively). The k + -star packing problem is to cover as many vertices of an input graph G as possible using vertex-disjoint k + -stars in G ; and given k > t ≥ 1 , the k − / t -star packing problem is to cover as many vertices of G as possible using vertex-disjoint k − -stars but no t -stars in G . Both problems are NP-hard for any fixed k ≥ 2 . We present a ( 1 + k 2 2 k + 1 ) - and a 3 2 -approximation algorithms for the k + -star packing problem when k ≥ 3 and k = 2 , respectively, and a ( 1 + 1 t + 1 + 1 / k ) -approximation algorithm for the k − / t -star packing problem when k > t ≥ 2 . They are all local search algorithms and they improve the best known approximation algorithms for the problems, respectively.

We study the fair allocation of indivisible items to n agents to maximize the utilitarian social welfare, where the fairness criterion is envy-free up to one item and there are only two different utility functions shared by the agents. We present a 2-approximation algorithm when the two utility functions are normalized, improving the previous best ratio of 16 √n shown for general normalized utility functions; thus this constant ratio approximation algorithm confirms the APX-completeness in this special case previously shown APX-hard. When there are only three agents, i.e., n = 3, the previous best ratio is 3 shown for general utility functions, and we present an improved and tight 5/3-approximation algorithm when the two utility functions are normalized, and a best possible and tight 2-approximation algorithm when the two utility functions are unnormalized.

The problem studied in this paper is to find a collection of vertex-disjoint paths in a given graph G = ( V , E ) such that each path has length at least k , called a long path, and the total number of edges on these paths is maximized. The problem is NP-hard for any fixed k or when k is part of the input, by a reduction from the Hamiltonian path problem. Berman and Karpinski presented a 7/6-approximation algorithm for k = 1 , but for a general k ≥ 2 , there is no approximation algorithm directly for the problem. We present the first local search ( 0.4394 k + O ( 1 ) ) -approximation algorithm for any fixed k ≥ 1 , and a 1.4254-approximation algorithm for k = 2 built on top of a maximum triangle-free path-cycle cover.

Given a digraph G=(V,E), the k-path partition problem aims to find a minimum collection of vertex-disjoint directed paths, each of order at most k, to cover all the vertices of V. The problem has various applications in facility location, network monitoring, transportation networks and others. Its special case on undirected graphs is NP-hard when k≥3, and has received much study recently from the approximation algorithm perspective. However, the general problem on digraphs is seemingly untouched in the literature. We fill the gap with the first k/2-approximation algorithm, for any k≥3, based on a novel concept of enlarging walk to minimize the number of singletons in the k-path partition. Secondly, for k=3, we define a second novel kind of enlarging walks to greedily reduce the number of 2-paths in the 3-path partition and propose an improved 13/9-approximation algorithm. Lastly, for any k≥7, we present an improved (k+2)/3-approximation algorithm built on the maximum path-cycle cover followed by a careful 2-cycle elimination process.

The minimum k-path partition (Min-k-PP for short) problem targets to partition an input graph into the smallest number of paths, each of which has order at most k. We focus on the special case when k=3. Existing literature mainly concentrates on the exact algorithms for special graphs, such as trees. Because of the challenge of NP-hardness on general graphs, the approximability of the Min-3-PP problem attracts researchers' attention. The first approximation algorithm dates back about 10 years and achieves an approximation ratio of 3/2, which was recently improved to 13/9 and further to 4/3. We investigate the 3/2-approximation algorithm for the Min-3-PP problem and discover several interesting structural properties. Instead of studying the unweighted Min-3-PP problem directly, we design a novel weight schema for l-paths, l in {1, 2, 3}, and investigate the weighted version. A greedy local search algorithm is proposed to generate a heavy path partition. We show the achieved path partition has the least 1-paths, which is also the key ingredient for the algorithms with ratios 13/9 and 4/3. When switching back to the unweighted objective function, we prove the approximation ratio 21/16 via amortized analysis.

The maximum duo-preservation string mapping (Max-Duo) problem is the complement of the well studied minimum common string partition (MCSP) problem, both of which have applications in many fields including text compression and bioinformatics. k-Max-Duo is the restricted version of Max-Duo, where every letter of the alphabet occurs at most k times in each of the strings, which is readily reduced into the well known maximum independent set (MIS) problem on a graph of maximum degree \Delta \le 6(k-1). In particular, 2-Max-Duo can then be approximated arbitrarily close to 1.8 using the state-of-the-art approximation algorithm for the MIS problem. 2-Max-Duo was proved APX-hard and very recently a (1.6 + \epsilon)-approximation was claimed, for any \epsilon > 0. In this paper, we present a vertex-degree reduction technique, based on which, we show that 2-Max-Duo can be approximated arbitrarily close to 1.4.