Bin packing under linear constraints

In this paper, we study a bin packing problem in which the sizes of items are determined by k linear constraints, and the goal is to decide the sizes of items and pack them into a minimal number of unit sized bins. We first provide two scenarios that motivate this research. We show that this problem is NP-hard in general, and propose several algorithms in terms of the number of constraints. If the number of constraints is arbitrary, we propose a 2-approximation algorithm, which is based on the analysis of the Next Fit algorithm for the bin packing problem. If the number of linear constraints is a fixed constant, then we obtain a PTAS by combining linear programming and enumeration techniques, and show that it is an optimal algorithm in polynomial time when the number of constraints is one or two. It is well known that the bin packing problem is strongly NP-hard and cannot be approximated within a factor 3 / 2 unless P = NP. This result implies that the bin packing problem with a fixed number of constraints may be simper than the original bin packing problem. Finally, we discuss the case when the sizes of items are bounded.     

Some graph optimization problems with weights satisfying linear constraints

In this paper, we study several graph optimization problems in which the weights of vertices or edges are variables determined by several linear constraints, including maximum matching problem under linear constraints (max-MLC), minimum perfect matching problem under linear constraints (min-PMLC), shortest path problem under linear constraints (SPLC) and vertex cover problem under linear constraints (VCLC). The objective of these problems is to decide the weights that are feasible to the linear constraints, and find the optimal solutions of corresponding graph optimization problems among all feasible choices of weights. We find that these problems are NP-hard and are hard to be approximated in general. These findings suggest us to explore various special cases of them. In particular, we show that when the number of constraints is a fixed constant, all these problems are polynomially solvable. Moreover, if the total number of distinct weights is a fixed constant, then max-MLC, min-PMLC and SPLC are polynomially solvable, and VCLC has a 2-approximation algorithm. In addition, we propose approximation algorithms for various cases of max-MLC.

     

Related machine scheduling with machine speeds satisfying linear constraints

Journal of Combinatorial Optimization - We propose a related machine scheduling problem in which the processing times of jobs are given and known, but the speeds of machines are variables and must...