No description available.

In this work, we study the problem of clearing contamination spreading through a large network where we model the problem as a graph searching game. The problem can be summarized as constructing a search strategy that will leave the graph clear of any contamination at the end of the searching process in as few steps as possible. We show that this problem is NP-hard even on directed acyclic graphs and provide an efficient approximation algorithm. We experimentally observe the performance of our approximation algorithm in relation to the lower bound on several large online networks including Slashdot, Epinions and Twitter. The experiments reveal that in most cases our algorithm performs near optimally. / Graduate

The capacitated facility location problem is a well known problem in combinatorial optimization and operations research. In it, we are given a set of clients and a set of possible facility locations. Each client has a certain demand that needs to be satisfied from open facilities, without exceeding their capacity. Whenever we open a facility we incur in a corresponding opening cost. Whenever demand is served, we incur in an assignment cost; depending on the distance the demand travels. The goal is to open a set of facilities that satisfy all demands while minimizing the total opening and assignment costs. In this thesis, we present two novel LP-based approximation algorithms for the capacitated facility location problem. The first algorithm is based on LP-rounding techniques, and is designed for the special case of the capacitated facility location problem where capacities are uniform and assignment costs are given by a tree metric. The second algorithm follows a primal-dual approach, and works for the general case. For both algorithms, we obtain an approximation guarantee that is linear on the size of the problem. To the best of our knowledge, there are no LP-based algorithms known, for the type of instances that we focus on, that achieve a better performance.

This thesis involves the study of a range of geometric covering and piercing problems, where the unifying thread is approximation using disks. While some of the problems addressed in this work are solved exactly with polynomial time algorithms, many problems are shown to be at least NP-hard. For the latter, approximation algorithms are the best that we can do in polynomial time assuming that P is not equal to NP. One of the best known problems involving unit disks is the Discrete Unit Disk Cover (DUDC) problem, in which the input consists of a set of points P and a set of unit disks in the plane D, and the objective is to compute a subset of the disks of minimum cardinality which covers all of the points. Another perspective on the problem is to consider the centre points (denoted Q) of the disks D as an approximating set of points for P. An optimal solution to DUDC provides a minimal cardinality subset Q*, a subset of Q, so that each point in P is within unit distance of a point in Q*. In order to approximate the general DUDC problem, we also examine several restricted variants. In the Line-Separable Discrete Unit Disk Cover (LSDUDC) problem, P and Q are separated by a line in the plane. We write that l^- is the half-plane defined by l containing P, and l^+ is the half-plane containing Q. LSDUDC may be solved exactly in O(m^2n) time using a greedy algorithm. We augment this result by describing a 2-approximate solution for the Assisted LSDUDC problem, where the union of all disks centred in l^+ covers all points in P, but we consider using disks centred in l^- as well to try to improve the solution. Next, we describe the Within-Strip Discrete Unit Disk Cover (WSDUDC) problem, where P and Q are confined to a strip of the plane of height h. We show that this problem is NP-complete, and we provide a range of approximation algorithms for the problem with trade-offs between the approximation factor and running time. We outline approximation algorithms for the general DUDC problem which make use of the algorithms for LSDUDC and WSDUDC. These results provide the fastest known approximation algorithms for DUDC. As with the WSDUDC results, we present a set of algorithms in which better approximation factors may be had at the expense of greater running time, ranging from a 15-approximate algorithm which runs in O(mn + m log m + n log n) time to a 18-approximate algorithm which runs in O(m^6n+n log n) time. The next problems that we study are Hausdorff Core problems. These problems accept an input polygon P, and we seek a convex polygon Q which is fully contained in P and minimizes the Hausdorff distance between P and Q. Interestingly, we show that this problem may be reduced to that of computing the minimum radius of disk, call it k_opt, so that a convex polygon Q contained in P intersects all disks of radius k_opt centred on the vertices of P. We begin by describing a polynomial time algorithm for the simple case where P has only a single reflex vertex. On general polygons, we provide a parameterized algorithm which performs a parametric search on the possible values of k_opt. The solution to the decision version of the problem, i.e. determining whether there exists a Hausdorff Core for P given k_opt, requires some novel insights. We also describe an FPTAS for the decision version of the Hausdorff Core problem. Finally, we study Generalized Minimum Spanning Tree (GMST) problems, where the input consists of imprecise vertices, and the objective is to select a single point from each imprecise vertex in order to optimize the weight of the MST over the points. In keeping with one of the themes of the thesis, we begin by using disks as the imprecise vertices. We show that the minimization and maximization versions of this problem are NP-hard, and we describe some parameterized and approximation algorithms. Finally, we look at the case where the imprecise vertices consist of just two vertices each, and we show that the minimization version of the problem (which we call 2-GMST) remains NP-hard, even in the plane. We also provide an algorithm to solve the 2-GMST problem exactly if the combinatorial structure of the optimal solution is known. We identify a number of open problems in this thesis that are worthy of further study. Among them: Is the Assisted LSDUDC problem NP-complete? Can the WSDUDC results be used to obtain an improved PTAS for DUDC? Are there classes of polygons for which the determination of the Hausdorff Core is easy? Is there a PTAS for the maximum weight GMST problem on (unit) disks? Is there a combinatorial approximation algorithm for the 2-GMST problem (particularly with an approximation factor under 4)?

