In this dissertation, we examine specific network connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite its many practical uses, this problem has not been previously studied. We present the first constant factor approximation algorithm for VCC, and provide an upper bound on the integrality gap of its linear programming relaxation. We also introduce a new, useful, extension of the minimum spanning tree problem, called the Extended Minimum Spanning Tree Problem (EMST), that is based on a special case of VCC; and provide both a polynomial-time algorithm and a complete linear description for it. Furthermore, we show how to generalize this new problem to handle numerous disjoint vital cores, providing the first complete linear description of, and polynomial-time algorithm for, the generalized problem. We examine the Survivable Network Design Problem (SNDP) with multiple copies of edges allowed in the solution (multi-SNDP), and present a new approximation algorithm for which the approximation guarantee is better than that of the current best known for certain cases of multi-SNDP. With our method, we also obtain improved bounds on the integrality gap of the linear programming relaxation of the problem. Furthermore, we show the application of these results to variations of SNDP. We investigate cases where the optimal values of multi-SNDP and SNDP are equal; and we present an improvement on the previously best known integrality gap bound and approximation guarantee for the special case of SNDP with metric costs and low vertex connectivity requirements, as well as for the similar special case of the Vertex Connected Survivable Network Design Problem (VC-SNDP). The quality of the results that one can obtain for a given network design problem often depends on its integer linear programming formulation, and, in particular, on its linear programming relaxation. In this connection, we investigate formulations for the Steiner Tree Problem (ST). We propose two new formulations for ST, and investigate their strength in terms of their associated integrality gaps.

A graph is said to be 2-edge-connected if it remains connected after the deletion of any single edge. Given an unweighted bridgeless graph G with n vertices, the minimum size 2-edge-connected spanning subgraph problem (2EC) is that of finding a 2-edge-connected spanning subgraph of G with the minimum number of edges. This problem has important applications in the design of survivable networks. However, because the problem is NP-hard, it is unlikely that efficient methods exist for solving it. Thus efficient methods that find solutions that are provably close to optimal are sought. In this thesis, an approximation algorithm is presented for 2EC on bridgeless cubic graphs which guarantees to be within 5/4 of the optimal solution value, improving on the previous best proven approximation guarantee of 5/4+ε for this problem. We also focus on the linear programming (LP) relaxation of 2EC, which provides important lower bounds for 2EC in useful solution techniques like branch and bound. The “goodness” of this lower bound is measured by the integrality gap of the LP relaxation for 2EC, denoted by α2EC. Through a computational study, we find the exact value of α2EC for graphs with small n. Moreover, a significant improvement is found for the lower bound on the value of α2EC for bridgeless subcubic graphs, which improves the known best lower bound on α2EC from 9/8 to 8/7.

Orientador: Eduardo Candido Xavier / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-27T04:49:46Z (GMT). No. of bitstreams: 1 Povoa_MarceloGalvao_M.pdf: 1965830 bytes, checksum: 7509ae1701df384bfdc3d415ecd4eda8 (MD5) Previous issue date: 2015 / Resumo: Sistemas computacionais conhecidos como Data Grids fornecem uma infraestrutura computacional distribuída para processamento e armazenamento de dados, com várias aplicações envolvendo computação em larga escala. Devido ao uso de um grande volume de dados, é necessário não apenas um escalonamento eficiente de tarefas, mas também uma distribuição inteligente de réplicas dos dados para se atingir o melhor desempenho. Esses dois problemas já foram extensivamente estudados de forma independente na literatura, mas estamos concentrados em um formulação integrada em um problema estático, de forma a otimizar uma única função objetivo. Primeiramente, mostramos que este problema não pode admitir um algoritmo aproximado. Porém, considerando uma versão restrita do problema, apresentamos um algoritmo aproximado original com fator de aproximação constante. Também fazemos um estudo de algoritmos aproximados para problemas relacionados disponíveis na literatura. Sob um aspecto mais prático, introduzimos duas heurísticas originais para o problema. A primeira é baseada no agrupamento de máquinas próximas em clusters, enquanto a segunda procura identificar grupos de dados frequentemente acessados em conjunto. Comparamos esses algoritmos com duas abordagens adaptadas da literatura, através de simulações computacionais em um grande conjunto de instâncias baseadas em grids reais. Mostramos que nossa primeira heurística costuma obter melhores soluções que as outras com boa eficiência de tempo, enquanto a segunda heurística é ainda mais rápida e ainda obtém soluções competitivas / Abstract: Computational systems known as Data Grids provide a flexible, distributed computing infrastructure for processing and storage and has many applications in large-scale computing. Due to the use of great amounts of data, not only efficient task scheduling but also thorough file replication are crucial for achieving the best performance. Both these problems have already been studied independently in the literature, but we are interested in a combined formulation as a static problem, in order to minimize a single objective function. First, we show that this problem does not admit an approximation algorithm. However, considering a restricted version of the problem, we provide a constant ratio approximation algorithm. We also conduct a study of approximation algorithms for related problems avaliable in the literature. On a more practical side, we introduce two novel heuristics for the problem. The first is based on grouping neighbor nodes into clusters, while the second tries to identify groups of files frequently accessed together. We compare these algorithms with two adapted approaches from other works in the literature by doing computational simulations using an extensive set of instances based on real grids. We show that our first heuristic often obtains the best solutions with good time efficiency, while the second is even faster and still provides competitive solutions / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

