Approximation Algorithms for High Multiplicity Strip Packing, Thief Orienteering, and K-Median
Abstract
This thesis investigates three research objectives on three different problems: (1) algorithm design for problems in which the input can be grouped into a small number of classes, demonstrated on the high multiplicity strip packing problem; (2) algorithm design for problems with multiple interdependent sub-problems, demonstrated on the thief orienteering problem; and (3) algorithm design using neural networks with few layers, demonstrated on the k-median problem.
(1) The two-dimensional strip packing problem consists of packing in a rectangular strip of width $1$ and minimum height a set of $n$ rectangles, where each rectangle has width $0 < w \leq 1$ and height $0 < h \leq h_{max}$. We consider the high-multiplicity version of the problem in which there are only $K$ different types of rectangles. For the case when $K = 3$, we give an algorithm that produces solutions requiring at most height $\frac{3}{2}h_{max} + \epsilon$ plus the height of an optimal solution, where $\epsilon$ is any positive constant. For the case when $K = 4$, we give an algorithm yielding solutions of height at most $\frac{7}{3}h_{max} + \epsilon$ plus the height of an optimal solution. For the case when $K > 3$, we give an algorithm that gives solutions of height at most $\lfloor\frac{3}{4}K\rfloor + 1 + \epsilon$ plus the height of an optimal solution.
(2) We consider routing an agent called a \textit{thief} through a weighted graph $G = (V, E)$ from a start vertex $s$ to an end vertex $t$. A set $I$ of items each with weight $w_{i}$ and profit $p_{i}$ is distributed among $V \setminus \{s,t\}$. The thief, who has a knapsack of capacity $W$, must follow a simple path from $s$ to $t$ within a given time $T$ while packing in the knapsack a set of items taken from the vertices along the path of total weight at most $W$ and maximum profit. The travel time across an edge depends on the edge length and current knapsack load.
The thief orienteering problem (ThOP) is a generalization of the orienteering problem, the longest path problem, and the 0-1 knapsack problem. We prove that there exists no approximation algorithm for ThOP with constant approximation ratio unless $\P=\NP$, and we present a polynomial-time approximation scheme (PTAS) for ThOP when $G$ is directed and acyclic (DAG) that produces solutions using time at most $T(1 + \epsilon)$ for any constant $\epsilon > 0$. We show how to transform instances of ThOP on outerplanar and series-parallel graphs into equivalent instances of ThOP on DAGs; therefore, yielding a PTAS for these graph classes as well. We present a fully polynomial-time approximation scheme (FPTAS) for ThOP on arbitrary undirected graphs where the travel time depends only on the lengths of the edges and $T$ is the length of a shortest path from $s$ to $t$ plus a constant $K$. Finally, we present a FPTAS for a version of the problem where the input graph is a clique.
(3) The k-median problem (KMP) is a classical clustering problem where given $n$ locations one wants to select $k$ locations such that the total distance between every non-selected location and its nearest selected location is minimized. We present a modified Hopfield network for KMP and experimentally evaluate it against several neural networks and local search algorithms, demonstrating that our algorithm produces solutions very quickly with competitive approximation ratios. We describe several improvements to our algorithm which could help us match the state-of-the-art algorithms.