In this doctoral thesis, four questions related to computational geometry are considered. The first is an extremal combinatorics question regarding triangles with vertices taken from a set of n points in convex position. More precisely, two such triangles can exhibit eight distinct configurations and, for each subset of these configurations, we are interested in the asymptotics of how many triangles one can have while avoiding configurations in the subset (as a function of n). For most of these subsets, we answer this question optimally up to a logarithmic factor in the form of several Turán-type theorems. The answers for the remaining few were in turn tied to that of a long-standing open problem which appeared in the literature in the contexts of monotone matrices, tripod packing and 2-comparable sets. The second problem, called Line Segment Covering (LSC), is about covering the cells of an arrangement of line segments with these line segments, where a segment covers the cells it is incident to. Recently, a PTAS, an APX -hardness proof and a FPT algorithm for variants of this problem have been shown. This paper and a new slight generalization of one of its results is included as a chapter. The third problem has been posed in the Sixth Annual Workshop on Geometry and Graphs and concerns the design of road networks to minimize the maximum travel time between two point sets in the plane. Traveling outside the roads costs more time per unit of distance than traveling on the roads and the total length of the roads can not exceed a budget. When the point sets are the opposing sides of a unit square and the budget is at most √2, we were able to come up with a few network designs that cover all possible cases and are provably optimal. Furthermore, when both point sets are the boundary of a unit circle, we managed to disprove the natural conjecture that a concentric circle is an optimal design. Finally, we consider collision-avoiding schedules of unit-velocity axis-aligned trains departing and arriving from points in the integer lattice. We prove a few surprising results on the existence of constant upper bounds on the maximum delay that are independent of the train network. In particular, these upper bounds are shown to always exist in two dimensions and to exist in three dimensions for unit-length trains. We also showed computationally that, for several scenarios, these upper bounds are tight.

The <i>mixed postman problem</i> consists of finding a minimum cost tour of a mixed graph <i>M</i> = (<i>V</i>,<i>E</i>,<i>A</i>) traversing all its edges and arcs at least once. We prove that two well-known linear programming relaxations of this problem are equivalent. The <i>extra cost</i> of a mixed postman tour <i>T</i> is the cost of <i>T</i> minus the cost of the edges and arcs of <i>M</i>. We prove that it is <i>NP</i>-hard to approximate the minimum extra cost of a mixed postman tour. A related problem, known as the <i>windy postman problem</i>, consists of finding a minimum cost tour of an undirected graph <i>G</i>=(<i>V</i>,<i>E</i>) traversing all its edges at least once, where the cost of an edge depends on the direction of traversal. We say that <i>G</i> is <i>windy postman perfect</i> if a certain <i>windy postman polyhedron O</i> (<i>G</i>) is integral. We prove that series-parallel undirected graphs are windy postman perfect, therefore solving a conjecture of Win. Given a mixed graph <i>M</i> = (<i>V</i>,<i>E</i>,<i>A</i>) and a subset <i>R</i> &#8838; <i>E</i> &#8746; <i>A</i>, we say that a mixed postman tour of <i>M</i> is <i>restricted</i> if it traverses the elements of <i>R</i> exactly once. The <i>restricted mixed postman problem</i> consists of finding a minimum cost restricted tour. We prove that this problem is <i>NP</i>-hard even if <i>R</i>=<i>A</i> and we restrict <i>M</i> to be planar, hence solving a conjecture of Veerasamy. We also prove that it is <i>NP</i>-complete to decide whether there exists a restricted tour even if <i>R</i>=<i>E</i> and we restrict <i>M</i> to be planar. The <i>edges postman problem</i> is the special case of the restricted mixed postman problem when <i>R</i>=<i>A</i>. We give a new class of valid inequalities for this problem. We introduce a relaxation of this problem, called the <i>b-join problem</i>, that can be solved in polynomial time. We give an algorithm which is simultaneously a 4/3-approximation algorithm for the edges postman problem, and a 2-approximation algorithm for the extra cost of a tour. The <i>arcs postman problem</i> is the special case of the restricted mixed postman problem when <i>R</i>=<i>E</i>. We introduce a class of necessary conditions for <i>M</i> to have an arcs postman tour, and we give a polynomial-time algorithm to decide whether one of these conditions holds. We give linear programming formulations of this problem for mixed graphs arising from windy postman perfect graphs, and mixed graphs whose arcs form a forest.

