Electronic Thesis and Dissertation Repository

Thesis Format

Integrated Article

Degree

Doctor of Philosophy

Program

Computer Science

Supervisor

Solis-Oba, Roberto

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.

Summary for Lay Audience

Many real-life applications require computing solutions to complex optimization problems: Using a computer requires solving a series of scheduling problems to coordinate the execution of its various processes, ordering a package from Amazon requires solving a variety of packing and scheduling problems to transport and deliver products, using Google Maps to give directions requires solving network routing problems to provide an optimum path, and so on. Moreover, businesses in fields such as manufacturing, supply chain management, and other operations research fields are faced with an even larger number of complicated optimization problems to solve; modeling each business's unique industrial challenge requires adding a variety of constraints to classical problem formulations and hence the same algorithm cannot be used to solve all of the problems, even if the problems are closely related. Research that creates new and improved algorithms for optimization problems enables many of today’s technologies. Hence, the design and analysis of efficient algorithms for these problems is of critical importance.

This thesis focuses on the design and analysis of efficient algorithms for optimization problems. In particular, we investigate 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) We design an approximation algorithm for the high multiplicity strip packing problem, which involves efficiently placing rectangles inside of a bigger rectangle, that takes advantage of the small number of input classes to outperform the more general algorithms that treat all the input items individually.

(2) We design an approximation algorithm for a restricted version of the thief orienteering problem, which involves selecting a route between two points and collecting items along that route and placing them in a knapsack, that can compute solutions arbitrarily close to an optimal solution at the expense of taking longer to compute solutions.

(3) We design a modified Hopfield neural network for the k-median problem, which involves identifying a number of cluster centers such that the input locations are all assigned to a nearby cluster, and perform an experimental evaluation against other local search algorithms and neural networks.

We conclude this thesis with a discussion of future research that could improve or extend our work.

Download

Share

COinS