Interval graphs are well studied structures. Intervals can represent resources like jobs to be sched-uled. Finding maximum independent set in interval graphs would correspond to scheduling maximum number of non-conflicting jobs on the computer. Most optimization problems on interval graphs like independent set, vertex cover, dominating set, maximum clique, etc can be solved efficiently using combinatorial algorithms in polynomial time. Hitting, Covering and Packing problems have been ex-tensively studied in the last few decades and have applications in diverse areas. While they are NP-hard for most settings, they are polynomial solvable for intervals. In this thesis, we consider the generaliza-tions of hitting, covering and packing problems for intervals. We model these problems as min-cost flow problems using non-trivial reduction and solve it using standard flow algorithms. Demand-hitting problem which is a generalization of hitting problem is defined as follows: Given N intervals, a positive integer demand for every interval, M points, a real weight for every point, select a subset of points H, such that every interval contains at least as many points in H as its demand and sum of weight of the points in H is minimized. Note that if the demand is one for all intervals, we get the standard hitting set problem. In this case, we give a dynamic programming based O(M + N) time algorithm assuming that intervals and points are sorted. A special case of the demand-hitting set is the K-hitting set problem where the demand of all the intervals is K. For the K-hitting set problem, we give a O(M2N) time flow based algorithm. For the demand-hitting problem, we make an assumption that no interval is contained in another interval. Under this assumption, we give a O(M2N) time flow based algorithm. Demand-covering problem which is a generalization of covering problem is defined as follows: Given N intervals, a real weight for every interval, M points, a positive integer demand for every point, select a subset of intervals C, such that every point is contained in at least as many intervals in C as its demand and sum of weight of the intervals in C is minimized. Note that if the demand of points are one, we get the standard covering set problem. In this case, we give a dynamic programming based O(M + N log N) time algorithm assuming that points are sorted. A special case of the demand-covering set is the K-covering set problem where the demand of all the points is K. For the K-covering set problem, we give a O(MN2) time flow based algorithm. For the demand-covering problem, we give a O(MN2) time flow based algorithm. K-pack points problem which is a generalization of packing problem is defined as follows: Given N intervals, an integer K, M points, a real weight for every point, select a subset of points Y , such that every interval contains at most K points from Y and sum of weight of the points in Y is maximized. Note that if K is one, we get the standard pack points problem. In this case, we give a dynamic pro-gramming based O(M + N) time algorithm assuming that points and intervals are sorted. For K-pack points problem, we give O(M2 log M) time flow based algorithm assuming that intervals and points are sorted.

Empresas estão procurando reduzir seus custos e aumentar seu desempenho e competitividade. Neste cenário de redução de custos, a logística colaborativa pode ser uma aliada. Numa rede complexa, onde embarcadores muitas vezes nem sabem da existência de outros embarcadores com demandas complementares, existe um potencial de sinergia e redução de custos através da diminuição de deslocamentos de veículos sem carga, ou seja, deslocamentos para reposicionar os veículos. Visando essa redução, o Problema de Cobertura de Rotas (PCR), que tem como objetivo cobrir rotas no mínimo custo, une as demandas de frete de vários embarcadores e tenta minimizar os deslocamentos sem cargas (reposicionamentos), reduzindo assim o custo total de toda a rede dos embarcadores envolvidos. Esta pesquisa propõe um modelo e uma heurística para resolver, em grande escala através de programação paralela, uma expansão do PCR. / Companies are looking to reduce costs and improve performance and competitiveness. In this cost-cutting scenario, collaborative logistics can be an ally. In a complex network where shippers often do not know of the existence of other shippers with complementary demands, there is potential for synergy and cost savings by reducing unloaded travelling of vehicles, i.e, the distance and time to reposition the vehicles\'. Towards that reduction, the Lane Covering Problem (LCP), which aims to cover at least cost routeslinks the various shippers\' demands of freight and tries to minimize operations without loads (repositioning), thus reducing the total cost of the entire network for involved shippers. This research proposes a model and an heuristic to solve, in large-scale through parallel programming, an expansion of the PCR.

