In this thesis, I survey 11 approximation algorithms for unweighted set cover problem. I have also implemented the three algorithms and created a software library that stores the code I have written. The algorithms I survey are: 1. Johnson's standard greedy; 2. f-frequency greedy; 3. Goldsmidt, Hochbaum and Yu's modified greedy; 4. Halldorsson's local optimization; 5. Dur and Furer semi local optimization; 6. Asaf Levin's improvement to Dur and Furer; 7. Simple rounding; 8. Randomized rounding; 9. LP duality; 10. Primal-dual schema; and 11. Network flow technique. Most of the algorithms surveyed are refinements of standard greedy algorithm.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19864号 / 情博第615号 / 新制||情||107(附属図書館) / 32900 / 京都大学大学院情報学研究科通信情報システム専攻 / (主査)教授 岩間 一雄, 教授 永持 仁, 教授 五十嵐 淳 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DGAM

京都大学 / 新制・課程博士 / 博士(理学) / 甲第24388号 / 理博第4887号 / 新制||理||1699(附属図書館) / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)教授 牧野 和久, 教授 並河 良典, 教授 長谷川 真人 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DGAM

The presence of substitution among multiple similar products plays an important role in inventory management. It has been observed in the literature that incorporating the impact of substitution among products can substantially improve the profit and reduce the understock or overstock risk. This thesis focuses on exploring and exploiting the impact of substitution on inventory management problems by theoretically analyzing mathematical models and developing efficient solution approaches. To that end, we address four problems. In the first problem, we study different pricing strategies and the role of substitution for new and remanufactured products. Our work presents a two-stage model for an original equipment manufacturer (OEM) in this regard. A closed-form one-to-one mapping of product designs onto the optimal product strategies is developed, which provides useful information for the retailer. Our second problem is a multi-product newsvendor problem with customer-driven demand substitution. We completely characterize the optimal order policy when the demand is known and reformulate this nonconvex problem as a binary quadratic program. When the demand is stochastic, we formulate the problem as a two-stage stochastic program with mixed integer recourse, derive several necessary optimality conditions, prove the submodularity of the profit function, develop polynomial-time approximation algorithms, and show their performance guarantees. Our numerical investigation demonstrates the effectiveness of the proposed algorithms and, furthermore, reveals several useful findings and managerial insights. In the third problem, we study a robust multi-product newsvendor model with substitution (R-MNMS), where both demand and substitution rates are uncertain and are subject to cardinality-constrained uncertainty set. We show that for given order quantities, computing the worst-case total profit, in general, is NP-hard, and therefore, address three special cases for which we provide closed-form solutions. In practice, placing an order might incur a fixed cost. Motivated by this fact, our fourth problem extends the R-MNMS by incorporating fixed cost (denoted as R-MNMSF) and develop efficient approaches for its solution. In particular, we propose an exact branch-and-cut algorithm to solve small- or medium-sized problem instances of the R-MNMSF, and for large-scale problem instances, we develop an approximation algorithm. We further study the effects of the fixed cost and show how to tune the parameters of the uncertainty set. / Doctor of Philosophy / In a multi-product supply chain, the substitution of products arises if a customer's first-choice product is out-of-stock, and she/he have to turn to buy another similar product. It has been shown in the literature that the presence of product substitution reduces the assortment size, and thus, brings in more profit. %and reduce the inventory level. However, how to quantitatively study and analyze substitution effects has not been addressed in the literature. This thesis fills this gap by developing and analyzing the profit model, and therefore, providing judicious decisions for the retailer to make in order to maximize their profit. In our first problem, we consider substitution between new products and remanufactured products. We provide closed-form solutions, and a mapping that can help the retailer in choosing optimal prices and end-of-life options given a certain product design. In our second problem, we study multi-product newsvendor model with substitution. We first show that, when the probability distribution of customers' demand is known, we can tightly approximate the proposed model as a stochastic integer program under discrete support. Next, we provide effective solution approaches to solve the multi-product newsvendor model with substitution. In practice, typically, there is a limited information available on the customers' demand or substitution rates, and therefore, for our third problem, we study a robust model with a cardinality uncertainty set to account for these stochastic demand and substitution rates. We give closed-form solutions for the following three special cases: (1) there are only two products, (2) there is no substitution among different products, and (3) the budget of uncertainty is equal to the number of products. Finally, similar to many inventory management problems, we include a fixed cost in the robust model and develop efficient approaches for its solution. The numerical study demonstrates the effectiveness of the proposed methods and the robustness of our model. We further illustrate the effects of the fixed cost and how to tune the parameters of the uncertainty set.