O tema central deste trabalho é o estudo de problemas sobre caminhos mais longos em grafos, de pontos de vista tanto estrutural como algorítmico. A primeira parte tem como foco o estudo de problemas motivados pela seguinte questão levantada por T. Gallai em 1966: é verdade que em todo grafo conexo existe um vértice comum a todos os seus caminhos mais longos? Hoje, já se conhecem diversos grafos conexos cuja intersecção de todos os seus caminhos mais longos é vazia. Entretanto, existem classes de grafos para as quais a resposta à pergunta de Gallai é afirmativa. Nessa linha, apresentamos alguns resultados da literatura e duas novas classes que obtivemos: os grafos exoplanares e as 2-árvores. Motivado por esse problema, nos anos 80, T. Zamfirescu formulou a seguinte pergunta que permanece em aberto: é verdade que em todo grafo conexo existe um vértice comum a quaisquer três de seus caminhos mais longos? Apresentamos, além de alguns resultados conhecidos, uma prova de que a resposta é afirmativa para grafos em que todo bloco não trivial é hamiltoniano. Notamos que esse último resultado e o acima mencionado para grafos exoplanares generalizam um teorema de M. Axenovich (2009) que afirma que quaisquer três caminhos mais longos em um grafo exoplanar têm um vértice em comum. Finalmente, mencionamos alguns outros resultados da literatura relacionados com o tema. Na segunda parte, investigamos o problema de encontrar um caminho mais longo em um grafo. Este problema é NP-difícil para grafos arbitrários. Isto motiva investigações em duas linhas a respeito da busca de tais caminhos. Pode-se procurar classes especiais de grafos para as quais existem algoritmos polinomiais, ou pode-se abrir mão da busca de um caminho mais longo, e projetar um algoritmo eficiente que encontra um caminho cujo comprimento esteja próximo do comprimento de um mais longo. Nesse trabalho estudamos ambas as abordagens e apresentamos alguns resultados da literatura. / The central theme of this thesis is the study of problems related to longest paths in graphs, both from a structural and an algorithmic point of view. The first part focuses on the study of problems motivated by the following question raised by T. Gallai in 1966: is it true that every connected graph has a vertex common to all its longest paths? Today, many connected graphs in which all longest paths have empty intersection are known. However, there are classes of graphs for which Gallais question has a positive answer. In this direction, we present some results from the literature, as well as two new classes we obtained: outerplanar graphs and 2-trees. Motivated by this problem, T. Zamfirescu, in the 80s, proposed the following question which remains open: is it true that every connected graph has a vertex common to any three of its longest paths? We present, in addition to some known results, a proof that the answer to this question is positive for graphs in which all non-trivial blocks are Hamiltonian. We note that this result and the one mentioned above for outerplanar graphs generalize a theorem of M. Axenovich (2009) that states that any three longest paths in an outerplanar graph have a common vertex. Finally, we mention some other related results from the literature. In the second part, we investigate the problem of finding a longest path in a graph. This problem is NP-hard for arbitrary graphs. This motivates investigations in two directions with respect to the search for such paths. We can look for special classes of graphs for which the problem is polynomially solvable, or we can relinquish the search for a longest path and design an efficient algorithm that finds a path whose length is close to that of a longest path. In this thesis we study both approaches and present some results from the literature.