A crescente necessidade de buscar operações mais eficientes, com menor custo e mais sustentáveis tem feito com que empresas passassem a procurar oportunidades pelas quais estes objetivos pudessem ser atingidos. Na área de transportes encontrou-se na colaboração uma oportunidade para tal. Este trabalho trata o problema de cobertura rotas com cardinalidade restrita (PCRCR), onde empresas que realizam viagens de carga cheia se unem com o objetivo de reduzir o deslocamento vazio de veículos através da formação de ciclos. É chamado de problema de cardinalidade restrita uma vez que limitamos o número de máximo de viagens no ciclo, o que torna este problema NP-Hard. Existem na literatura duas heurísticas (construtivas) e um modelo por programação linear inteira para a solução deste problema. Este trabalho apresenta uma heurística baseada em um método de busca local que reduziu em média 3,19% os melhores resultados apresentados na literatura. Também são apresentados os tempos de execução de cada um dos algoritmos e a importância de escolher de uma boa solução inicial quando se deseja implantar uma Heurística com Busca Local. / The growing need to seek more efficient, lower cost and more sustainable operations has caused industries to seek opportunities in which these objectives could be achieved. In the area of transportation, collaboration is an opportunity for that. This work deals with the cardinality constrained lane covering problem (CCLCP), where companies who uses full truck loads join efforts in order to reduce empty vehicle travel through closed cycle formation. It is known as cardinality constraint problem as the maximum number of trips in the cycle is limited to an integer number, which makes this problem NP-Hard. There are two heuristics in the literature (constructive) and an integer linear programming model for solving this problem. This work presents a heuristic based on a local search method that reduced an average of 3.19% the better results in the literature. It also presents the execution times of each algorithm and the importance of choosing a good initial solution when you want to create a Local Search Heuristic.

Remote sensors and unmanned aerial vehicles (UAVs) have the potential to dramatically improve infrastructure health monitoring in terms of accuracy of the information and frequency of data collection. UAV automation has made significant progress but that automation is also creating vast amounts of data that needs to be processed into actionable information. A key aspect of this work is the optimization (not just automation) of data collection from UAVs for targeted planning of mission objectives. This work investigates the use of camera planning for Structure from Motion for 3D modeling of infrastructure. Included in this thesis is a novel multi-scale view-planning algorithm for autonomous targeted inspection. The method presented reduced the number of photos needed and therefore reduced the processing time while maintaining desired accuracies across the test site. A second focus in this work investigates various set covering problem algorithms to use for selecting the optimal camera set. The trade-offs between solve time and quality of results are explored. The Carousel Greedy algorithm is found to be the best method for solving the problem due to its relatively fast solve speeds and the high quality of the solutions found. Finally, physical flight tests are used to demonstrate the quality of the method for determining coverage. Each of the set covering problem algorithms are used to create a camera set that achieves 95% coverage. The models from the different camera sets are comparable despite having a large amount of variability in the camera sets chosen. While this study focuses on multi-scale view planning for optical sensors, the methods could be extended to other remote sensors, such as aerial LiDAR.

Remote sensors and unmanned aerial vehicles (UAVs) have the potential to dramatically improve infrastructure health monitoring in terms of accuracy of the information and frequency of data collection. UAV automation has made significant progress but that automation is also creating vast amounts of data that needs to be processed into actionable information. A key aspect of this work is the optimization (not just automation) of data collection from UAVs for targeted planning of mission objectives. This work investigates the use of camera planning for Structure from Motion for 3D modeling of infrastructure. Included in this thesis is a novel multi-scale view-planning algorithm for autonomous targeted inspection. The method presented reduced the number of photos needed and therefore reduced the processing time while maintaining desired accuracies across the test site. A second focus in this work investigates various set covering problem algorithms to use for selecting the optimal camera set. The trade-offs between solve time and quality of results are explored. The Carousel Greedy algorithm is found to be the best method for solving the problem due to its relatively fast solve speeds and the high quality of the solutions found. Finally, physical flight tests are used to demonstrate the quality of the method for determining coverage. Each of the set covering problem algorithms are used to create a camera set that achieves 95% coverage. The models from the different camera sets are comparable despite having a large amount of variability in the camera sets chosen. While this study focuses on multi-scale view planning for optical sensors, the methods could be extended to other remote sensors, such as aerial LiDAR.

