One central question in theoretical computer science is how to solve problems accurately and quickly. Despite the encouraging development of various algorithmic techniques in the past, we are still at the very beginning of the understanding of these techniques. One particularly interesting paradigm is the greedy algorithm paradigm. Informally, a greedy algorithm builds a solution to a problem incrementally by making locally optimal decisions at each step. Greedy algorithms are important in algorithm design as they are natural, conceptually simple to state and usually efficient. Despite wide applications of greedy algorithms in practice, their behaviour is not well understood. However, we do know that in several specific settings, greedy algorithms can achieve good results. This thesis focuses on examining contexts in which greedy and greedy-like algorithms are successful, and extending them to more general settings. In particular, we investigate structural properties of graphs and set systems, families of special functions, and greedy approximation algorithms for several classic NP-hard problems in those contexts. A natural phenomenon we observe is a trade-off between the approximation ratio and the generality of those contexts.

Cette thèse s’intéresse à la résolution de problèmes d’optimisation combinatoires NP-difficiles en utilisant des méthodes de résolution approchées. Deux domaines d’application sont ciblés ici, d’une part la problématique générale du réseau de transport avec une variante portant plus précisément sur la planification des tournées avec une équipe de véhicules, d’autre part le problème de gestion de sessions en mode multicast dans un réseau de télécommunication, abordé ici du point de vue plus général du partitionnement dans un graphe biparti. Ces deux applications sont évidemment d’intérêt, tant du point de vue fondamental pour les méthodes de résolution qui doivent toujours progresser face à de nouveaux challenges, que du point de vue des retombées industrielles potentielles. La résolution de tels problèmes comporte généralement deux phases : dans un premier temps il s’agit de définir un ou plusieurs modèles mathématiques, de les comparer éventuellement pour choisir le plus efficace en fonction des outils de résolution disponibles; dans un deuxième temps il est possible d’utiliser un paradigme de résolution générique, comme par exemple un solveur de programmation linéaire, ou bien de spécialiser un algorithme en y incluant des heuristiques et connaissances spécifiques, afin d’optimiser sa performance. C’est dans cette deuxième démarche que se situe cette thèse, démarche souvent nécessaire lorsque les problèmes abordés deviennent complexes et/ou de grande taille et que l’on souhaite concevoir des algorithmes plus efficaces / This thesis focuses on solving combinatorial optimization problems NP-hard using approximate solving methods. Two practical application areas are targeted here, firstly the general problem of vehicule routing network with a variant specifically with planning tours with a vehicle team, on the other hand the multicast session management problem on a telecommunications network, addressed by the broader perspective of clustering in a bipartite graph. Both applications are obviously of interest both from the fundamental point of view for the resolution methods that must always progress facing new challenges, from the point of view of potential industrial benefits. The resolution of such problems usually has two phases: initially it comes to define one or more mathematical models to compare possibly to choose the most effective according to the available resolution tools; secondly it is possible to use a generic resolution paradigm, such as a linear programming solver, or specialize an algorithm by including specific heuristics and knowledge to optimize its performance. This thesis is in this second approach. This is often necessary when the problems addressed become complex and / or large and that we need to be designing more efficient algorithms

The areas of machine learning, data mining, and knowledge representation have many different formats used to represent information. Decision rules, amongst these formats, are the most expressive and easily-understood by humans. In this thesis, we use dynamic programming to design decision rules and analyze them. The use of dynamic programming allows us to work with decision rules in ways that were previously only possible for brute force methods. Our algorithms allow us to describe the set of all rules for a given decision table. Further, we can perform multi-stage optimization by repeatedly reducing this set to only contain rules that are optimal with respect to selected criteria. One way that we apply this study is to generate small systems with short rules by simulating a greedy algorithm for the set cover problem. We also compare maximum path lengths (depth) of deterministic and non-deterministic decision trees (a non-deterministic decision tree is effectively a complete system of decision rules) with regards to Boolean functions. Another area of advancement is the presentation of algorithms for constructing Pareto optimal points for rules and rule systems. This allows us to study the existence of “totally optimal” decision rules (rules that are simultaneously optimal with regards to multiple criteria). We also utilize Pareto optimal points to compare and rate greedy heuristics with regards to two criteria at once. Another application of Pareto optimal points is the study of trade-offs between cost and uncertainty which allows us to find reasonable systems of decision rules that strike a balance between length and accuracy.