The goal of this thesis is to study the complexity of NP-Hard problems, using the Max-Cut and the Max-k-Cut problems, and the study of fitness landscapes. The Max-Cut and Max-k-Cut problems are well studied NP-hard problems specially since the approximation algorithm of Goemans and Williamson (1995) which introduced the use of SDP to solve relaxed problems. In order to prove the existence of a performance guarantee, the rounding step from the SDP solution to a Max-Cut solution is simple and randomized. For the Max-k-Cut problem, there exist several approximation algorithms but many of them have been proved to be equivalent. Similarly as in Max-Cut, these approximation algorithms use a simple randomized rounding to be able to get a performance guarantee. Ignoring for now the performance guarantee, one could ask if there is a rounding process that takes into account the structure of the relaxed solution since it is the result of an optimization problem. In this thesis we answered this question positively by using clustering as a rounding method. In order to compare the performance of both algorithms, a series of experiments were performed using the so-called G-set benchmark for the Max-Cut problem and using the Random Graph Benchmark of Goemans1995 for the Max-k-Cut problem. With this new rounding, larger cut values are found both for the Max-Cut and the Max-k-Cut problems, and always above the value of the performance guarantee of the approximation algorithm. This suggests that taking into account the structure of the problem to design algorithms can lead to better results, possibly at the cost of a worse performance guarantee. An example for the vertex k-center problem can be seen in Garcia-Diaz et al. (2017), where a 3-approximation algorithm performs better than a 2-approximation algorithm despite having a worse performance guarantee. Landscapes over discrete configurations spaces are an important model in evolutionary and structural biology, as well as many other areas of science, from the physics of disordered systems to operations research. A landscape is a function defined on a very large discrete set V that carries an additional metric or at least topological structure into the real numbers R. We will consider landscapes defined on the vertex set of undirected graphs. Thus let G=G(V,E) be an undirected graph and f an arbitrary real-valued function taking values from V . We will refer to the triple (V,E,f) as a landscape over G. We say two configurations x,y in V are neutral if f(x)=f(y). We colloquially refer to a landscape as 'neutral'' if a substantial fraction of adjacent pairs of configurations are neutral. A flat landscape is one where f is constant. The opposite of flatness is ruggedness and it is defined as the number of local optima or by means of pair correlation functions. These two key features of a landscape, ruggedness and neutrality, appear to be two sides of the same coin. Ruggedness can be measured either by correlation properties, which are sensitive to monotonic transformation of the landscape, and by combinatorial properties such as the lengths of downhill paths and the number of local optima, which are invariant under monotonic transformations. The connection between the two views has remained largely unexplored and poorly understood. For this thesis, a survey on fitness landscapes is presented, together with the first steps in the direction to find this connection together with a relation between the covariance matrix of a random landscape model and its ruggedness.