No description available.

Algorithmic mechanism design deals with efficiently-computable algorithmic constructions in the presence of strategic players who hold the inputs to the problem and may misreport their input if doing so benefits them. Algorithmic mechanism design finds applications in a variety of internet settings such as resource allocation, facility location and e-commerce, such as sponsored search auctions. There is an extensive amount of work in algorithmic mechanism design on packing problems such as single-item auctions, multi-unit auctions and combinatorial auctions. But, surprisingly, covering problems, also called procurement auctions, have almost been completely unexplored, especially in the multidimensional setting. In this thesis, we systematically investigate multidimensional covering mechanism- design problems, wherein there are m items that need to be covered and n players who provide covering objects, with each player i having a private cost for the covering objects he provides. A feasible solution to the covering problem is a collection of covering objects (obtained from the various players) that together cover all items. Two widely considered objectives in mechanism design are: (i) cost-minimization (CM) which aims to minimize the total cost incurred by the players and the mechanism designer; and (ii) payment minimization (PayM), which aims to minimize the payment to players. Covering mechanism design problems turn out to behave quite differently from packing mechanism design problems. In particular, various techniques utilized successfully for packing problems do not perform well for covering mechanism design problems, and this necessitates new approaches and solution concepts. In this thesis we devise various techniques for handling covering mechanism design problems, which yield a variety of results for both the CM and PayM objectives. In our investigation of the CM objective, we focus on two representative covering problems: uncapacitated facility location (UFL) and vertex cover. For multi-dimensional UFL, we give a black-box method to transform any Lagrangian-multiplier-preserving ??-approximation algorithm for UFL into a truthful-in-expectation, ??-approximation mechanism. This yields the first result for multi-dimensional UFL, namely a truthful-in-expectation 2-approximation mechanism. For multi-dimensional VCP (Multi-VCP), we develop a decomposition method that reduces the mechanism-design problem into the simpler task of constructing threshold mechanisms, which are a restricted class of truthful mechanisms, for simpler (in terms of graph structure or problem dimension) instances of Multi-VCP. By suitably designing the decomposition and the threshold mechanisms it uses as building blocks, we obtain truthful mechanisms with approximation ratios (n is the number of nodes): (1) O(r2 log n) for r-dimensional VCP; and (2) O(r log n) for r-dimensional VCP on any proper minor-closed family of graphs (which improves to O(log n) if no two neighbors of a node belong to the same player). These are the first truthful mechanisms for Multi-VCP with non-trivial approximation guarantees. For the PayM objective, we work in the oft-used Bayesian setting, where players??? types are drawn from an underlying distribution and may be correlated, and the goal is to minimize the expected total payment made by the mechanism. We consider the problem of designing incentive compatible, ex-post individually rational (IR) mechanisms for covering problems in the above model. The standard notion of incentive compatibility (IC) in such settings is Bayesian incentive compatibility (BIC), but this notion is over-reliant on having precise knowledge of the underlying distribution, which makes it a rather non- robust notion. We formulate a notion of IC that we call robust Bayesian IC (robust BIC) that is substantially more robust than BIC, and develop black-box reductions from robust BIC-mechanism design to algorithm design. This black-box reduction applies to single- dimensional settings even when we only have an LP-relative approximation algorithm for the algorithmic problem. We obtain near-optimal mechanisms for various covering settings including single- and multi-item procurement auctions, various single-dimensional covering problems, and multidimensional facility location problems. Finally, we study the notion of frugality, which considers the PayM objective but in a worst-case setting, where one does not have prior information about the players??? types. We show that some of our mechanisms developed for the CM objective are also good with respect to certain oft-used frugality benchmarks proposed in the literature. We also introduce an alternate benchmark for frugality, which more directly reflects the goal that the mechanism???s payment be close to the best possible payment, and obtain some preliminary results with respect to this benchmark.

