Orientador: Orlando Lee / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-27T12:18:11Z (GMT). No. of bitstreams: 1 SanFelice_MarioCesar_D.pdf: 1457706 bytes, checksum: 4813f4ed44c52462656d56537d73d5dc (MD5) Previous issue date: 2015 / Resumo: Nesta tese estudamos problemas online das famílias de localização de instalações e de Steiner, através da abordagem de análise competitiva. O objetivo nestes problemas é construir uma rede de custo mínimo para atender a uma determinada demanda. Nós apresentamos resultados conhecidos para o problema Online da Localização de Instalações (OFL), o problema Online da Árvore de Steiner (OST) e o problema Online Single-Source Rent-or-Buy (OSRoB). O OFL consiste em atender a um conjunto de clientes, através da abertura de algumas instalações e da conexão de cada cliente com uma instalação aberta. O OST tem por objetivo conectar um conjunto de terminais utilizando uma árvore, que pode conter vértices não terminais, chamados vértices de Steiner. O OSRoB é uma versão rent-or-buy do OST, onde todos os terminais devem ser conectados a um nó especial chamado raíz. Os algoritmos e técnicas que apresentamos para estes problemas são importantes no desenvolvimento dos nossos algoritmos para os problemas que consideramos. Apresentamos novos resultados para o problema Online da Localização de Instalações com Coleta de Prêmios (OPFL), o problema Online da Árvore Estrela de Steiner (OSTS), e o problema Online da Localização de Instalações Conectadas (OCFL). O OPFL é uma generalização do OFL, em que alguns clientes podem ficar desconectados mediante o pagamento de penalidades. O OSTS é uma variante do OST, em que os vértices possuem custos não negativos. O OCFL é uma combinação do OFL e do OST, em que um conjunto de clientes precisa ser atendido através da abertura de algumas instalações, da conexão de cada cliente com uma instalação aberta, e da construção de uma árvore, mais custosa, que conecta as instalações abertas / Abstract: In this thesis we study online problems from the facility location and Steiner families, through the point of view of competitive analysis. The goal in these problems is to build a minimum cost network to attend a certain demand. We present known results for the Online Facility Location problem (OFL), the Online Steiner Tree problem (OST) and the Online Single-Source Rent-or-Buy problem (OSRoB). The OFL consists of serving a set of clients by opening some facilities and by connecting each client to a facility. The OST aims to connect a set of terminals in order to create a tree network, that may contain nonterminals, called Steiner nodes. The OSRoB is a rent-or-buy version of the OST, in which all terminals must be connected to a special node called root. The algorithms and techniques that we present for these problems play an important role in the design of our algorithms for the problems we consider. We present new results for the Online Prize-Collecting Facility Location problem (OPFL), the Online Steiner Tree Star problem (OSTS), and the Online Connected Facility Location problem (OCFL). The OPFL is a generalization of the OFL, in which some clients may be left unconnected by paying a penalty. The OSTS is a variant of the OST, in which the nodes have non-negative costs. The OCFL is a combination of the OFL and the OST, in which a set of clients needs to be served by opening some facilities, by connecting each client to a facility, and by creating a more expensive tree network that connects the open facilities / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