Avec les préoccupations environnementales croissantes liées aux émissions de carbone et la chute rapide des prix des batteries, la part de marché des véhicules électriques (EV) augmente rapidement. Le nombre croissant de EV ainsi que les progrès sans précédent dans la capacité de la batterie et de la technologie entraîne une augmentation drastique de la demande totale d'énergie destinée aux véhicules électriques. Cette forte demande de charge rend complexe le problème de planification de la charge. Même en prenant avantage de la propriété reportable des demandes de charge et d'une planification adéquate, la demande globale pourrait dépasser le taux de charge tolérable des stations, étant donné les contraintes physiques des dispositifs de charge et des transformateurs. Le principal défi est la nécessité de concevoir des solutions en ligne puisque, dans la pratique, l'ordonnanceur ne dispose d'aucune information sur les arrivées futures d'EV. Cette thèse étudie le problème d'ordonnancement des EV en ligne et fournit trois contributions principales. Premièrement, nous démontrons que le problème classique de la programmation en ligne des tâches sensibles aux échéances avec des valeurs partielles est similaire au problème d'ordonnancement EV et étudions l'extension de la programmation des charges EV en prenant en compte de la limite de traitement des travaux. Le problème réside dans la catégorie des problèmes d'ordonnancement en ligne couplés dans le temps sans disponibilité d'informations futures. Le premier algorithme proposé est déterministe, tandis que le second est randomisé et bénéficie d'une complexité de calcul plus faible. Deuxièmement, nous formulons un problème de maximisation du bien-être social pour la planification de la charge des EV avec une contrainte de capacité de charge. Nous avons conçu des algorithmes d'ordonnancement de charge qui non seulement fonctionnent dans un scénario en ligne, mais aussi qui répondent aux deux principaux défis suivants : (i) fournir un engagement à l'arrivée ; (ii) garantir la résistance aux stratégies (de groupe). Des simulations approfondies utilisant des traces réelles démontrent l'efficacité de nos algorithmes d'ordonnancement en ligne par rapport à la solution hors-ligne optimale non-engagée. La troisième contribution concerne la planification en ligne des véhicules électriques dans un réseau de recharge adaptatif (ACN) avec des contraintes de pics locaux et globaux. Nous avons conçu un algorithme d'ordonnancement primal-dual de faible complexité qui atteint un rapport d'approximation borné. Des résultats expérimentaux détaillés basés sur des traces montrent que les performances des algorithmes en ligne proposés sont proches de l'optimum hors ligne et surpassent les solutions existantes / With the increased environmental concerns related to carbon emission, and rapid drop in battery prices (e.g., 35% drop in 2017), the market share of Electric Vehicles (EVs) is rapidly growing. The growing number of EVs along with the unprecedented advances in battery capacity and technology results in drastic increase in the total energy demand of EVs. This large charging demand makes the EV charging scheduling problem challenging. The critical challenge is the need for online solution design since in practical scenario the scheduler has no information of future arrivals of EVs in a time-coupled underlying problem. This thesis studies online EV scheduling problem and provides three main contributions. First, we demonstrate that the classical problem of online scheduling of deadlinesensitive jobs with partial values is similar to the EV scheduling problem and study the extension to EV charging scheduling by taking into account the processing rate limit of jobs as an additional constraint to the original problem. The problem lies in the category of time-coupled online scheduling problems without availability of future information. Using competitive ratio, as a well-established performance metric, two online algorithms, both of which are shown to be (2 − 1/U)-competitive are proposed, where U is the maximum scarcity level, a parameter that indicates demand-to-supply ratio. Second, we formulate a social welfare maximization problem for EV charging scheduling with charging capacity constraint. We devise charging scheduling algorithms that not only work in online scenario, but also they address the following two key challenges: (i) to provide on-arrival commitment; respecting the capacity constraint may hinder fulfilling charging requirement of deadline-constrained EVs entirely. Therefore, committing a guaranteed charging amount upon arrival of each EV is highly required; (ii) to guarantee (group)-strategy-proofness as a salient feature to promote EVs to reveal their true type and do not collude with other EVs. Third, we tackle online scheduling of EVs in an adaptive charging network (ACN) with local and global peak constraints. Two alternatives in resource-limited scenarios are to maximize the social welfare by partially charging the EVs (fractional model) or selecting a subset of EVs and fully charge them (integral model). For the fractional model, both offline and online algorithms are devised. We prove that the offline algorithm is optimal. We prove the online algorithm achieves a competitive ratio of 2. The integral model, however, is more challenging since the underlying problem is NP-hard due to 0/1 selection criteria of EVs. Hence, efficient solution design is challenging even in offline setting. We devise a low-complexity primal-dual scheduling algorithm that achieves a bounded approximation ratio. Built upon the offline approximate algorithm, we propose an online algorithm and analyze its competitive ratio in special cases

