The multicommodity flow problem involves shipping multiple commodities simultaneously through a network so that the total flow over each edge does not exceed the capacity of that edge. The concurrent flow problem also associates with each commodity a demand, and involves finding the maximum fraction z, such that z of each commodity's demand can be feasibly shipped through the network. This problem has applications in message routing, transportation, and scheduling problems. It can be formulated as a linear programming problem, and the best known solutions take advantage of decomposition techniques for linear programming. Often, quickly finding an approximate solution is more important than finding an optimal solution. A solution is epsilon-optimal if it lies within a factor of (1+epsilon) of the optimal solution. We present a combinatorial approximation algorithm for the concurrent flow problem. This algorithm consists of finding an initial flow, and gradually rerouting this flow from more to less congested paths, until an epsilon-optimal flow is achieved. This algorithm theoretically runs much faster than linear programming based algorithms.

We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We first study two linear programming relaxations of the problem, one based on a time-indexed formulation, the other on a completiontime formulation. We show their equivalence by proving that a O(n log n) greedy algorithm leads to optimal solutions to both relaxations. The proof relies on the notion of mean busy times of jobs, a concept which enhances our understanding of these LP relaxations. Based on the greedy solution, we describe two simple randomized approximation algorithms, which are guaranteed to deliver feasible schedules with expected objective value within factors of 1.7451 and 1.6853, respectively, of the optimum. They are based on the concept of common and independent a-points, respectively. The analysis implies in particular that the worst-case relative error of the LP relaxations is at most 1.6853, and we provide instances showing that it is at least e/(e - 1) 1.5819. Both algorithms may be derandomized, their deterministic versions running in O(n2 ) time. The randomized algorithms also apply to the on-line setting, in which jobs arrive dynamically over time and one must decide which job to process without knowledge of jobs that will be released afterwards.

Small Unmanned Aerial Vehicles (UAVs) are currently used in several surveillance applications to monitor a set of targets and collect relevant data. One of the main constraints that characterize a small UAV is the maximum amount of fuel the vehicle can carry. In the thesis, we consider a single UAV routing problem where there are multiple depots and the vehicle is allowed to refuel at any depot. The objective of the problem is to find a path for the UAV such that each target is visited at least once by the vehicle, the fuel constraint is never violated along the path for the UAV, and the total length of the path is a minimum. Mixed integer, linear programming formulations are proposed to solve the problem optimally. As solving these formulations to optimality may take a large amount of time, fast and efficient construction and improvement heuristics are developed to find good sub-optimal solutions to the problem. Simulation results are also presented to corroborate the performance of all the algorithms. In addition to the above contributions, this thesis develops an approximation algorithm for a multiple UAV routing problem with fuel constraints.

Given a set of n points on a plane, in the Minimum Weight Triangulation problem, we wish to find a triangulation that minimizes the sum of Euclidean lengths of its edges. The problem has been studied for more than four decades and is known to be incredibly challenging. In fact, the complexity status of this problem remained open until recently when it was shown to be NP-Hard. We present a novel polynomial-time algorithm that computes a 16-approximation of the minimum weight triangulation---a constant that is significantly smaller than what has been previously known. To construct our candidate solution, our algorithm uses grids to partition edges into levels by increasing weights, so that edges with similar weights appear in the same level. We incrementally triangulate the point set by constructing a growing partial triangulation for each level, introducing edges in increasing order of level. At each level, we use a variant of the ring heuristic followed by a greedy heuristic to add edges, finally resulting in a complete triangulation of the point set. In our analysis, we reduce the problem of comparing the weight of the candidate and the optimal solutions to a comparison between the cardinality of the two underlying graphs. We develop a new technique to compare the cardinality of planar straight-line graphs, and in combination with properties due to the imposed grid structure, we bound the approximation ratio. / Master of Science

