Linear programming (LP) relaxations provide a powerfultechnique to design approximation algorithms for combinatorialoptimization problems. In the first part of the thesis, we studythe metric s-t path Traveling Salesma...
详细信息
Linear programming (LP) relaxations provide a powerfultechnique to design approximation algorithms for combinatorialoptimization problems. In the first part of the thesis, we studythe metric s-t path Traveling Salesman Problem (TSP) via LPrelaxations. We first consider the s-t path graph-TSP, acritical special case of the metric s-t path TSP. We design a newsimple LP-based algorithm for the s-t path graph-TSP that achievesthe best known approximation factor of 1.5. Then, we turn ourattention to the general metric s-t path TSP. [An, Kleinberg, andShmoys, STOC 2012] improved on the long standing 5/3-approximationfactor and presented an algorithm that achieves an approximationfactor of (1+\sqrtapproximation)/2 \approx 1.61803. Later, [Sebo, IPCO 2013]further improved the approximation factor to 8/5. We present asimple, self-contained analysis that unifies both ***, we compare two different LP relaxations of the s-tpath TSP, namely the path version of the Held-Karp LP relaxationfor TSP and a weaker LP relaxation, and we show that both LPs havethe same (fractional) optimal value. Also, we show that the minimumcost of integral solutions of the two LPs are within a factor of3/2 of each other. Furthermore, we prove that a half-integralsolution of the stronger LP relaxation of cost c can be rounded toan integral solution of cost at most 3c/2. Finally, we give aninstance that presents obstructions to two natural methods that aimfor an approximation factor of 3/2. The Sherali-Adams (SA)system and the Lasserre (Las) system are two popularLift-and-Project systems that tighten a given LP relaxation in asystematic way. In the second part of the thesis, we study theAsymmetric Traveling Salesman Problem (ATSP) and unweighted TreeAugmentation Problem, respectively, in the framework of the SAsystem and the Las system. For ATSP, our focus is on negativeresults. For any fixed integer t>=0 and small \epsilon,00 can be any small constant, byanalyzing a combinatorial algorithm. T
As we are currently in the information age, people expect access to information to exist by default. In order to facilitate the communication of knowledge, efficient networks must be built. In particular, the networks...
详细信息
As we are currently in the information age, people expect access to information to exist by default. In order to facilitate the communication of knowledge, efficient networks must be built. In particular, the networks must be built satisfying some con- straints while minimizing cost or time. These constraints often make these problems NP-hard. In this thesis, we investigate two different sets of problems: communicating information quickly and building cheap networks. In the communication problems, the goal is to minimize the number of rounds of communication. In the network design problems the goal is to construct a network of minimum cost. First, we study the communication problem of computing a minimum time sched- ule to spread rumors in a given graph under the telephone, radio, and wireless (also called edge-star) models. In all of these communication models, the communication happens in discrete rounds. In the telephone model, a matching is given every round and matched nodes exchange all their information with each other. In the radio model, any subset of nodes can broadcast in a round but only nodes with a single broad- casting neighbor get a message. If a node has two or more neighbors broadcasting, they receive no messages due to interference. In the wireless model, any subset of nodes can broadcast in a round and a non-broadcasting node can tune to listen to ex- actly one of its neighbors. The various rumor spreading problems assume a message at several or all nodes and that each message must reach some target node or set of nodes. The goal is to deliver all messages to their destinations in a minimum num- ber of rounds. The various problems we study include gossip, multicommodity, and asymmetric multicommodity. In the gossip problem, the goal is to communicate mes- sages from every node to every other node. In multicommodity, pairs of nodes are given must exchange their messages with each other. In asymmetric multicommodity, ordered pairs of nodes are give
Let G = (V, E) be an undirected multi-graph with a special vertex root E V, and where each edge e E E is endowed with a length 1(e) : 0 and a capacity c(e) > 0. For a path P that connects u and v, the transmission ...
详细信息
ISBN:
(纸本)3540230254
Let G = (V, E) be an undirected multi-graph with a special vertex root E V, and where each edge e E E is endowed with a length 1(e) : 0 and a capacity c(e) > 0. For a path P that connects u and v, the transmission time of P is defined as t(P) = Sigma(eis an element ofP) l(e) + max(eis an element ofp) 1/c(e). For a spanning tree T, let P-u,v(T) be the unique u - v path in T. The QUICKEST RADIUS SPANNING TREE PROBLEM is to find a spanning tree T of G such that max(vis an element ofV) t(P-root,v(T)) is minimized. In this paper we present a 2-approximation algorithm for this problem, and show that unless P = NP, there is no approximation algorithm with performance guarantee of 2 - epsilon for any epsilon > 0. The QUICKEST DIAMETER SPANNING TREE PROBLEM is to find a spanning tree T of G such that max(u,vis an element ofV) t(P-u,v(T)) is minimized. We present a 2-approximation to this problem, and prove that unless P = NP there is no approximation algorithm with performance guarantee of 3/2 - epsilon for any epsilon > 0.
One of the most flourishing areas of research in the design and analysis of approximation algorithms has been for facility location problems. In particular, for the metric case of two simple models, the uncapacitated ...
详细信息
RNA interactions are fundamental in many cellular processes, which can involve two or more RNA molecules. Multiple RNA interactions are also believed to be much more complex than pairwise interactions. Recently, multi...
详细信息
Two-stage stochastic optimization is a widely used framework for modeling uncertainty, where we have a probability distribution over possible realizations of the data, called scenarios, and decisions are taken in two ...
详细信息
Two-stage stochastic optimization is a widely used framework for modeling uncertainty, where we have a probability distribution over possible realizations of the data, called scenarios, and decisions are taken in two stages: we take first-stage actions knowing only the underlying distribution and before a scenario is realized, and may take additional second-stage recourse actions after a scenario is realized. The goal is typically to minimize the total expected cost. A common criticism levied at this model is that the underlying probability distribution is itself often imprecise. To address this, an approach that is quite versatile and has gained popularity in the stochastic-optimization literature is the two-stage distributionally robust stochastic model: given a collection D of probability distributions, our goal now is to minimize the maximum expected total cost with respect to a distribution in D. There has been almost no prior work however on developing approximation algorithms for distributionally robust problems where the underlying scenario collection is discrete, as is the case with discrete-optimization problems. We provide frameworks for designing approximation algorithms in such settings when the collection D is a ball around a central distribution, defined relative to two notions of distance between probability distributions: Wasserstein metrics (which include the L_1 metric) and the L_infinity metric. Our frameworks yield efficient algorithms even in settings with an exponential number of scenarios, where the central distribution may only be accessed via a sampling oracle. For distributionally robust optimization under a Wasserstein ball, we first show that one can utilize the sample average approximation (SAA) method (solve the distributionally robust problem with an empirical estimate of the central distribution) to reduce the problem to the case where the central distribution has a polynomial-size support, and is represented explicitly. This follows
In this thesis, we will have discussions on two main topics, max-min allocation and scheduling jobs with precedent constraints on machines with communication delays. New approximation algorithms are given in Chapter 2...
详细信息
In this thesis, we will have discussions on two main topics, max-min allocation and scheduling jobs with precedent constraints on machines with communication delays. New approximation algorithms are given in Chapter 2, 4 and 5, where linear programming plays a fairly important role on algorithm designs, while Chapter 3 contains partial results on the general max-min allocation. The Santa Claus problem is also known as the restricted max-min fair allocation. In this problem, Santa Claus has a set of gifts, and he wants to distribute them among a set of children so that the least happy child is made as happy as possible. Here, the value that a child i has for a present j is of the form pij ∈ {0, pj}. Based on a modification of Haxell’s hypergraph matching argument, a polynomial time algorithm by Annamalai et al. gives a 12.33-approximation. In joint work with Sami Davies and Thomas Rothvoss, a matroid version of the Santa Claus problem is introduced. The algorithm is based on Haxell’s augmenting tree, but with the introduction of the matroid structure. Our result can then be used as a blackbox to obtain a (4 + ε)-approximation for Santa Claus, comparing against a natural, compact LP. A recent work of Cheng and Mao [CM19] also gets the factor (4 + ε). On the second half, we first consider the classic problem of scheduling jobs with precedence constraints on identical machines to minimize makespan, in the presence of communication delays. In this setting, denoted by P | prec, c | Cmax, if two dependent jobs are scheduled on different machines, then at least c units of time must pass between their executions. Despite its relevance to many applications, the best known approximation ratio was O(c), whereas Graham’s greedy list scheduling algorithm already gives a (c + 1)-approximation in that setting. An outstanding open problem in the top-10 list by Schuurman and Woeginger and its recent update by Bansal asks whether there exists a constant-factor approximation algorithm.
In this paper we have shown the utility of the Principal Lattice of Partitions approach to the construction of approximate algorithms for the Min-k-overlap problem. In particular we give an improved performance guaran...
详细信息
The most basic form of the max-sum dispersion problem ( MSD ) is as follows: given n points in R q and an integer k, select a set of k points such that the sum of the pairwise distances within the set is maximal. This...
详细信息
The most basic form of the max-sum dispersion problem ( MSD ) is as follows: given n points in R q and an integer k, select a set of k points such that the sum of the pairwise distances within the set is maximal. This is a prominent diversity problem, with wide applications in web search and information retrieval, where one needs to find a small and diverse representa- tive subset of a large dataset. The problem has recently received a great deal of attention in the computational geometry and operations research communities; and since it is NP-hard, research has focused on efficient heuristics and approximation algorithms. Several classes of distance functions have been considered in the literature. Many of the most common distances used in applications are induced by a norm in a real vector space. The focus of this thesis is on MSD over these geometric instances. We provide for it simple and fast polynomial-time approximation schemes (PTASs), as well as improved constant-factor approximation algorithms. We pay special attention to the class of negative-type distances, a class that includes Euclidean and Manhattan distances, among many others. In order to exploit the properties of this class, we apply several techniques and results from the theory of isometric embeddings. We explore the following variations of the MSD problem: matroid and matroid-intersection constraints, knapsack constraints, and the mixed-objective problem that maximizes a combi- nation of the sum of pairwise distances with a submodular monotone function. In addition to approximation algorithms, we present a core-set for geometric instances of low dimension, and we discuss the efficient implementation of some of our algorithms for massive datasets, using the streaming and distributed models of computation.
Dynamic graph algorithms have seen significant theoretical advancements, but practical evaluations often lag behind. This work bridges the gap between theory and practice by engineering and empirically evaluating rece...
详细信息
暂无评论