Piercing problems arise often in facility location, which is a well-studied area of computational geometry. The general form of the piercing problem discussed in this dissertation asks for the minimum number of facilities for a set of given rectangular demand regions such that each region has at least one facility located within it. It has been shown that even if all regions are uniform sized squares, the problem is NP-hard. Therefore we concentrate on approximation algorithms for the problem. As the known approximation ratio for arbitrarily sized rectangles is poor, we restrict our effort to designing approximation algorithms for unit-height rectangles. Our e-approximation scheme requires <I>n</I>^{<I>O</I>(1/&epsilon;??)} time. We also consider the problem with restrictions like bounding the depth of a point and the width of the rectangles. The approximation schemes for these two cases take <I>n</I>^{<I>O</I>(1/&epsilon;)} time. We also show how to maintain a factor 2 approximation of the piercing set in <I>O</I>(log <I>n</I>) amortized time in an insertion-only scenario.

Geometric packing problems are NP-complete problems that arise in VLSI design. In this thesis, we present two novel algorithms using dynamic programming to compute exactly the maximum number of k x k squares of unit size that can be packed without overlap into a given n x m grid. The first algorithm was implemented and ran successfully on problems of large input up to 1,000,000 nodes for different values. A heuristic based on the second algorithm is implemented. This heuristic is fast in practice, but may not always be giving optimal times in theory. However, over a wide range of random data this version of the algorithm is giving very good solutions very fast and runs on problems of up to 100,000,000 nodes in a grid and different ranges for the variables. It is also shown that this version of algorithm is clearly superior to the first algorithm and has shown to be very efficient in practice.

