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.

This paper studies the parity-constrained k -supplier (PAR k -supplier) problem, which extends the well-known k -supplier problem. In the PAR k -supplier problem, we are given a set of vertices in a metric space with distances and an integer k . The vertex set is partitioned into a facility set and a client set. Each facility has an odd or even parity requirement. The objective is to select at most k facilities to open and assign each client to an open facility, ensuring that the number of clients assigned to each open facility matches its parity requirement, while also minimizing the maximum distance of any client to its assigned facility. As our main contribution, we design the first constant-factor 9-approximation algorithm for the parity-constrained k -supplier problem. The algorithm is divided into two main phases. In the first phase, we determine the initial set of open facilities with a maximum cardinality of k and the assignment of all the clients. There may include some so-called invalid facilities that do not meet their parity requirements under the initial assignment. In the second phase, we find a matching based on the invalid facilities and reassign some clients accordingly to obtain a feasible solution.