Cache replacement policies have applications that are nearly ubiquitous in technology. Among these is an interesting subset which occurs when referentially transparent functions are memoized, eg. in compilers, in dynamic programming, and other software caches. In many applications the least recently used (LRU) approach likely preserves items most needed by memoized function calls. However, despite its popularity LRU is expensive to implement, which has caused a spate of research initiatives aimed at approximating its cache miss performance in exchange for faster and more memory efficient implementations. We present a novel caching algorithm, Far From Recently Used (FFRU), which offers a simple, but highly configurable mechanism for providing lower bounds on the usage recency of items evicted from the cache. This algorithm preserves the constant time amortized cost of insertions and updates and minimizes the memory overhead needed to administer the eviction guarantees. We study the cache miss performance of several memoized optimization problems which vary in the number of subproblems generated and the access patterns exhibited by their recursive calls. We study their cache miss performance using LRU cache replacement, then show the performance of FFRU in these same problem scenarios. We show that for equivalent minimum eviction age guarantees, FFRU incurs fewer cache misses than LRU, and does so using less memory. We also present some variations of the algorithms studied (Fibonacci, KMP, LCS, and Euclidean TSP) which exploit the characteristics of the cache replacement algorithms being employed, further resulting in improved cache miss performance. We present a novel implementation of a well known approximation algorithm for the Euclidean Traveling Salesman Problem due to Sanjeev Arora. Our implementation of this algorithm outperforms the currently known implementations of the same. It has long remained an open question whether or not algorithms relying on geometric divisions of space can be implemented into practical tools, and our powerful implementation of Arora's algorithm establishes a new benchmark in that arena. / Computer and Information Science

In this work we present a general duality-theory framework for revenue maximization in additive Bayesian auctions involving multiple items and many bidders whose values for the goods follow arbitrary continuous joint distributions over some multi-dimensional real interval. Although the single-item case has been resolved in a very elegant way by the seminal work of Myerson [1981], optimal solutions involving more items still remain elusive. The framework extends linear programming duality and complementarity to constraints with partial derivatives. The dual system reveals the natural geometric nature of the problem and highlights its connection with the theory of bipartite graph matchings. We demonstrate the power of the framework by applying it to various special monopoly settings where a seller of multiple heterogeneous goods faces a buyer with independent item values drawn from various distributions of interest, to design both exact and approximately optimal selling mechanisms. Previous optimal solutions were only known for up to two and three goods, and a very limited range of distributional priors. The duality framework is used not only for proving optimality, but perhaps more importantly, for deriving the optimal mechanisms themselves. Some of our main results include: the proposal of a simple deterministic mechanism, which we call Straight-Jacket Auction (SJA) and is defined in a greedy, recursive way through natural geometric constraints, for many uniformly distributed goods, where exact optimality is proven for up to six items and general optimality is conjectured; a scheme of sufficient conditions for exact optimality for two-good settings and general independent distributions; a technique for upper-bounding the optimal revenue for arbitrarily many goods, with an application to uniform and exponential priors; and the proof that offering deterministically all items in a single full bundle is the optimal way of selling multiple exponentially i.i.d. items.