L'analyse des techniques d'approximation est centrale en géométrie algorithmique, pour des raisons pratiques comme théoriques. Dans cette thèse nous traitons de l'échantillonnage des structures géométriques et des algorithmes d'approximation géométriques en optimisation combinatoire. La première partie est consacrée à la combinatoire des hypergraphes. Nous débutons par les problèmes de packing, dont des extensions d'un lemme de Haussler, particulièrement le lemme dit de Shallow packing, pour lequel nous donnons aussi un minorant optimal, conjecturé mais pas établi dans les travaux antérieurs. Puis nous appliquons ledit lemme, avec la méthode de partition polynomiale récemment introduite, à l'étude d'un analogue combinatoire des régions de Macbeath de la géométrie convexe : les M-réseaux, pour lesquels nous unifions les résultats d'existence et majorations existants, et donnons aussi quelques minorants. Nous illustrons leur relation aux epsilon-réseaux, structures incontournables en géométrie combinatoire et algorithmique, notamment en observant que les majorants de Chan et al. (SODA 2012) ou Varadarajan (STOC 2010) pour les epsilon-réseaux (uniformes) découlent directement de nos résultats sur les M-réseaux. La deuxième partie traite des techniques de recherche locale appliquées aux restrictions géométriques de problèmes classiques d'optimisation combinatoire. En dix ans, ces techniques ont produit les premiers schémas d'approximation en temps polynomial pour divers problèmes tels que celui de calculer un plus petit ensemble intersectant pour un ensemble de disques donnés en entrée parmi un ensemble de points donnés en entrée. En fait, il a été montré que pour de nombreux tels problèmes, la recherche locale de rayon Θ (1/epsilon²) donne une (1 + epsilon)-approximation en temps n^{O(1/epsilon²)}. Savoir si l'exposant de n pouvait être ramené à o (1/epsilon²) demeurait une question ouverte. Nous répondons par la négative : la garantie d'approximation de la recherche locale n'est améliorable pour aucun desdits problèmes / The analysis of approximation techniques is a key topic in computational geometry, both for practical and theoretical reasons. In this thesis we discuss sampling tools for geometric structures and geometric approximation algorithms in combinatorial optimization. Part I focuses on the combinatorics of geometric set systems. We start by discussing packing problems in set systems, including extensions of a lemma of Haussler, mainly the so-called shallow packing lemma. For said lemma we also give an optimal lower bound that had been conjectured but not established in previous work on the topic. Then we use this lemma, together with the recently introduced polynomial partitioning technique, to study a combinatorial analogue of the Macbeath regions from convex geometry: Mnets, for which we unify previous existence results and upper bounds, and also give some lower bounds. We highlight their connection with epsilon-nets, staples of computational and combinatorial geometry, for example by observing that the unweighted epsilon-net bound of Chan et al. (SODA 2012) or Varadarajan (STOC 2010) follows directly from our results on Mnets. Part II deals with local-search techniques applied to geometric restrictions of classical combinatorial optimization problems. Over the last ten years such techniques have produced the first polynomial-time approximation schemes for various problems, such as that of computing a minimum-sized hitting set for a collection of input disks from a set of input points. In fact, it was shown that for many of these problems, local search with radius Θ(1/epsilon²) gives a (1 + epsilon)-approximation with running time n^{O(1/epsilon²)}. However the question of whether the exponent of n could be decreased to o(1/epsilon²) was left open. We answer it in the negative: the approximation guarantee of local search cannot be improved for any of these problems. The key ingredient is a new lower bound on locally expanding planar graphs, which is then used to show the impossibility results

Esta tese teve como objetivo estudar problemas cinéticos de clustering, ou seja, problemas de clustering nos quais os objetos se movimentam. O trabalho se concentrou no caso unidimensional, em que os objetos são pontos se movendo na reta real. Diversas variantes desse caso foram abordadas. Em termos do movimento, consideramos o caso em que cada ponto se move com uma velocidade constante num dado intervalo de tempo, o caso em que os pontos se movem arbitrariamente e temos apenas as suas posições em instantes discretos de tempo, o caso em que os pontos se movem com uma velocidade aleatória em que se conhece apenas o valor esperado da velocidade, e o caso em que, dada uma partição do intervalo de tempo, os pontos se movem com velocidades constantes em cada subintervalo. Em termos do tipo de clustering buscado, nos concentramos no caso em que o número de clusters é um dado do problema e consideramos diferentes medidas de qualidade para o clustering. Duas delas são tradicionais para problemas de clustering: a soma dos diâmetros dos clusters e o diâmetro máximo de um cluster. A terceira medida considerada leva em conta a característica cinética do problema, e permite, de uma maneira controlada, que o clustering mude com o tempo. Para cada uma das variantes do problema, são apresentados algoritmos, exatos ou de aproximação, alguns resultados de complexidade obtidos, e questões que ficaram em aberto. / This work aimed to study kinetic problems of clustering, i.e., clustering problems in which the objects are moving. The study focused on the unidimensional case, where the objects are points moving on the real line. Several variants of this case have been discussed. Regarding the movement, we consider the case where each point moves at a constant velocity in a given time interval, the case where the points move arbitrarily and we only know their positions in discrete time instants, the case where the points move at a random velocity in which only the expected value of the velocity is known, and the case where, given a partition of the time interval, the points move at constant velocities in each sub-interval. Regarding the kind of clustering sought, we focused in the case where the number of clusters is part of the input of the problem and we consider different measures of quality for the clustering. Two of them are traditional measures for clustering problems: the sum of the cluster diameters and the maximum diameter of a cluster. The third measure considered takes into account the kinetic characteristic of the problem, and allows, in a controlled manner, that a cluster change along time. For each of the variants of the problem, we present algorithms, exact or approximation, some obtained complexity results, and open questions.