O Problema de Minimização do Número Máximo de Pilhas Abertas (MOSP, do inglês minimization of open stacks problem) é um problema de otimização combinatória da família NP-Difícil que vem recebendo grande atenção na literatura especializada. Este trabalho apresenta novas contribuições em termos de modelos e técnicas de resolução para o problema. A primeira parte deste trabalho lidou com modelos matemáticos, sendo analisados os modelos existentes que se baseiam em programação inteira mista. Variações de um modelo da literatura foram propostas, com o objetivo de tentar diminuir o tempo de execução necessário para se obter uma solução exata com a utilização de pacotes comerciais. Os resultados mostraram que as propostas são capazes de acelerar a solução de algumas classes de instâncias mas, que de maneira geral, métodos baseados em relaxação linear encontram dificuldade em provar a otimalidade devido à baixa qualidade dos limitantes inferiores. Uma outra contribuição deste trabalho foi o desenvolvimento de um modelo conjunto para o problema MOSP e para o problema de minimização da duração de pedidos (MORP, do inglês minimization of order spread problem). Este modelo propõe um framework unificado em que os dois problemas podem ser resolvidos ao mesmo tempo, tendo suas funções objetivo individuais ponderadas através de pesos definidos pelo usuário. A segunda parte do trabalho voltou-se para o desenvolvimento de métodos heurísticos para o MOSP. Duas estratégias de solução foram desenvolvidas. O primeiro método propõe uma transformação heurística entre o problema MOSP e o clássico problema do caixeiro viajente (TSP, do inglês traveling salesman problem). A partir de uma representação em grafo do MOSP, o TSP é definido por meio de uma regra de atribuição de distâncias baseadas nos graus dos nós. Nos testes computacionais, a estratégia proposta mostrou-se eficiente em relação às heurísticas específicas para o MOSP, obtendo a solução ótima do MOSP em 80,42% das instâncias testadas e sendo competitiva em termos de tempo computacional com algumas das melhores heurísticas da literatura. O segundo método heurístico proposto utilizou a ideia de decomposição. De fato, neste método, um corte no grafo associado ao problema original divide-o em problemas menores, que são resolvidos. A solução global é obtida através da junção das soluções dos subproblemas e, em alguns casos, é possível demonstrar a otimalidade da solução obtida. Testes computacionais indicam a validade da proposta e apontam caminhos para pesquisas futuras / The minimization of open stacks problem (MOSP) is a well known NP-hard combinatorial optimization problem that has been extensively discussed in the specialized literature. This study presents some new contributions in terms of models and solution methods for this problem. The first part of this thesis dealt with mathematical models. The existing mixedinteger models have been analyzed and variants of a well known model have been proposed, with the goal of reducing the time needed by commercial packages to obtain proved-optimal solutions. The results of computational tests on a widely used set of instances have indicated that the modifications proposed are able to reduce the time needed to obtain optimal solutions for some classes of instances. Nevertheless, a conclusion has been the fact that mixed-integer programming models have difficulty in obtaining convergence due to the low quality linear relaxation bounds. Another contribution of this thesis is the proposal of a single model that is able to deal with both the MOSP and with the Minimization of Order Spread Problem (MORP). This unified framework allows both problems to be jointly solved, by using a weighted objective function that included both original objectives. The second part of this thesis dealt with the development of heuristic strategies. Two solution strategies have been proposed. The first method proposes a heuristic conversion between MOSP and Traveling Salesman Problem (TSP) instances. This conversion relies the assignment distances to the TSP instance based on the degree of the vertices of the associated MOSP graph. Computational tests have shown that the proposed methodology is efficient, both in terms of solution quality (optimal solutions were obtained for 80.42% of the tested instances) and computational effort. The second method uses a decomposition idea. A cut is made in the graph associated with the original MOSP problem, yielding two smaller problems, which are solved. In some cases, the obtained combined solution can be prover optimal. Computational tests have shown the validity of the proposal and indicate new research opportunities

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.

Given a graph, a matching is a set of vertex-disjoint edges. Graph matchings have been well studied, since they play a fundamental role in algorithmic theory as well as motivate many practical applications. Of particular interest is the problem of finding a maximum cardinality matching of a graph. Also of interest is the weighted variant: the problem of computing a minimum-cost maximum cardinality matching. For an arbitrary graph with m edges and n vertices, there are known, long-standing combinatorial algorithms that compute a maximum cardinality matching in O(m\sqrt{n}) time. For graphs with non-negative integer edge costs at most C, it is known how to compute a minimum-cost maximum cardinality matching in roughly O(m\sqrt{n} log(nC)) time using combinatorial methods. While non-combinatorial methods exist, they are generally impractical and not well understood due to their complexity. As a result, there is great interest in obtaining faster matching algorithms that are purely combinatorial in nature. Improving existing combinatorial algorithms for arbitrary graphs is considered to be a very difficult problem. To make the problem more approachable, it is desirable to make some additional assumptions about the graph. For our work, we make two such assumptions. First, we assume the graph is bipartite. Second, we assume that the graph has a small balanced separator, meaning it is possible to split the graph into two roughly equal-size components by removing a relatively small portion of the graph. Several well-studied classes of graphs have separator-like properties, including planar graphs, minor-free graphs, and geometric graphs. For such graphs, we describe a framework, a general set of techniques for designing efficient algorithms. We demonstrate this framework by applying it to yield polynomial-factor improvements for several open-problems in bipartite matching. / Doctor of Philosophy / Assume we are given a list of objects, and a list of compatible pairs of these objects. A matching consists of a chosen subset of these compatible pairs, where each object participates in at most one chosen pair. For any chosen pair of objects, we say the these two objects are matched. Generally, we seek to maximize the number of compatible matches. A maximum cardinality matching is a matching with the largest possible size. In many cases, there are multiple options for maximizing the number of compatible pairings. While maximizing the size of the matching is often the primary concern, one may also seek to minimize the cost of the matching. This is known as the minimum-cost maximum-cardinality matching problem. These two matching problems have been well studied, since they play a fundamental role in algorithmic theory as well as motivate many practical applications. Our interest is in the design of algorithms for both of these problems that are efficiently scalable, even as the number of objects involved grows very large. To aid in the design of scalable algorithms, we observe that some inputs have good separators, meaning that by removing some subset S of objects, one can divide the remaining objects into two sets V and V', where all pairs of objects between V and V' are incompatible. We design several new algorithms that exploit good separators, and prove that these algorithms scale better than previously existing approaches.