Approximation algorithms employing Monte Carlo methods, across application domains, often require as a subroutine the estimation of the mean of a random variable with support on [0,1]. One wishes to estimate this mean to within a user-specified error, using as few samples from the simulated distribution as possible. In the case that the mean being estimated is small, one is then interested in controlling the relative error of the estimate. We introduce a new (epsilon, delta) relative error approximation scheme for [0,1] random variables and provide a comparison of this algorithm's performance to that of an existing approximation scheme, both establishing theoretical bounds on the expected number of samples required by the two algorithms and empirically comparing the samples used when the algorithms are employed for a particular application.

In this thesis, a discrete Markov chain model for analyzing memory interference in multiprocessors, is presented.

Mathematical modeling is a central component of operations research. Most of the academic research in our field focuses on developing algorithmic tools for solving various mathematical problems arising from our models. However, our procedure for selecting the best model to use in any particular application is ad hoc. This dissertation seeks to rigorously quantify the trade-offs between various design criteria in model construction through a series of case studies. The hope is that a better understanding of the pros and cons of different models (for the same application) can guide and improve the model selection process. In this dissertation, we focus on two broad types of trade-offs. The first type arises naturally in mechanism or market design, a discipline that focuses on developing optimization models for complex multi-agent systems. Such systems may require satisfying multiple objectives that are potentially in conflict with one another. Hence, finding a solution that simultaneously satisfies several design requirements is challenging. The second type addresses the dynamics between model complexity and computational tractability in the context of approximation algorithms for some discrete optimization problems. The need to study this type of trade-offs is motivated by certain industry problems where the goal is to obtain the best solution within a reasonable time frame. Hence, being able to quantify and compare the degree of sub-optimality of the solution obtained under different models is helpful. Chapters 2-5 of the dissertation focus on trade-offs of the first type and Chapters 6-7 the second type.

本论文着重研究了带有Lp模球约束以及二次约束的多项式优化问题的计算复杂度以及关于此类问题的近似算法。在本论文中，利用张量对称化的技巧，我们首次证明了当P∈ [2 ，∞] ，任意高阶的带有Lp模球约束的多项式优化问题均为NP 困难。借助模的对偶性质，我们将这类优化问题转化为求解凸体半径的问题，从而使得我们获得了之前研究所无法使用的算法工具。具体来说，利用计算凸几何的算法工具，对于Lp模球约束的多项式优化问题，我们得到了近似比为[附圖]的确定性多项式时间近似算法，其中d为目标多项式的阶次， n 为问题的维度。使用随机算法，我们将近似比进一步提高为此类问题的己知最优值。[附圖]。此外，我们发展了计算凸几何当中对于凸体半径的计算方法，从而设计出了一种对二次约束多项式优化问题近似比为[附圖]的近似算法，其中m为问题的约束个数。我们的结果涵盖并提高了之前关于此类问题的研究结果。我们相信在本论文中使用的新的算法工具，将在今后的多项式优化问题研究中得到更广泛的应用。 / In this thesis, we present polynomial time approximation algorithms for solving various homogeneous polynomial optimization problems and their multilinear relaxations. Specifically, for the problems with Lp ball constraint, where P∈ [2 ，∞], by reducing them to that of determining the Lq-diameter of certain convex body, we show that they can be approximated to within a factor of [with formula] in deterministic polynomial time, where q = p=(p - 1) is the conjugate of p, n is the number of variables, and d is the degree of the polynomial. We further show that with the help of randomization, the approximation guarantee can be improved to [with formula], which is independent of p and is currently the best for the aforementioned problems. Moreover, we extend the argument of deterministic algorithm mentioned above to solve the quadratically constrained polynomial optimization problems. In particular, for any intersection of ellipsoids K, we can, in polynomial time, construct a random polytope P, which satisfies [with formula]. Then, by reducing the problem to that of evaluating the maximum polytopal norm [with formula] induced by P, over certain convex body, we can approximate the quadratically constrained problem within a factor of [with formula] in polynomial time. Our results unify and generalize those in the literature, which focus either on the quadratic case or the case where [with formula]. We believe that the wide array of tools used in this thesis will have further applications in the study of polynomial optimization problems. / Detailed summary in vernacular field only. / Hou, Ke. / On title page "p" is subscript. / Thesis (Ph.D.) Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 106-111). / Abstracts also in Chinese.