Combinatorial Optimization Problems with Conflicts or Vectors

In this thesis titled, combinatorial optimization problem with conflicts or vectors, we introduce three combinatorial optimization problems and investigate to what extent these problems can still be solved in polynomial time or approximated.

First, we look at Balanced Optimization with vector costs. An instance of a balanced optimization problem with vector costs consists of a ground set X, a cost vector for every element of X, and a system of feasible subsets over X. The goal is to find a feasible subset that minimizes the so-called imbalance of values in every coordinate of the underlying vector costs. Balanced optimization problems with vector costs are equivalent to the robust optimization version of balanced optimization problems under the min-max criterion. We regard these problems as a family of optimization problems; one particular member of this family is the known balanced assignment problem[SF1]  with vector costs. We investigate the complexity and approximability of robust balanced optimization problems in a fairly general setting. We identify a large family of problems that admit a 2-approximation in polynomial time, and we show that for many problems in this family this approximation factor 2 is best-possible (unless P=NP).

Second, we discuss the Transportation Problem with Conflicts. The classical transportation problem is a fundamental problem in Operations Research, where items need to be transported from supply nodes (each with a given supply) to demand nodes (each with a given demand) in the cheapest possible way. Here, we are interested in a generalization of the transportation problem where, each supply node has a (possibly empty) set of conflicting pairs of demand nodes, and each demand node a (possibly empty) set of conflicting pairs of supply nodes. Each supply node may only send supply to at most one demand node of each conflicting pair. Likewise, each demand node may only receive supply from at most one supply node of each conflicting pair. We call the resulting problem the transportation problem with conflicts (TPC). We show that the complexity of TPC depends upon the structure of the so-called conflict graph that follows from the conflicting pairs. More concrete, we show that for many graph-classes the corresponding TPC remains NP-hard, and for some special cases, we derive constant factor approximation algorithms.

Third, we look at Partitioning Vectors into quadruples. In this problem 4n given vectors need to be partitioned into n clusters of four vectors each. A cluster of four vectors is called a quad, and the cost of a quad is the sum of the component-wise maxima of the four vectors in the quad. The problem is to partition the given 4n vectors into n quads with minimum total cost. We analyze the worst-case behavior of a straightforward matching-based algorithm, and prove that this algorithm is a 3/2-approximation algorithm for this partitioning problem. We also analyze the performance of this algorithm on special cases of the problem. In the most restrictive special case, we consider pairwise distinct binary vectors that contain exactly two 1’s and their underlying graph has to be connected. For this special case, we prove that the problem is NP-hard and that the matching-based algorithm is a 5/4-approximation algorithm.