This thesis presents a thorough introduction to flow shop problems with synchronous movement which are a variant of a non-preemptive permutation flow shop. Jobs have to be moved from one machine to the next by an unpaced synchronous transportation system, which implies that the processing is organized in synchronized cycles. This means that in each cycle the current jobs start at the same time on the corresponding machines and after processing have to wait until the last job is finished. Afterwards, all jobs are moved to the next machine simultaneously. In this thesis flow shops with synchronous movement are systematically embedded into the flow shop scheduling framework. The problem is defined for the most common objective functions as well as for many extensions and additional constraints that can be observed in real world applications. The thesis offers an extensive study of complexity of the discussed problems. Several exact and heuristic solution algorithms are proposed and evaluated. Further, a project in cooperation with a practitioner where flow shops with synchronous movement and resource constraints appear in a real world application is discussed. The results of the implemented heuristic approach are compared to the actual production of the industrial partner.

In this dissertation, we consider extensions of dynamic programming for combinatorial optimization. We introduce two exact multi-objective optimization algorithms: the multi-stage optimization algorithm that optimizes the problem relative to the ordered sequence of objectives (lexicographic optimization) and the bi-criteria optimization algorithm that simultaneously optimizes the problem relative to two objectives (Pareto optimization). We also introduce a counting algorithm to count optimal solution before and after every optimization stage of multi-stage optimization. We propose a fairly universal approach based on so-called circuits without repetitions in which each element is generated exactly one time. Such circuits represent the sets of elements under consideration (the sets of feasible solutions) and are used by counting, multi-stage, and bi-criteria optimization algorithms. For a given optimization problem, we should describe an appropriate circuit and cost functions. Then, we can use the designed algorithms for which we already have proofs of their correctness and ways to evaluate the required number of operations and the time. We construct conventional (which work directly with elements) circuits without repetitions for matrix chain multiplication, global sequence alignment, optimal paths in directed graphs, binary search trees, convex polygon triangulation, line breaking (text justification), one-dimensional clustering, optimal bitonic tour, and segmented least squares. For these problems, we evaluate the number of operations and the time required by the optimization and counting algorithms, and consider the results of computational experiments. If we cannot find a conventional circuit without repetitions for a problem, we can either create custom algorithms for optimization and counting from scratch or can transform a circuit with repetitions into a so-called syntactical circuit, which is a circuit without repetitions that works not with elements but with formulas representing these elements. We apply both approaches to the optimization of matchings in trees and apply the second approach to the 0/1 knapsack problem. We also briefly introduce our work in operation research with applications to health care. This work extends our interest in the optimization field from developing new methods included in this dissertation towards the practical application.