Neste projeto estudamos algoritmos de aproximação para o problema da árvore de Steiner com coleta de prêmios. Trata-se de uma generalização do problema da árvore de Steiner, onde é dado um grafo com custos positivos nas arestas e penalidades positivas nos vértices. O objetivo é encontrar uma subárvore do grafo que minimize a soma dos custos das arestas mais a soma das penalidades dos vértices que não pertencem à subárvore. Em 2009, os autores Archer, Bateni, Hajiaghayi e Karloff obtiveram pela primeira vez um algoritmo com fator de aproximação estritamente menor do que 2. Além de analisarmos este algoritmo, estudamos também a implementação de algoritmos 2-aproximação para o problema da árvore de Steiner e da árvore de Steiner com coleta de prêmios. / In this project we analyze approximation algorithms for the prize-collecting Steiner tree problem. This is a generalization of the Steiner tree problem, in which it is given a graph with positive costs in edges and positive penalties in vertices. The goal is to find a subtree of the graph that minimizes the sum of costs of edges plus the sum of the penalties of the vertices that don\'t belong to the subtree. In 2009, the authors Archer, Bateni, Hajiaghayi e Karloff described, for the first time an algorithm with approximation factor strictly less than 2. Besides analyzing this algorithm, we also study the implementation of 2-approximation algorithms to the Steiner tree problem and prize-collecting Steiner tree problem.

Esta tese teve como objetivo estudar problemas cinéticos de clustering, ou seja, problemas de clustering nos quais os objetos se movimentam. O trabalho se concentrou no caso unidimensional, em que os objetos são pontos se movendo na reta real. Diversas variantes desse caso foram abordadas. Em termos do movimento, consideramos o caso em que cada ponto se move com uma velocidade constante num dado intervalo de tempo, o caso em que os pontos se movem arbitrariamente e temos apenas as suas posições em instantes discretos de tempo, o caso em que os pontos se movem com uma velocidade aleatória em que se conhece apenas o valor esperado da velocidade, e o caso em que, dada uma partição do intervalo de tempo, os pontos se movem com velocidades constantes em cada subintervalo. Em termos do tipo de clustering buscado, nos concentramos no caso em que o número de clusters é um dado do problema e consideramos diferentes medidas de qualidade para o clustering. Duas delas são tradicionais para problemas de clustering: a soma dos diâmetros dos clusters e o diâmetro máximo de um cluster. A terceira medida considerada leva em conta a característica cinética do problema, e permite, de uma maneira controlada, que o clustering mude com o tempo. Para cada uma das variantes do problema, são apresentados algoritmos, exatos ou de aproximação, alguns resultados de complexidade obtidos, e questões que ficaram em aberto. / This work aimed to study kinetic problems of clustering, i.e., clustering problems in which the objects are moving. The study focused on the unidimensional case, where the objects are points moving on the real line. Several variants of this case have been discussed. Regarding the movement, we consider the case where each point moves at a constant velocity in a given time interval, the case where the points move arbitrarily and we only know their positions in discrete time instants, the case where the points move at a random velocity in which only the expected value of the velocity is known, and the case where, given a partition of the time interval, the points move at constant velocities in each sub-interval. Regarding the kind of clustering sought, we focused in the case where the number of clusters is part of the input of the problem and we consider different measures of quality for the clustering. Two of them are traditional measures for clustering problems: the sum of the cluster diameters and the maximum diameter of a cluster. The third measure considered takes into account the kinetic characteristic of the problem, and allows, in a controlled manner, that a cluster change along time. For each of the variants of the problem, we present algorithms, exact or approximation, some obtained complexity results, and open questions.