In July 2012, a paper by Gutfraind et al. introduced the neighbor-aided network installation problem, which asks for "a minimal cost ordering of the vertices of a graph, where the cost of visiting a node is a function of the number of neighbors that have already been visited." Additionally, in a 2018 paper by Cummings et al., two greedy heuristics were implemented to estimate solutions to the NANIP-Blackstart problem. This paper will evaluate the performance of the greedy heuristics introduced by Cummings et al., and compare their performance to a new heuristic. In addition to comparing heuristics, we will also look at varying the blackstart node and cost function. This analysis will be conducted by testing the heuristics on power networks from the SuiteSparse Matrix Collection and NIST Matrix Market. The goal of this body of work is to better understand the variables at play in the NANIP-Blackstart problem in order to work towards better estimated solutions.

In this dissertation, we study several problems related to intervals and develop efficient algorithms for them. Interval problems have many applications in reality because many objects, values, and ranges are intervals in nature, such as time intervals, distances, line segments, probabilities, etc. Problems on intervals are gaining attention also because intervals are among the most basic geometric objects, and for the same reason, computational geometry techniques find useful for attacking these problems. Specifically, the problems we study in this dissertation includes the following: balanced splitting on weighted intervals, minimizing the movements of spreading points, dispersing points on intervals, multiple barrier coverage, and separating overlapped intervals on a line. We develop efficient algorithms for these problems and our results are either first known solutions or improve the previous work. In the problem of balanced splitting on weighted intervals, we are given a set of n intervals with non-negative weights on a line and an integer k ≥ 1. The goal is to find k points to partition the line into k + 1 segments, such that the maximum sum of the interval weights in these segments is minimized. We give an algorithm that solves the problem in O(n log n) time. Our second problem is on minimizing the movements of spreading points. In this problem, we are given a set of points on a line and we want to spread the points on the line so that the minimum pairwise distance of all points is no smaller than a given value δ. The objective is to minimize the maximum moving distance of all points. We solve the problem in O(n) time. We also solve the cycle version of the problem in linear time. For the third problem, we are given a set of n non-overlapping intervals on a line and we want to place a point on each interval so that the minimum pairwise distance of all points are maximized. We present an O(n) time algorithm for the problem. We also solve its cycle version in O(n) time. The fourth problem is on multiple barrier coverage, where we are given n sensors in the plane and m barriers (represented by intervals) on a line. The goal is to move the sensors onto the line to cover all the barriers such that the maximum moving distance of all sensors is minimized. Our algorithm for the problem runs in O(n2 log n log log n + nm log m) time. In a special case where the sensors are all initially on the line, our algorithm runs in O((n + m) log(n + m)) time. Finally, for the problem of separating overlapped intervals, we have a set of n intervals (possibly overlapped) on a line and we want to move them along the line so that no two intervals properly intersect. The objective is to minimize the maximum moving distance of all intervals. We propose an O(n log n) time algorithm for the problem. The algorithms and techniques developed in this dissertation are quite basic and fundamental, so they might be useful for solving other related problems on intervals as well.

