A cactus graph is a graph in which any two cycles are edge-disjoint. We present a constructive proof of the fact that any plane graph G contains a cactus subgraph C where C contains at least a 1/6 fraction of the tria...
详细信息
ISBN:
(纸本)9783959771009
A cactus graph is a graph in which any two cycles are edge-disjoint. We present a constructive proof of the fact that any plane graph G contains a cactus subgraph C where C contains at least a 1/6 fraction of the triangular faces of G. We also show that this ratio cannot be improved by showing a tight lower bound. Together with an algorithm for linear matroid parity, our bound implies two approximation algorithms for computing "dense planar structures" inside any graph: (i) A 1/6 approximation algorithm for, given any graph G, finding a planar subgraph with a maximum number of triangular faces;this improves upon the previous 1/11-approximation;(ii) An alternate (and arguably more illustrative) proof of the 4/9 approximation algorithm for finding a planar subgraph with a maximum number of edges. Our bound is obtained by analyzing a natural localsearch strategy and heavily exploiting the exchange arguments. Therefore, this suggests the power of localsearch in handling problems of this kind.
Automated algorithm configuration procedures play an increasingly important role in the development and application of algorithms for a wide range of computationally challenging problems. Until very recently, these co...
详细信息
ISBN:
(纸本)9783319503493;9783319503486
Automated algorithm configuration procedures play an increasingly important role in the development and application of algorithms for a wide range of computationally challenging problems. Until very recently, these configuration procedures were limited to optimising a single performance objective, such as the running time or solution quality achieved by the algorithm being configured. However, in many applications there is more than one performance objective of interest. This gives rise to the multi-objective automatic algorithm configuration problem, which involves finding a Pareto set of configurations of a given target algorithm that characterises trade-offs between multiple performance objectives. In this work, we introduce MO-ParamILS, a multiobjective extension of the state-of-the-art single-objective algorithm configuration framework ParamILS, and demonstrate that it produces good results on several challenging bi-objective algorithm configuration scenarios compared to a base-line obtained from using a state-of-the-art single-objective algorithm configurator.
The propositional satisfiability problem (SAT) is one of the most studied NP-complete problems in computer science [1]. Some of the best known methods for solving certain types of SAT instances are stochastic local se...
详细信息
ISBN:
(纸本)9783642293498;9783642293504
The propositional satisfiability problem (SAT) is one of the most studied NP-complete problems in computer science [1]. Some of the best known methods for solving certain types of SAT instances are stochastic local search algorithms [6]. Pure Additive Weighting Scheme (PAWS) is now one of the best dynamic local search algorithms in the additive weighting category [7]. Fang et. al [3] introduce the island confinement method to speed up the local search algorithms. In this paper, we incorporate the island confinement method into PAWS to speed up PAWS. We show through experiments that, the resulted algorithm, PAWSI, betters PAWS in solving the hard graph coloring and AIS problems. abstract environment.
Large-scale optimisation problems are usually hard to solve optimally. Approximation algorithms such as metaheuristics, able to quickly find sub-optimal solutions, are often preferred. This thesis focuses on multi-obj...
详细信息
Large-scale optimisation problems are usually hard to solve optimally. Approximation algorithms such as metaheuristics, able to quickly find sub-optimal solutions, are often preferred. This thesis focuses on multi-objective localsearch (MOLS) algorithms, metaheuristics able to deal with the simultaneous optimisation of multiple criteria. As many algorithms, metaheuristics expose many parameters that significantly impact their performance. These parameters can be either predicted and set before the execution of the algorithm, or dynamically modified during the execution itself. While in the last decade many advances have been made on the automatic design of algorithms, the great majority of them only deal with single-objective algorithms and the optimisation of a single performance indicator such as the algorithm running time or the final solution quality. In this thesis, we investigate the relations between automatic algorithm design and multi-objective optimisation, with an application on MOLS algorithms. We first review possible MOLS strategies ans parameters and present a general, highly configurable, MOLS framework. We also propose MO-ParamILS, an automatic configurator specifically designed to deal with multiple performance indicators. Then, we conduct several studies on the automatic offline design of MOLS algorithms on multiple combinatorial bi-objective problems. Finally, we discuss two online extensions of classical algorithm configuration: first the integration of parameter control mechanisms, to benefit from having multiple configuration predictions; then the use of configuration schedules, to sequentially use multiple configurations.
We investigate randomized processes underlying load balancing based on the multiple-choice paradigm: m balls have to be placed in n bins, and each ball can be placed into one out of 2 randomly selected bins. The aim i...
详细信息
ISBN:
(纸本)3540407707
We investigate randomized processes underlying load balancing based on the multiple-choice paradigm: m balls have to be placed in n bins, and each ball can be placed into one out of 2 randomly selected bins. The aim is to distribute the balls as evenly as possible among the bins. Previously, it was known that a simple process that places the balls one by one in the least loaded bin can achieve a maximum load of m/n + Theta(log log n) with high probability. Furthermore, it was known that it is possible to achieve (with high probability) a maximum load of at most [m/n] + 1 using maximum flow computations. In this paper, we extend these results in several aspects. First of all, we show that if m greater than or equal to c n log n for some sufficiently large c, then a perfect distribution of balls among the bins can be achieved (i.e., the maximum load is [m/n]) with high probability. The bound for m is essentially optimal, because it is known that if m less than or equal to c' n log n for some sufficiently small constant c', the best possible maximum load that can be achieved is [m/n] + 1 with high probability. Next, we analyze a simple, randomized load balancing process based on a localsearch paradigm. Our first result here is that this process always converges to a best possible load distribution. Then, we study the convergence speed of the process. We show that if m is sufficiently large compared to n, then no matter with which ball distribution the system starts, if the imbalance is Delta, then the process needs only Delta(.)n(O(1)) steps to reach a perfect distribution, with high probability. We also prove a similar result for m approximate to n, and show that if m = O(n log n/log log n), then an optimal load distribution (which has the maximum load of [m/n] + 1) is reached by the random process after a polynomial number of steps, with high probability.
This thesis presents new solution approaches for land leveling, using optimal earthmoving vehicle routing. It addresses the Shortest Route Cut and Fill Problem (SRCFP) developed by Henderson, Vaughan, Wakefield and J...
详细信息
This thesis presents new solution approaches for land leveling, using optimal earthmoving vehicle routing. It addresses the Shortest Route Cut and Fill Problem (SRCFP) developed by Henderson, Vaughan, Wakefield and Jacobson [2000]. The SRCFP is a discrete optimization search problem, proven to be NP-hard. The SRCFP describes the process of reshaping terrain through a series of cuts and fills. This process is commonly done when leveling land for building homes, parking lots, etc. The model used to represent this natural system is a variation of the Traveling Salesman Problem. The model is designed to limit the time needed to operate expensive, earthmoving vehicles. The model finds a vehicle route that minimizes the total time required to travel between cut and fill locations while leveling the site. An optimal route is a route requiring the least amount of travel time for an individual earthmoving vehicle.
This research addresses the SRCFP by evaluating minimum function values across an unknown response surface. The result is a cost estimating strategy that provides construction planners a strategy for contouring terrain as cheaply as possible. Other applications of this research include rapid runway repair, and robotic vehicle routing.
Haxell's condition [16] is a natural hypergraph analog of Hall's condition, which is a well-known necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell'...
详细信息
ISBN:
(纸本)9781510819672
Haxell's condition [16] is a natural hypergraph analog of Hall's condition, which is a well-known necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell's condition holds it forces the existence of a perfect matching in the bipartite hypergraph. Unlike in graphs, however, there is no known polynomial time algorithm to find the hypergraph perfect matching that is guaranteed to exist when Haxell's condition is satisfied. We prove the existence of an efficient algorithm to find perfect matchings in bipartite hypergraphs whenever a stronger version of Haxell's condition holds. Our algorithm can be seen as a generalization of the classical Hungarian algorithm for finding perfect matchings in bipartite graphs. The techniques we use to achieve this result could be of use more generally in other combinatorial problems on hypergraphs where disjointness structure is crucial, e.g. Set Packing.
This paper considers a context- and user-aware approach to the tour planning in Geographic Information Systems. We regard the following scenario: a person with specific preferences and a fixed amount of time is visiti...
详细信息
ISBN:
(纸本)9781581135916
This paper considers a context- and user-aware approach to the tour planning in Geographic Information Systems. We regard the following scenario: a person with specific preferences and a fixed amount of time is visiting a foreign place of interest. Therefore spatial as well as user specific information is modeled as a multimodally attributed digraph structure, where nodes represent the points of interest and arcs the user optimal paths between them. The goal is to find a set of nodes and arcs representing a round trip that is best satisfying the priorities of the user. This results in an Enhanced Profitable Tour Problem (EPTP), which is - as a generalization of the well-known Traveling Salesman Problem (TSP) - an NP-hard optimization problem. In this article, we introduce an efficient algorithm for this problem and discuss the modeling and implementation details.
暂无评论