Empresas estão procurando reduzir seus custos e aumentar seu desempenho e competitividade. Neste cenário de redução de custos, a logística colaborativa pode ser uma aliada. Numa rede complexa, onde embarcadores muitas vezes nem sabem da existência de outros embarcadores com demandas complementares, existe um potencial de sinergia e redução de custos através da diminuição de deslocamentos de veículos sem carga, ou seja, deslocamentos para reposicionar os veículos. Visando essa redução, o Problema de Cobertura de Rotas (PCR), que tem como objetivo cobrir rotas no mínimo custo, une as demandas de frete de vários embarcadores e tenta minimizar os deslocamentos sem cargas (reposicionamentos), reduzindo assim o custo total de toda a rede dos embarcadores envolvidos. Esta pesquisa propõe um modelo e uma heurística para resolver, em grande escala através de programação paralela, uma expansão do PCR. / Companies are looking to reduce costs and improve performance and competitiveness. In this cost-cutting scenario, collaborative logistics can be an ally. In a complex network where shippers often do not know of the existence of other shippers with complementary demands, there is potential for synergy and cost savings by reducing unloaded travelling of vehicles, i.e, the distance and time to reposition the vehicles\'. Towards that reduction, the Lane Covering Problem (LCP), which aims to cover at least cost routeslinks the various shippers\' demands of freight and tries to minimize operations without loads (repositioning), thus reducing the total cost of the entire network for involved shippers. This research proposes a model and an heuristic to solve, in large-scale through parallel programming, an expansion of the PCR.

A crescente necessidade de buscar operações mais eficientes, com menor custo e mais sustentáveis tem feito com que empresas passassem a procurar oportunidades pelas quais estes objetivos pudessem ser atingidos. Na área de transportes encontrou-se na colaboração uma oportunidade para tal. Este trabalho trata o problema de cobertura rotas com cardinalidade restrita (PCRCR), onde empresas que realizam viagens de carga cheia se unem com o objetivo de reduzir o deslocamento vazio de veículos através da formação de ciclos. É chamado de problema de cardinalidade restrita uma vez que limitamos o número de máximo de viagens no ciclo, o que torna este problema NP-Hard. Existem na literatura duas heurísticas (construtivas) e um modelo por programação linear inteira para a solução deste problema. Este trabalho apresenta uma heurística baseada em um método de busca local que reduziu em média 3,19% os melhores resultados apresentados na literatura. Também são apresentados os tempos de execução de cada um dos algoritmos e a importância de escolher de uma boa solução inicial quando se deseja implantar uma Heurística com Busca Local. / The growing need to seek more efficient, lower cost and more sustainable operations has caused industries to seek opportunities in which these objectives could be achieved. In the area of transportation, collaboration is an opportunity for that. This work deals with the cardinality constrained lane covering problem (CCLCP), where companies who uses full truck loads join efforts in order to reduce empty vehicle travel through closed cycle formation. It is known as cardinality constraint problem as the maximum number of trips in the cycle is limited to an integer number, which makes this problem NP-Hard. There are two heuristics in the literature (constructive) and an integer linear programming model for solving this problem. This work presents a heuristic based on a local search method that reduced an average of 3.19% the better results in the literature. It also presents the execution times of each algorithm and the importance of choosing a good initial solution when you want to create a Local Search Heuristic.

Municipalities in the Czech Republic deal with their budget, which among others consists of granted subsidies from the region, State, European Union or other organizations. Nowadays the budget transactions are not being under the control. In the future, it is appropriate to introduce some external view to control their spending. Establishment of an audit service for each municipality would be financially inevitable. Therefore it is suggested to provide the State audit services only in some municipalities and to share them with more municipalities within one region. Deployment of the audit centers and assigning municipalities lead to solving a linear problem which falls under the covering problem class. The establishment of audit centers is only illustrative, the employment of more shared state services could follow a similar principle.