<p>The thesis consists of four papers on combinatorial auctions and a summary. The first part is more of a practical nature and contains two papers. In the first paper, we study the performance of a caching technique in an optimal algorithm for a multi-unit combinatorial auction.</p><p>In the second paper, we compare the revenues from a second-price combinatorial auction against a second-price one-shot simultaneous auction. In particular, we show that when the synergy parameter is small, the combinatorial auction gives a higher expected revenue than the one-shot. This is in contrast to an earliear result by Krishna and Rosenthal. We also compare the two mechanisms under the assumption that bidders are risk-averse. Such bidders are more sensitive to financial loss (winner's curse) that they tend to bid less aggressively, which leads to lower revenues. Since a direct analytical approach turns out to be difficult, we present numerical results that show which auction mechanism maximizes the seller's revenue depending on the values of synergy and aversion parameter.</p><p>The second part is more theoretical. Here, we analyze the asymptotic performance of a greedy algorithm for a problem inspired by combinatorial auctions. In particular, we consider a special case in which every bid contains exactly 3 items, and use a Poisson process to model an auction with a random (Poisson) No. of bids. For this restricted case, winner determination problem is equivalent to a maximal 3-set packing on a weighted hypergraph, and hence NP-complete. However, the greedy algorithm approximates this special case within a factor of 3.</p><p>In the third paper, we compute the asymptotic expected size of the partial allocation and its corresponding expected total revenue from the greedy algorithm, for some distribution of bid prices.</p><p>In the final paper, we study the case of a deterministic number of bids, which is proportional to the number of distinguishable items in the auction, say M. Then, we prove that the number of bids allocated, suitably normalized, converges to a Normal random variable as M goes to infinity. As a prelude, we also prove that, both the number of bids allocated and those submitted, again suitably normalized, jointly converge in distribution to a continuous 2-dimensional Gaussian process as M goes to infinity.</p>

The thesis consists of four papers on combinatorial auctions and a summary. The first part is more of a practical nature and contains two papers. In the first paper, we study the performance of a caching technique in an optimal algorithm for a multi-unit combinatorial auction. In the second paper, we compare the revenues from a second-price combinatorial auction against a second-price one-shot simultaneous auction. In particular, we show that when the synergy parameter is small, the combinatorial auction gives a higher expected revenue than the one-shot. This is in contrast to an earliear result by Krishna and Rosenthal. We also compare the two mechanisms under the assumption that bidders are risk-averse. Such bidders are more sensitive to financial loss (winner's curse) that they tend to bid less aggressively, which leads to lower revenues. Since a direct analytical approach turns out to be difficult, we present numerical results that show which auction mechanism maximizes the seller's revenue depending on the values of synergy and aversion parameter. The second part is more theoretical. Here, we analyze the asymptotic performance of a greedy algorithm for a problem inspired by combinatorial auctions. In particular, we consider a special case in which every bid contains exactly 3 items, and use a Poisson process to model an auction with a random (Poisson) No. of bids. For this restricted case, winner determination problem is equivalent to a maximal 3-set packing on a weighted hypergraph, and hence NP-complete. However, the greedy algorithm approximates this special case within a factor of 3. In the third paper, we compute the asymptotic expected size of the partial allocation and its corresponding expected total revenue from the greedy algorithm, for some distribution of bid prices. In the final paper, we study the case of a deterministic number of bids, which is proportional to the number of distinguishable items in the auction, say M. Then, we prove that the number of bids allocated, suitably normalized, converges to a Normal random variable as M goes to infinity. As a prelude, we also prove that, both the number of bids allocated and those submitted, again suitably normalized, jointly converge in distribution to a continuous 2-dimensional Gaussian process as M goes to infinity.

Snow cleaning is one of the important tasks in the winter time in Sweden. Every year government spends huge amount money for snow cleaning purpose. In this thesis we generate a shortest road network of the city and put the depots in different place of the city for snow cleaning. We generate shortest road network using minimum spanning tree algorithm and find the depots position using greedy heuristic. When snow is falling, vehicles start work from the depots and clean the snow all the road network of the city. We generate two types of model. Models are economic model and efficient model. Economic model provide good economical solution of the problem and it use less number of vehicles. Efficient model generate good efficient solution and it take less amount of time to clean the entire road network.

In this thesis we use greedy randomize adaptive search procedure (GRASP) to solve the traveling salesman problem (TSP). Starting with nearest neighbor method to construct the initial TSP tour, we apply the 2-opt and the path-relinking method for the initial tour improvement. To increase 2-opt search speed, fixed-radius near neighbor search and don0t &#8722; look bit techniques are introduced. For the same reason a new efficient data structure, the reverse array, is proposed to represent the TSP tour. Computational results show that GRASP gives fairly good solutions in a short time.

We develop a class of models to represent the dynamics of a virus spreading in a cellphone network, employing a taxonomy that includes five key characteristics. Based on the resulting dynamics governing the spread, we present optimization models to rapidly detect the virus, subject to resource limitations. We consider two goals, maximizing the probability of detecting a virus by a time threshold and minimizing the expected time to detection, which can be applied to all spread models we consider. We establish a submodularity result for these two objective functions that ensures that a greedy heuristic yields a well-known constant-factor (63%) approximation. We relate the latter optimization problem, under a specific virus-spread mechanism from our class of models, to a classic facility-location model. Using data from a large carrier, we build several base cellphone contact networks of different scale. We then rescale these base networks using the so-called c-core decomposition that removes vertices of low degree in a recursive way. We further show that this down-sampling strategy preserves, in general, the topological properties of the base networks, based on testing several measures. For the objective that maximizes the probability that we detect a virus by a time threshold, we provide a sample-average optimization model that yields an asymptotically-optimal design for locating the detection devices, as the number of samples grows large. To choose a relevant time threshold, we perform a simulation for some spread models. We then test the performance of our proposed solution methods by solving the presented optimization models for some spread dynamics using some of the contact networks built after the c-core decomposition. The computational results show that the greedy algorithm is an efficient way to solve the corresponding sample-average approximation model, and the greedy solutions outperform some other simple solution approaches. / text