Dans cette thèse, nous abordons des problèmes NP-difficiles à l'aide de techniques combinatoires, en se focalisant sur le domaine de la complexité paramétrée. Les principaux problèmes que nous considérons sont les problèmes de Multicoupe et d'Arbre Orienté Couvrant avec Beaucoup de Feuilles. La Multicoupe est une généralisation naturelle du très classique problème de coupe, et consiste à séparer un ensemble donné de paires de sommets en supprimant le moins d'arêtes possible dans un graphe. Le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles consiste à trouver un arbre couvrant avec le plus de feuilles possible dans un graphe dirigé. Les résultats principaux de cette thèse sont les suivants. Nous montrons que le problème de Multicoupe paramétré par la taille de la solution est FPT (soluble à paramètre fixé), c'est-à-dire que l'existence d'une multicoupe de taille $k$ dans un graphe à $n$ sommets peut être décidée en temps $f(k)*poly(n)$. Nous montrons que Multicoupe dans les arbres admet un noyau polynomial, c'est-à-dire est réductible aux instances de taille polynomiale en $k$. Nous donnons un algorithme en temps $O^*(3.72^k)$ pour le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles et le premier algorithme exponentiel exact non trivial (c'est-à-dire meilleur que $2^n$). Nous fournissons aussi un noyau quadratique et une approximation à facteur constant. Ces résultats algorithmiques sont basés sur des résultats combinatoires et des propriétés structurelles qui concernent, entre autres, les décompositions arborescentes, les mineurs, des règles de réduction et les $s-t$ numberings. Nous présentons des résultats combinatoires hors du domaine de la complexité paramétrée: une caractérisation des graphes de cercle Helly comme les graphes de cercle sans diamant induit, et une caractérisation partielle des classes de graphes 2-bel-ordonnées. / This thesis tackles NP-hard problems with combinatorial techniques, focusing on the framework of Fixed-Parameter Tractability. The main problems considered here are Multicut and Maximum Leaf Out-branching. Multicut is a natural generalisation of the cut problem, and consists in simultaneously separating prescribed pairs of vertices by removing as few edges as possible in a graph. Maximum Leaf Out-branching consists in finding a spanning directed tree with as many leaves as possible in a directed graph. The main results of this thesis are the following. We show that Multicut is FPT when parameterized by the solution size, i.e. deciding the existence of a multicut of size $k$ in a graph with $n$ vertices can be done in time $f(k)*poly(n)$. We show that Multicut In Trees admits a polynomial kernel, i.e. can be reduced to instances of size polynomial in $k$. We give an $O^*(3.72^k)$ algorithm for Maximum Leaf Out-branching and the first non-trivial (better than $2^n$) exact algorithm. We also provide a quadratic kernel and a constant factor approximation algorithm. These algorithmic results are based on combinatorial results and structural properties, involving tree decompositions, minors, reduction rules and $s-t$ numberings, among others. We present results obtained with combinatorial techniques outside the scope of parameterized complexity: a characterization of Helly circle graphs as the diamond-free circle graphs, and a partial characterisation of 2-well-quasi-ordered classes of graphs.

Neste trabalho estudamos aspectos algorítmicos do Problema da Cobertura por Sensores. Em linhas gerais, este problema a entrada consiste em uma região a ser monitorada por um conjunto de sensores previamente posicionados, cada qual dotado de bateria com duração limitada, e o objetivo é atribuir a cada sensor um tempo de início, de modo que toda a região seja coberta o maior tempo possível. Focamos nosso estudo no caso unidimensional do problema, chamado Problema da Cobertura de Faixa Restrita, no qual a região a ser monitorada é um intervalo (da reta real). Estudamos diversas variantes, de acordo com os subintervalos que os sensores cobrem (se de tamanhos fixos ou variados), e de acordo com a duração das baterias (se uniformes ou não). Estudamos também o caso preemptivo: quando os sensores podem ser ligados mais de uma vez. Para este último caso, projetamos um algoritmo polinomial bem simples. O Problema da Cobertura de Faixa Restrita é NP-difícil no caso não-preemptivo em que os sensores têm bateria de duração variável. Para este caso, em 2009 Gibson e Varadarajan apresentaram um algoritmo polinomial que provaram ser uma 5-aproximação. Provamos que este algoritmo tem fator de aproximação 4, e mostramos que este fator é justo. Apresentamos também formulações lineares inteiras para este caso, e os resultados computacionais obtidos. / We study the algorithmic aspects of the Sensor Cover Problem. Broadly speaking, in this problem the input consists of a region to be covered by a set of sensors previously positioned, each one powered with a battery of limited duration, and the objective is to assign to each sensor an initial time, so as to cover the given region for as long as possible. We focus our study on the one-dimensional case of the problem, called Restricted Strip Cover Problem, in which the region to be covered is an interval (of the real line). We study several variants, according to the type of the subintervals the sensors cover (if they have fixed length or not), to the duration of the batteries (if uniform or not). We also study the preemptive case: when the sensors can be turned on and off more than once. For this case, we designed a simple polynomial-time algorithm. The Restricted Strip Cover Problem is NP-hard in the non-preemptive case in which the sensors have non-uniform duration batteries. For this case, in 2009 Gibson and Varadarajan designed a polynomial-time algorithm which they proved to be a 5-aproximation. We prove that this algorithm has approximation ratio 4, and show that this ratio is tight. We also present two integer linear formulations for this case, and report on the computational results obtained with this approach.