Most combinatorial optimization problems are NP -hard, which imply that under well- believed complexity assumptions, there exist no polynomial time algorithms to solve them. To cope with the NP-hardness, approximation algorithms which return solutions close to the optimal, have become a rich field of study. One successful method for designing approx- imation algorithms has been to model the optimization problem as an integer program and then using its polynomial time solvable linear programming relaxation for the design and analysis of such algorithms. Such a technique is called the LP-based technique. In this thesis, we study the algorithmic aspects of three classes of combinatorial optimization problems using LP-based techniques as our main tool. Connectivity Problems: We study the Steiner tree problem and devise new linear pro- gramming relaxations for the problem. We show an equivalence of our relaxation with the well studied bidirected cut relaxation for the Steiner tree problem. Furthermore, for a class of graphs called quasi-bipartite graphs, we improve the best known upper bound on the integrality gap from 3/2 to 4/3. Algorithmically, we obtain fast and simple approximation algorithms for the Steiner tree problem on quasi-bipartite graphs. Allocation Problems: We study the budgeted al location problem of allocating a set of indivisible items to a set of agents who bid on it but possess a hard budget constraint more than which they are unwilling to pay. This problem is a special case of submodular welfare maximization. We use a natural LP relaxation for the problem and improve the best known approximation factor for the problem from ~ 0.632 to 3/4. We also improve the inapprox- imability factor of the problem to 15/16 and use our techniques to show inapproximability results for many other allocation problems. We also study online allocation problems where the set of items are unknown and appear one at a time. Under some necessary assumptions we provide online algorithms for many problems which attain the (almost) optimal competitive ratio. Both these works have applications in the area of budgeted auctions, the most famous of which are the sponsored search auctions hosted by search engines on the Internet. Design Problems: We formally define and study design problems which asks how the weights of an input instance can be designed, so that the minimum (or maximum) of a certain function of the input can be maximized (respectively, minimized). We show if the function can be approximated to any factor $alpha$, then the optimum design can be approximated to the same factor. We also show that (max-min) design problems are dual to packing problems. We use the framework developed by our study of design problems to obtain results about fraction- ally packing Steiner trees in a "black-box" fashion. Finally, we study integral packing of spanning trees and provide an alternate proof of a theorem of Nash-Williams and Tutte about packing spanning trees.

The initial question addressed in this thesis is how to take into account the multi-objective aspect of decision problems in inverse optimization. The most straightforward extension consists of finding a minimal adjustment of the objective functions coefficients such that a given feasible solution becomes efficient. However, there is not only a single question raised by inverse multi-objective optimization, because there is usually not a single efficient solution. The way we define inverse multi-objective<p>optimization takes into account this important aspect. This gives rise to many questions which are identified by a precise notation that highlights a large collection of inverse problems that could be investigated. In this thesis, a selection of inverse problems are presented and solved. This selection is motivated by their possible applications and the interesting theoretical questions they can rise in practice. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

International Telemetering Conference Proceedings / October 18-21, 2004 / Town & Country Resort, San Diego, California / The Broadcast Scheduling Problem (BSP) is a well known NP-complete problem that arises in the study of wireless networks. In the BSP, a finite set of stations are to be scheduled in a time division multiple access (TDMA) frame. The objective is a collision free transmission schedule with the minimum number of TDMA slots and maximal slot utilization. Such a schedule will minimize the total system delay. We present variations of a Greedy Randomized Adaptive Search Procedure (GRASP) for the BSP. Path-relinking, a post-optimization strategy is applied. Also, a reactivity method is used to balance GRASP parameters. Numerical results of our research are reported and compared with other heuristics from the literature.

In this thesis, a class of combinatorial optimization methods rooted in statistical mechanics and their use in signal processing applications will be discussed. The thesis consists of two separate parts. The first part deals with the rationale for my work and also covers the background information necessary to put the second part, which consists of a number of papers, in context. There are (at least) two sides to an optimization problem---the problem statement arising from an application or a design and the selection of an algorithm to solve the problem. In this work the problem statements are practical problems, of combinatorial nature, frequently encountered in signal processing and the algorithms of choice are annealing based algorithms, founded in statistical mechanics. From my work, it is my experience that solving a particular problem often leads to new developments on the part of the algorithm which, in turn, open up possibilities to apply the modified algorithm to a new set of problems, leading to a continuously improving algorithm and a growing field of applications. The included papers deal with the application of annealing optimization methods to the problems of configuring active noise and vibration control systems, digital filter design and adaptive filtering. They also describe the successive development of a highly efficient entropy-directed deterministic annealing (EDDA) optimization algorithm detailed in the final paper.