<p>The thesis consists of four papers on combinatorial auctions and a summary. The first part is more of a practical nature and contains two papers. In the first paper, we study the performance of a caching technique in an optimal algorithm for a multi-unit combinatorial auction.</p><p>In the second paper, we compare the revenues from a second-price combinatorial auction against a second-price one-shot simultaneous auction. In particular, we show that when the synergy parameter is small, the combinatorial auction gives a higher expected revenue than the one-shot. This is in contrast to an earliear result by Krishna and Rosenthal. We also compare the two mechanisms under the assumption that bidders are risk-averse. Such bidders are more sensitive to financial loss (winner's curse) that they tend to bid less aggressively, which leads to lower revenues. Since a direct analytical approach turns out to be difficult, we present numerical results that show which auction mechanism maximizes the seller's revenue depending on the values of synergy and aversion parameter.</p><p>The second part is more theoretical. Here, we analyze the asymptotic performance of a greedy algorithm for a problem inspired by combinatorial auctions. In particular, we consider a special case in which every bid contains exactly 3 items, and use a Poisson process to model an auction with a random (Poisson) No. of bids. For this restricted case, winner determination problem is equivalent to a maximal 3-set packing on a weighted hypergraph, and hence NP-complete. However, the greedy algorithm approximates this special case within a factor of 3.</p><p>In the third paper, we compute the asymptotic expected size of the partial allocation and its corresponding expected total revenue from the greedy algorithm, for some distribution of bid prices.</p><p>In the final paper, we study the case of a deterministic number of bids, which is proportional to the number of distinguishable items in the auction, say M. Then, we prove that the number of bids allocated, suitably normalized, converges to a Normal random variable as M goes to infinity. As a prelude, we also prove that, both the number of bids allocated and those submitted, again suitably normalized, jointly converge in distribution to a continuous 2-dimensional Gaussian process as M goes to infinity.</p>

The thesis consists of four papers on combinatorial auctions and a summary. The first part is more of a practical nature and contains two papers. In the first paper, we study the performance of a caching technique in an optimal algorithm for a multi-unit combinatorial auction. In the second paper, we compare the revenues from a second-price combinatorial auction against a second-price one-shot simultaneous auction. In particular, we show that when the synergy parameter is small, the combinatorial auction gives a higher expected revenue than the one-shot. This is in contrast to an earliear result by Krishna and Rosenthal. We also compare the two mechanisms under the assumption that bidders are risk-averse. Such bidders are more sensitive to financial loss (winner's curse) that they tend to bid less aggressively, which leads to lower revenues. Since a direct analytical approach turns out to be difficult, we present numerical results that show which auction mechanism maximizes the seller's revenue depending on the values of synergy and aversion parameter. The second part is more theoretical. Here, we analyze the asymptotic performance of a greedy algorithm for a problem inspired by combinatorial auctions. In particular, we consider a special case in which every bid contains exactly 3 items, and use a Poisson process to model an auction with a random (Poisson) No. of bids. For this restricted case, winner determination problem is equivalent to a maximal 3-set packing on a weighted hypergraph, and hence NP-complete. However, the greedy algorithm approximates this special case within a factor of 3. In the third paper, we compute the asymptotic expected size of the partial allocation and its corresponding expected total revenue from the greedy algorithm, for some distribution of bid prices. In the final paper, we study the case of a deterministic number of bids, which is proportional to the number of distinguishable items in the auction, say M. Then, we prove that the number of bids allocated, suitably normalized, converges to a Normal random variable as M goes to infinity. As a prelude, we also prove that, both the number of bids allocated and those submitted, again suitably normalized, jointly converge in distribution to a continuous 2-dimensional Gaussian process as M goes to infinity.

We study a directed network design problem called the $k$-$(S,T)$-connectivity problem; we design and analyze approximation algorithms and give hardness results. For each positive integer $k$, the minimum cost $k$-vertex connected spanning subgraph problem is a special case of the $k$-$(S,T)$-connectivity problem. We defer precise statements of the problem and of our results to the introduction. For $k=1$, we call the problem the $(S,T)$-connectivity problem. We study three variants of the problem: the standard $(S,T)$-connectivity problem, the relaxed $(S,T)$-connectivity problem, and the unrestricted $(S,T)$-connectivity problem. We give hardness results for these three variants. We design a $2$-approximation algorithm for the standard $(S,T)$-connectivity problem. We design tight approximation algorithms for the relaxed $(S,T)$-connectivity problem and one of its special cases. For any $k$, we give an $O(\log k\log n)$-approximation algorithm, where $n$ denotes the number of vertices. The approximation guarantee almost matches the best approximation guarantee known for the minimum cost $k$-vertex connected spanning subgraph problem which is $O(\log k\log\frac{n}{n-k})$ due to Nutov in 2009.

Various civil and military applications of UAVs, or ground robots, require a set of vehicles to monitor a group of targets. Routing problems naturally arise in this setting where the operators of the vehicles have to plan the paths suitably in order to optimize the use of resources available such as sensors, fuel etc. These vehicles may differ either in their structural (design and dynamics) or functional (sensing) capabilities. This thesis addresses an important routing problem involving two heterogeneous vehicles. As the addressed routing problem is NP-Hard, we develop an approximation algorithm and heuristics to solve the problem. Our approach involves dividing the routing problem into two sub-problems: Partitioning and Sequencing. Partitioning the targets involves finding two distinct sets of targets, each corresponding to one of the vehicles. We then find a sequence in which these targets need to be visited in order to optimize the use of resources to the maximum possible extent. The sequencing problem can be solved either by Christofides algorithm or the Lin-Kernighan Heuristic (LKH). The problem of partitioning is tackled by solving a Linear Program (LP) obtained by relaxing some of the constraints of an Integer Programming (IP) model for the problem. We observe the performance of two LP models for the partitioning. The first LP model is obtained by relaxing only the integrality constraints whereas in the second model relaxes both integrality and degree constraints. The algorithms were implemented in a C++ environment with the help of Concert Technology for CPLEX, and Boost Graph Libraries. The performance of these algorithms was studied for 50 random instances of varying problem sizes. It was found that on an average, the algorithms based on the first LP model provided better (closer to the optimum) solutions as compared to those based on the second LP model. We also observed that for both the LP models, the average quality of solutions given by the heuristics were found to be better ( within 5% of the optimum) than the average quality of solutions obtained from the approximation algorithm (between 30 - 60% of the optimum depending on the problem size).

We study a directed network design problem called the $k$-$(S,T)$-connectivity problem; we design and analyze approximation algorithms and give hardness results. For each positive integer $k$, the minimum cost $k$-vertex connected spanning subgraph problem is a special case of the $k$-$(S,T)$-connectivity problem. We defer precise statements of the problem and of our results to the introduction. For $k=1$, we call the problem the $(S,T)$-connectivity problem. We study three variants of the problem: the standard $(S,T)$-connectivity problem, the relaxed $(S,T)$-connectivity problem, and the unrestricted $(S,T)$-connectivity problem. We give hardness results for these three variants. We design a $2$-approximation algorithm for the standard $(S,T)$-connectivity problem. We design tight approximation algorithms for the relaxed $(S,T)$-connectivity problem and one of its special cases. For any $k$, we give an $O(\log k\log n)$-approximation algorithm, where $n$ denotes the number of vertices. The approximation guarantee almost matches the best approximation guarantee known for the minimum cost $k$-vertex connected spanning subgraph problem which is $O(\log k\log\frac{n}{n-k})$ due to Nutov in 2009.

The problem of finding the convex hull of a set of points in the plane is one of the fundamental and well-studied problems in Computational Geometry. However, for a set of imprecise points, the convex hull problem has not been thoroughly investigated. By imprecise points, we refer to a region in the plane inside which one point may lie. We are particularly interested in finding a minimum perimeter convex hull of a set of imprecise points, where the imprecise points are modelled as line segments. Currently, the best known algorithm that solves the minimum perimeter convex hull problem has an exponential running time in the worst case. It is still unknown whether this problem is NP-hard. We explore several approximation algorithms for this problem. Finally we propose a constant factor approximation algorithm that runs in O(nlogn) time. / Thesis (Master, Computing) -- Queen's University, 2008-11-28 14:47:15.169