Dissertations / Theses on the topic 'Geometric Covering and Packing'
To see the other types of publications on this topic, follow the link: Geometric Covering and Packing.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Geometric Covering and Packing.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Song, Yongqiang. "Improved Approximation Algorithms for Geometric Packing Problems With Experimental Evaluation." Thesis, University of North Texas, 2003. https://digital.library.unt.edu/ark:/67531/metadc4355/.
Full textAbstract:
Geometric packing problems are NP-complete problems that arise in VLSI design. In this thesis, we present two novel algorithms using dynamic programming to compute exactly the maximum number of k x k squares of unit size that can be packed without overlap into a given n x m grid. The first algorithm was implemented and ran successfully on problems of large input up to 1,000,000 nodes for different values. A heuristic based on the second algorithm is implemented. This heuristic is fast in practice, but may not always be giving optimal times in theory. However, over a wide range of random data this version of the algorithm is giving very good solutions very fast and runs on problems of up to 100,000,000 nodes in a grid and different ranges for the variables. It is also shown that this version of algorithm is clearly superior to the first algorithm and has shown to be very efficient in practice.
2
Bezdek, Andras. "Packing and covering problems /." The Ohio State University, 1986. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487266691095136.
Full text
3
Chen, Zhibin, and 陳智斌. "On various packing and covering problems." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2009. http://hub.hku.hk/bib/B43085520.
Full text
4
Chen, Zhibin. "On various packing and covering problems." Click to view the E-thesis via HKUTO, 2009. http://sunzi.lib.hku.hk/hkuto/record/B43085520.
Full text
5
Nielsen, Torben Noerup. "Combinatorial Bin Packing Problems." Diss., The University of Arizona, 1985. http://hdl.handle.net/10150/187536.
Full textAbstract:
In the past few years, there has been a strong and growing interest in evaluating the expected behavior of what we call combinatorial bin packing problems. A combinatorial bin packing problem consists of a number of items of various sizes and value ratios (value per unit of size) along with a collection of bins of fixed capacity into which the items are to be packed. The packing must be done in such a way that the sum of the sizes of the items into a given bin does not exceed the capacity of that bin. Moreover, an item must either be packed into a bin in its entirety or not at all: this "all or nothing" requirement is why these problems are characterized as being combinatorial. The objective of the packing is to optimize a given criterion Junction. Here optimize means either maximize or minimize, depending on the problem. We study two problems that fit into this framework: the Knapsack Problem and the Minimum Sum of Squares Problem. Both of these problems are known to be in the class of NP-hard problems and there is ample reason to suspect that these problems do not admit of efficient exact solution. We obtain results concerning the performance of heuristics under the assumption that the inputs are random samples from some distribution. For the Knapsack Problem, we develop four heuristics, two of which are on-line and two off-line. All four heuristics are shown to be asymptotically optimal in expectation when the item sizes and value ratios are assumed to be independent and uniform. One heuristic is shown to be asymptotically optimal in expectation when the item sizes are uniformly distributed and the value ratios are exponentially distributed. The amount of time required by these heuristics is no more than proportional to the amount of time required to sort the items in order of nonincreasing value ratios. For the Minimum Sum of Squares Problem, we develop two heuristics, both of which are off-line. Both of these heuristics are shown to be asymptotically optimal in expectation when the sizes of the items input are assumed uniformly distributed.
6
Stardom, John. "Metaheuristics and the search for covering and packing arrays." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2001. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/MQ61608.pdf.
Full text
7
Pasha, Arfath. "Geometric bin packing algorithm for arbitrary shapes." [Gainesville, Fla.] : University of Florida, 2003. http://purl.fcla.edu/fcla/etd/UFE0000907.
Full text
8
Chang, Engder. "Neural computing for minimum set covering and gate-packing problems." Case Western Reserve University School of Graduate Studies / OhioLINK, 1993. http://rave.ohiolink.edu/etdc/view?acc_num=case1056655652.
Full text
9
許眞眞 and Zhenzhen Xu. "A min-max theorem on packing and covering cycles in graphs." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2002. http://hub.hku.hk/bib/B31226966.
Full text
10
Xu, Zhenzhen. "A min-max theorem on packing and covering cycles in graphs /." Hong Kong : University of Hong Kong, 2002. http://sunzi.lib.hku.hk/hkuto/record.jsp?B25155301.
Full text
11
Martinez, Adam P. "A Geometric Tiling Algorithm for Approximating Minimal Covering Sets." University of Akron / OhioLINK, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=akron1321028719.
Full text
12
Kovaleva, Sofia. "Approximation of geometric set packing and hitting set problems." [Maastricht : Maastricht : Universiteit Maastricht] ; University Library, Maastricht University [Host], 2003. http://arno.unimaas.nl/show.cgi?fid=7461.
Full text
13
Prädel, Lars Dennis [Verfasser]. "Approximation Algorithms for Geometric Packing Problems / Lars Dennis Prädel." Kiel : Universitätsbibliothek Kiel, 2013. http://d-nb.info/1031190503/34.
Full text
14
Lü, Lin, and 吕琳. "Geometric optimization for shape processing." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2011. http://hub.hku.hk/bib/B46483640.
Full text
15
Bossenger, Wayne. "2D irregular strip packing at Kohler signs." Thesis, Stellenbosch : Stellenbosch University, 2014. http://hdl.handle.net/10019.1/96129.
Full textAbstract:
Thesis (MCom)--Stellenbosch University, 2014.ENGLISH ABSTRACT: Kohler Signs (PTY) Ltd is a sign production company located in Cape Town, South Africa. They manufacture and install signs for the City of Cape Town and private companies as well as manufacture advertisement signs to be placed on vehicles. Road signs consist of steel sheets that are cut and bent to the appropriate size and frame, and an image design, which is cut from re ective vinyl, are applied to the bent steel sheet. The image design consists of various letters, numbers and symbols which are categorised as irregular items. When these irregular items are combined in a distinctive way, with the use of di erent coloured vinyl, they convey a message to the road user which may be to yield for pedestrians crossing the street, or indicate to the road user the various highway exits that exist on the interchange ahead. These irregular items are placed upon re ective vinyl for cutting which results in vinyl o cuts that are wasted. The focus of this thesis is to minimise the waste incurred by placing these irregular items upon the vinyl in an optimal and timely manner for industry use. The vinyl printer, which cuts the irregular items out of the vinyl, consists of a xed width and is only limited in height by the vinyl itself. Thus, this problem may be described as a Two Dimensional Irregular Strip Packing Problem. These irregular items have only a few possible heights for each type of irregular item packed, which allows these irregular items to be packed as a level packing problem. The items are packed within levels as though they are regular items with the assistance of a prede ned rule-set. In this thesis various packing algorithms and image processing methodologies from the literature are researched and used to develop a new packing algorithm for this speci c problem. The newly developed algorithm is put through various benchmarks to test its performance. Some of these benchmarks are procured from Kohler Signs themselves, whereas others are randomly generated under certain conditions. These benchmarks reveal that the newly developed algorithm performs better for both the minimisation of waste and the minimisation of algorithm running time than the tried and trusted techniques utilised in industry by Kohler Signs.
AFRIKAANSE OPSOMMING: Kohler Signs (EDMS) Bpk is 'n padteken produksie maatskappy gele e in Kaapstad, Suid-Afrika. Hulle vervaardig en installeer tekens vir die Stad van Kaapstad en privaat maatskappye, sowel as advertensietekens wat op voertuie geplaas word. Padtekens bestaan uit staalplate wat gesny en gebuig word tot die toepaslike grootte en vorm. 'n Beeldontwerp, wat gesny is uit re ektiewe viniel, word vasgesit op die gebuigde staalplaat. Die beeldontwerp bestaan uit verskeie letters, getalle en simbole wat geklassi seer word as onre elmatige items. Wanneer hierdie onre elmatige items gekombineer word op 'n eiesoortige manier, met die gebruik van verskillende kleure viniel, dra hulle 'n boodskap oor aan die padgebruiker, soos byvoorbeeld om toe te gee aan voetgangers by 'n voetoorgang of dit dui aan die padgebruiker die verskillende snelweguitgange wat bestaan op die wisselaar wat voorl^e. Hierdie onre elmatige items word op re ektiewe viniel geplaas en uitgesny wat lei tot die vermorsing van stukkies viniel. Die fokus van hierdie tesis is om die onre elmatige items op 'n optimale en tydige wyse vir gebruik in industrie, op die viniel te plaas sodat die afval stukkies viniel geminimeer word. Die vinieldrukker, wat die onre elmatige items sny uit die viniel, bestaan uit 'n vaste wydte en is slegs beperk in hoogte deur die viniel self. Dus kan hierdie probleem beskryf word as 'n Twee-Dimensionele Onre elmatige Strookverpakkingsprobleem. Hierdie onre elmatige items het slegs 'n paar moontlike hoogtes vir elke tipe van onre elmatige item wat verpak word, wat dit moontlik maak om hierdie onre elmatige items te verpak as 'n strook verpakkingsprobleem. Die items word met behulp van 'n gede nieerde stel re els binne vlakke verpak asof hulle re elmatige items is. In hierdie tesis is verskeie verpakkingsalgoritmes en beeldverwerkingsmetodes van die literatuur nagevors en gebruik om 'n nuwe verpakkingsalgoritme vir hierdie spesi eke probleem te ontwikkel. Die nuut ontwikkelde algoritme se prestasie is deur middel van verskeie normbepalingsvoorbeelde getoets. Sommige van hierdie normbepalingsvoorbeelde is verkry van Kohler Signs self, terwyl ander lukraak gegenereer is onder sekere voorwaardes. Hierdie normbepalingsvoorbeelde toon dat die nuut ontwikkelde algoritme beter vaar as die beproefde tegnieke gebruik in industrie deur Kohler Signs vir beide die minimering van vermorsde viniel sowel as die minimering van die algoritme se uitvoertyd.
16
Schlipf, Lena Marie [Verfasser]. "Stabbing and Covering Geometric Objects in the Plane / Lena Marie Schlipf." Berlin : Freie Universität Berlin, 2014. http://d-nb.info/1047336782/34.
Full text
17
Spirova, Margarita. "Discrete Geometry in Normed Spaces." Doctoral thesis, Universitätsbibliothek Chemnitz, 2010. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-62896.
Full textAbstract:
This work refers to ball-intersections bodies as well as covering, packing, and kissing problems related to balls and spheres in normed spaces. A quick introduction to these topics and an overview of our results is given in Section 1.1 of Chapter 1. The needed background knowledge is collected in Section 1.2, also in Chapter 1. In Chapter 2 we define ball-intersection bodies and investigate special classes of them: ball-hulls, ball-intersections, equilateral ball-polyhedra, complete bodies and bodies of constant width. Thus, relations between the ball-hull and the ball-intersection of a set are given. We extend a minimal property of a special class of equilateral ball-polyhedra, known as Theorem of Chakerian, to all normed planes. In order to investigate bodies of constant width, we develop a concept of affine orthogonality, which is new even for the Euclidean subcase. In Chapter 2 we solve kissing, covering, and packing problems. For a given family of circles and lines we find at least one, but for some families even all circles kissing all the members of this family. For that reason we prove that a strictly convex, smooth normed plane is a topological Möbius plane. We give an exact geometric description of the maximal radius of all homothets of the unit disc that can be covered by 3 or 4 translates of it. Also we investigate configurations related to such coverings, namely a regular 4-covering and a Miquelian configuration of circles. We find the concealment number for a packing of translates of the unit ball.
18
Bhowmick, Santanu. "Multi-covering problems and their variants." Diss., University of Iowa, 2017. https://ir.uiowa.edu/etd/5418.
Full textAbstract:
In combinatorial optimization, covering problems are those problems where given a ground set and a family of subsets of the ground set, the objective is to find a minimum cost set of subsets whose union contains the ground set. We consider covering problems in the context of Computational Geometry, which is a subfield of Computer Science that deals with problems associated with geometric objects such as points, lines, disks, polygons etc. In particular, geometric covering is an active research area, where the ground set and the family of subsets are induced by geometric objects. Covering problems in combinatorial optimizations often have a geometric analogue that arises naturally, and though such problems remain NP-hard, it is often possible to exploit the geometric properties of the set system to obtain better approximation algorithms.
In this work, the fundamental problem that we consider is a generalization of geometric covering, where each element in the ground set may need to covered by more than one subset. To be precise, the problem is defined as follows: given two sets of points X, Y and a coverage function κ : X → Z+ ∪ {0}, construct balls centered on the points in Y such that each point in X is covered by at least κ(x) distinct balls. The objective in this problem is to minimize the total cost, which is a function of the radii of the balls. This problem is termed as the metric multi-cover (MMC) problem.
We first consider version of the MMC problem where κ(x) = 1 for all clients, i.e. the 1-covering case. The known results that give a constant factor approximation for this problem are variations of LP-based primal-dual algorithm. We use a modified local search technique, motivated by geometric idea, to derive a simple, constant- factor approximation for this problem in Chapter 2.
We then look at the MMC problem where the point sets X,Y are in the Euclidean plane, and each client x ∈ X needs to be covered by at least κ(x) distinct disks centered on the points in Y . In Chapter 4, we give the first polynomial time constant factor approximation for this problem, in which the constant is independent of the coverage function κ. Our solution also has an incremental property, which allows the algorithm to handle increases in the coverage requirement by increasing the radii of the current server disks, without affecting the approximation factor.
In the next problem, we move from the Euclidean plane to arbitrary metric spaces where we consider the uniform MMC problem. In this problem, each client x has the demand κ(x) = k, where k > 0 is an integer. We give the first constant factor approximation (independent of k) for this problem. The key contribution that led to this result is the formulation of a partitioning scheme of the servers in the uniform MMC problem, that reduces the uniform MMC problem to k instances of 1-covering problem, while preserving the optimality of the solution to a constant multiplicative factor. We present the partitioning scheme as an independent result in Chapter 5, which we then use to solve the uniform MMC problem in Chapter 6.
The MMC problem with arbitrary coverage function κ is then considered in Chapter 7. The key challenge that the non-uniform version presents is that the symmetry of the server partitioning scheme breaks down as the coverage demands of clients are independent of each other. We present a constant factor algorithm for this problem in Chapter 7.
The last problem that we consider is the t-MMC problem, which is a restricted version of the uniform MMC problem. The objective is to compute a cover in which each client is covered by at least k distinct server disks, using atmost t server disks in total. This problem is a generalization of the clustering problem (where k = 1), and to our knowledge this is the first time this generalization has been considered. We give a constant factor approximation for this problem in Chapter 8.
19
Khan, Arindam. "Approximation algorithms for multidimensional bin packing." Diss., Georgia Institute of Technology, 2015. http://hdl.handle.net/1853/54371.
Full textAbstract:
The bin packing problem has been the corner stone of approximation algorithms and has been extensively studied starting from the early seventies.
In the classical bin packing problem, we are given a list of real numbers in the range (0, 1], the goal is to place them in a minimum number of bins so that no bin holds numbers summing to more than 1.
In this thesis we study approximation algorithms for three generalizations of bin packing: geometric bin packing, vector bin packing and weighted bipartite edge coloring.
In two-dimensional (2-D) geometric bin packing, we are given a collection of rectangular items to be packed into a minimum number of unit size square bins. Geometric packing has vast applications in cutting stock, vehicle loading, pallet packing, memory allocation and several other logistics and robotics related problems.
We consider the widely studied orthogonal packing case, where the items must be placed in the bin such that their sides are parallel to the sides of the bin.
Here two variants are usually studied, (i) where the items cannot be rotated, and (ii) they can be rotated by 90 degrees. We give a polynomial time algorithm with an asymptotic approximation ratio of
$\ln(1.5) + 1 \approx 1.405$ for the versions with and without rotations.
We have also shown the limitations of rounding based algorithms, ubiquitous in bin packing algorithms. We have shown that any algorithm that
rounds at least one side of each large item to some number in a constant size collection values chosen independent of the problem instance, cannot achieve an asymptotic approximation ratio better than 3/2.
In d-dimensional vector bin packing (VBP), each item is a d-dimensional vector that needs to be packed into unit vector bins. The problem is of great significance in resource constrained scheduling and also appears in recent virtual machine placement in cloud computing. Even in two dimensions, it has novel applications in layout design, logistics, loading and scheduling problems.
We obtain a polynomial time algorithm with an asymptotic approximation ratio of $\ln(1.5) + 1 \approx 1.405$ for 2-D VBP. We also obtain a polynomial time algorithm with almost tight (absolute) approximation ratio of $1+\ln(1.5)$ for 2-D VBP.
For $d$ dimensions, we give a polynomial time algorithm with an asymptotic approximation ratio of $\ln(d/2) + 1.5 \approx \ln d+0.81$.
We also consider vector bin packing under resource augmentation. We give a polynomial time algorithm that packs vectors into $(1+\epsilon)Opt$ bins when we allow augmentation in (d - 1) dimensions and $Opt$ is the minimum number of bins needed to pack the vectors into (1,1) bins.
In weighted bipartite edge coloring problem, we are given an edge-weighted bipartite graph $G=(V,E)$ with weights $w: E \rightarrow [0,1]$. The task is to find a proper weighted coloring of the edges with as few colors as possible. An edge coloring of the weighted graph is called a proper weighted coloring if the sum of the weights of the edges incident to a vertex of any color is at most one. This problem is motivated by rearrangeability of 3-stage Clos networks which is very useful in various applications in interconnected networks and routing.
We show a polynomial time approximation algorithm that returns a proper weighted coloring with at most $\lceil 2.2223m \rceil$ colors where $m$ is the minimum number of unit sized bins needed to pack the weight of all edges incident at any vertex.
We also show that if all edge weights are $>1/4$ then $\lceil 2.2m \rceil$ colors are sufficient.
20
Tiwari, Santosh. "Development and integration of geometric and optimization algorithms for packing and layout design." Connect to this title online, 2009. http://etd.lib.clemson.edu/documents/1252423776/.
Full text
21
Asgeirsson, Agni. "On-line algorithms for bin-covering problems with known item distributions." Diss., Georgia Institute of Technology, 2014. http://hdl.handle.net/1853/53413.
Full textAbstract:
This thesis focuses on algorithms solving the on-line Bin-Covering problem, when
the items are generated from a known, stationary distribution. We introduce the
Prospect Algorithm. The main idea behind the Prospect Algorithm is to use
information on the item distribution to estimate how easy it will be to fill a bin with small overfill as a function of the empty space left in it. This estimate is then used to determine where to place the items, so that all active bins either stay easily fillable, or are finished with small overfill. We test the performance of the algorithm by simulation, and discuss how it can be modified to cope with additional constraints and extended to solve the Bin-Packing problem as well. The Prospect Algorithm is then adapted to achieve perfect packing, yielding a new version, the Prospect+ Algorithm, that is a slight but consistent improvement. Next, a Markov Decision Process formulation is used to obtain an optimal Bin-Covering algorithm to compare with the Prospect Algorithm. Even though the optimal algorithm can only be applied to limited (small) cases, it gives useful insights that lead to another modification of the Prospect Algorithm. We also discuss two relaxations of the on-line constraint, and describe how algorithms that are based on solving the Subset-Sum problem are used to
tackle these relaxed problems. Finally, several practical issues encountered when using the Prospect Algorithm in the real-world are analyzed, a computationally efficient way of doing the background calculations needed for the Prospect Algorithm is described, and the three versions of the Prospect Algorithm developed in this thesis are compared.
22
Rolfes, Jan Hendrik [Verfasser], Frank [Gutachter] Vallentin, David [Gutachter] Gross, and Cordian [Gutachter] Riener. "Convex Optimization Techniques for Geometric Covering Problems / Jan Hendrik Rolfes ; Gutachter: Frank Vallentin, David Gross, Cordian Riener." Köln : Universitäts- und Stadtbibliothek Köln, 2019. http://d-nb.info/1193649455/34.
Full text
23
Wierz, Andreas [Verfasser]. "Algorithms and Complexity Results for Packing and Covering Problems and Robust Dynamic Network Flows under Primal-Dual Aspects / Andreas Wierz." München : Verlag Dr. Hut, 2018. http://d-nb.info/1156510368/34.
Full text
24
Heydrich, Sandy [Verfasser], and Rob van [Akademischer Betreuer] Stee. "A tale of two packing problems : improved algorithms and tighter bounds for online bin packing and the geometric knapsack problem / Sandy Heydrich ; Betreuer: Rob van Stee." Saarbrücken : Saarländische Universitäts- und Landesbibliothek, 2018. http://d-nb.info/1164012193/34.
Full text
25
Freitas, Lucas Ismaily Bezerra 1987. "A conjectura de Tuza sobre triângulos em grafos." [s.n.], 2014. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275522.
Full textAbstract:
Orientador: Orlando LeeDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-25T17:05:58Z (GMT). No. of bitstreams: 1 Freitas_LucasIsmailyBezerra_M.pdf: 2067916 bytes, checksum: 77f11deab9d862fe9a10de2df94b447c (MD5) Previous issue date: 2014
Resumo: Neste trabalho estudamos a conjectura de Tuza, que relaciona cobertura mínima de triângulos por arestas com empacotamento máximo de triângulos aresta-disjuntos em grafos. Em 1981, Tuza conjecturou que para todo grafo, o número máximo de triângulos aresta-disjuntos é no máximo duas vezes o tamanho de uma cobertura mínima de triângulos por arestas. O caso geral da conjectura continua aberta. Contudo, diversas tentativas de prová-la surgiram na literatura, obtendo resultados para várias classes de grafos. Nesta dissertação, nós apresentamos os principais resultados obtidos da conjectura de Tuza. Atualmente, existem várias versões da conjectura. Contudo, ressaltamos que nosso foco está na conjectura aplicada a grafos simples. Apresentamos também uma conjectura que se verificada, implica na veracidade da conjectura de Tuza. Demonstramos ainda que se G é um contra-exemplo mínimo para a conjectura de Tuza, então G é 4-conexo. Deduzimos desse resultado que a conjectura de Tuza é válida para grafos sem minor do K_5
Abstract: In this thesis we study the conjecture of Tuza, which relates covering of triangles (by edges) with packing of edge-disjoint triangles in graphs. In 1981, Tuza conjectured that for any graph, the maximum number of edge-disjoint triangles is at most twice the size of a minimum cover of triangles by edges. The general case of the conjecture remains open. However, several attempts to prove it appeared in the literature, which contain results for several classes of graphs. In this thesis, we present the main known results for the conjecture of Tuza. Currently, there are several versions of Tuza's conjecture. Nevertheless, we emphasize that our focus is on conjecture applied to simple graphs. We also present a conjecture that, if verified, implies the validity of the conjecture of Tuza. We also show that if G is a mininum counterexample to the conjecture of Tuza, then G is 4-connected. We can deduce from this result that the conjecture of Tuza is valid for graphs with no K_5 minor
Mestrado
Ciência da Computação
Mestre em Ciência da Computação
26
Surber, Wesley M. "Restricted and Unrestricted Coverings of Complete Bipartite Graphs with Hexagons." Digital Commons @ East Tennessee State University, 2013. https://dc.etsu.edu/etd/1136.
Full textAbstract:
A minimal covering of a graph G with isomorphic copies of graph H is a set {H1, H2, H3, ... , Hn} where Hi is isomorphic to H, the vertex set of Hi is a subset of G, the edge set of G is a subset of the union of Hi's, and the cardinality of the union of Hi's minus G is minimum. Some studies have been made of covering the complete graph in which case an added condition of the edge set of Hi is the subset of the edge set of G for all i which implies no additional restrictions. However, if G is not the complete graph, then this condition may have implications. We will give necessary and sufficient conditions for minimal coverings of complete bipartite graph with 6-cycles, which we call minimal unrestricted coverings. We also give necessary and sufficient conditions for minimal coverings of the complete bipartite graph with 6-cycles with the added condition the edge set of Hi is a subset of G for all i, and call these minimal restricted coverings.
27
Moustrou, Philippe. "Geometric distance graphs, lattices and polytopes." Thesis, Bordeaux, 2017. http://www.theses.fr/2017BORD0802/document.
Full textAbstract:
Un graphe métrique G(X;D) est un graphe dont l’ensemble des sommets est l’ensemble X des points d’un espace métrique (X; d), et dont les arêtes relient les paires fx; yg de sommets telles que d(x; y) 2 D. Dans cette thèse, nous considérons deux problèmes qui peuvent être interprétés comme des problèmes de graphes métriques dans Rn. Premièrement, nous nous intéressons au célèbre problème d’empilements de sphères, relié au graphe métrique G(Rn; ]0; 2r[) pour un rayon de sphère r donné. Récemment, Venkatesh a amélioré d’un facteur log log n la meilleure borne inférieure connue pour un empilement de sphères donné par un réseau, pour une suite infinie de dimensions n. Ici nous prouvons une version effective de ce résultat, dans le sens où l’on exhibe, pour la même suite de dimensions, des familles finies de réseaux qui contiennent un réseaux dont la densité atteint la borne de Venkatesh. Notre construction met en jeu des codes construits sur des corps cyclotomiques, relevés en réseaux grâce à un analogue de la Construction A. Nous prouvons aussi un résultat similaire pour des familles de réseaux symplectiques. Deuxièmement, nous considérons le graphe distance-unité G associé à une norme k_k. Le nombre m1 (Rn; k _ k) est défini comme le supremum des densités réalisées par les stables de G. Si la boule unité associée à k _ k pave Rn par translation, alors il est aisé de voir que m1 (Rn; k _ k) > 1 2n . C. Bachoc et S. Robins ont conjecturé qu’il y a égalité. On montre que cette conjecture est vraie pour n = 2 ainsi que pour des régions de Voronoï de plusieurs types de réseaux en dimension supérieure, ceci en se ramenant à la résolution de problèmes d’empilement dans des graphes discretsA distance graph G(X;D) is a graph whose set of vertices is the set of points X of a metric space (X; d), and whose edges connect the pairs fx; yg such that d(x; y) 2 D. In this thesis, we consider two problems that may be interpreted in terms of distance graphs in Rn. First, we study the famous sphere packing problem, in relation with thedistance graph G(Rn; (0; 2r)) for a given sphere radius r. Recently, Venkatesh improved the best known lower bound for lattice sphere packings by a factor log log n for infinitely many dimensions n. We prove an effective version of this result, in the sense that we exhibit, for the same set of dimensions, finite families of lattices containing a lattice reaching this bound. Our construction uses codes over cyclotomic fields, lifted to lattices via Construction A. We also prove a similar result for families of symplectic lattices. Second, we consider the unit distance graph G associated with a norm k _ k. The number m1 (Rn; k _ k) is defined as the supremum of the densities achieved by independent sets in G. If the unit ball corresponding with k _ k tiles Rn by translation, then it is easy to see that m1 (Rn; k _ k) > 1 2n . C. Bachoc and S. Robins conjectured that the equality always holds. We show that this conjecture is true for n = 2 and for several Voronoï cells of lattices in higher dimensions, by solving packing problems in discrete graphs
28
Sheppard, Nicholas Paul. "Self-Reduction for Combinatorial Optimisation." Thesis, The University of Sydney, 2001. http://hdl.handle.net/2123/797.
Full textAbstract:
This thesis presents and develops a theory of self-reduction. This process is used to map instances of combinatorial optimisation problems onto smaller, more easily solvable instances in such a way that a solution of the former can be readily re-constructed, without loss of information or quality, from a solution of the latter. Self-reduction rules are surveyed for the Graph Colouring Problem, the Maximum Clique Problem, the Steiner Problem in Graphs, the Bin Packing Problem and the Set Covering Problem. This thesis introduces the problem of determining the maximum sequence of self-reductions on a given structure, and shows how the theory of confluence can be adapted from term re-writing to solve this problem by identifying rule sets for which all maximal reduction sequences are equivalent. Such confluence results are given for a number of reduction rules on problems on discrete systems. In contrast, NP-hardness results are also presented for some reduction rules. A probabilistic analysis of self-reductions on graphs is performed, showing that the expected number of self-reductions on a graph tends to zero as the order of the graph tends to infinity. An empirical study is performed comparing the performance of self-reduction, graph decomposition and direct methods of solving the Graph Colouring and Set Covering Problems. The results show that self-reduction is a potentially valuable, but sometimes erratic, method of finding exact solutions to combinatorial problems.
29
Sheppard, Nicholas Paul. "Self-Reduction for Combinatorial Optimisation." University of Sydney. Computer Science, 2001. http://hdl.handle.net/2123/797.
Full textAbstract:
This thesis presents and develops a theory of self-reduction. This process is used to map instances of combinatorial optimisation problems onto smaller, more easily solvable instances in such a way that a solution of the former can be readily re-constructed, without loss of information or quality, from a solution of the latter. Self-reduction rules are surveyed for the Graph Colouring Problem, the Maximum Clique Problem, the Steiner Problem in Graphs, the Bin Packing Problem and the Set Covering Problem. This thesis introduces the problem of determining the maximum sequence of self-reductions on a given structure, and shows how the theory of confluence can be adapted from term re-writing to solve this problem by identifying rule sets for which all maximal reduction sequences are equivalent. Such confluence results are given for a number of reduction rules on problems on discrete systems. In contrast, NP-hardness results are also presented for some reduction rules. A probabilistic analysis of self-reductions on graphs is performed, showing that the expected number of self-reductions on a graph tends to zero as the order of the graph tends to infinity. An empirical study is performed comparing the performance of self-reduction, graph decomposition and direct methods of solving the Graph Colouring and Set Covering Problems. The results show that self-reduction is a potentially valuable, but sometimes erratic, method of finding exact solutions to combinatorial problems.
30
Wierz, Andreas [Verfasser], Britta [Akademischer Betreuer] Peis, Arie Marinus [Akademischer Betreuer] Koster, and Martin [Akademischer Betreuer] Skutella. "Algorithms and complexity results for packing and covering problems and robust dynamic network flows under primal-dual aspects / Andreas Wierz ; Britta Peis, Arie Marinus Koster, Martin Skutella." Aachen : Universitätsbibliothek der RWTH Aachen, 2018. http://d-nb.info/1169314716/34.
Full text
31
Xia, Yan. "Packings and Coverings of Complete Graphs with a Hole with the 4-Cycle with a Pendant Edge." Digital Commons @ East Tennessee State University, 2013. https://dc.etsu.edu/etd/1173.
Full textAbstract:
In this thesis, we consider packings and coverings of various complete graphs with the 4-cycle with a pendant edge. We consider both restricted and unrestricted coverings. Necessary and sufficient conditions are given for such structures for (1) complete graphs Kv, (2) complete bipartite graphs Km,n, and (3) complete graphs with a hole K(v,w).
32
Newberry, Simon David. "An experimental investigation into the influence of geometric properties and construction techniques on the packing density of rock armour layers for coastal engineering structures." Thesis, Imperial College London, 2004. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.406440.
Full text
33
Muller, Carole. "Minor-closed classes of graphs: Isometric embeddings, cut dominants and ball packings." Doctoral thesis, Universite Libre de Bruxelles, 2021. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/331629.
Full textAbstract:
Une classe de graphes est close par mineurs si, pour tout graphe dans la classe et tout mineur de ce graphe, le mineur est ́egalement dans la classe. Par un fameux th ́eor`eme de Robertson et Seymour, nous savons que car- act ́eriser une telle classe peut ˆetre fait `a l’aide d’un nombre fini de mineurs exclus minimaux. Ceux-ci sont des graphes qui n’appartiennent pas `a la classe et qui sont minimaux dans le sens des mineurs pour cette propri ́et ́e.Dans cette thèse, nous étudions trois problèmes à propos de classes de graphes closes par mineurs. Les deux premiers sont reliés à la caractérisation de certaines classes de graphes, alors que le troisième étudie une relation de “packing-covering” dans des graphes excluant un mineur.Pour le premier problème, nous étudions des plongements isométriques de graphes dont les arêtes sont pondérées dans des espaces métriques. Principalement, nous nous intêressons aux espaces ell_2 et ell_∞. E ́tant donné un graphe pondéré, un plongement isométrique associe à chaque sommet du graphe un vecteur dans l’autre espace de sorte que pour chaque arête du graphe le poids de celle-ci est égal à la distance entre les vecteurs correspondant à ses sommets. Nous disons qu’une fonction de poids sur les arêtes est une fonction de distances réalisable s’il existe un tel plongement. Le paramètre f_p(G) détermine la dimension k minimale d’un espace ell_p telle que toute fonction de distances réalisable de G peut être plongée dans ell_p^k. Ce paramètre est monotone dans le sens des mineurs. Nous caractérisons les graphes tels que f_p(G) a une grande valeur en termes de mineurs inévitables pour p = 2 et p = ∞. Une famille de graphes donne des mineurs inévitables pour un invariant monotone pour les mineurs, si ces graphes “expliquent” pourquoi l’invariant est grand.Le deuxième problème étudie les mineurs exclus minimaux pour la classe de graphes avec φ(G) borné par une constante k, où φ(G) est un paramètre lié au dominant des coupes d’un graphe G. Ce polyèdre contient tous les points qui, composante par composante, sont plus grands ou égaux à une combination convexe des vecteurs d’incidence de coupes dans G. Le paramètre φ(G) est égal au membre de droite maximum d’une description linéaire du dominant des coupes de G en forme entière minimale. Nous étudions les mineurs exclus minimaux pour la propriété φ(G) <= 4 et montrons une nouvelle borne sur φ(G) en termes du “vertex cover number”.Le dernier problème est d’un autre type. Nous étudions une relation de “packing-covering” dans les classes de graphes excluant un mineur. Étant donné un graphe G, une boule de centre v et de rayon r est l’ensemble de tous les sommets de G qui sont à distance au plus r de v. Pour un graphe G et une collection de boules donnés nous pouvons définir un hypergraphe H dont les sommets sont ceux de G et les arêtes correspondent aux boules de la collection. Il est bien connu que dans l’hypergraphe H, le “transversal number” τ(H) vaut au moins le “packing number” ν(H). Nous montrons une borne supérieure sur ν(H) qui est linéaire en τ(H), résolvant ainsi un problème ouvert de Chepoi, Estellon et Vaxès.A class of graphs is closed under taking minors if for each graph in the class and each minor of this graph, the minor is also in the class. By a famous result of Robertson and Seymour, we know that characterizing such a class can be done by identifying a finite set of minimal excluded minors, that is, graphs which do not belong to the class and are minor-minimal for this property.In this thesis, we study three problems in minor-closed classes of graphs. The first two are related to the characterization of some graph classes, while the third one studies a packing-covering relation for graphs excluding a minor.In the first problem, we study isometric embeddings of edge-weighted graphs into metric spaces. In particular, we consider ell_2- and ell_∞-spaces. Given a weighted graph, an isometric embedding maps the vertices of this graph to vectors such that for each edge of the graph the weight of the edge equals the distance between the vectors representing its ends. We say that a weight function on the edges of the graph is a realizable distance function if such an embedding exists. The minor-monotone parameter f_p(G) determines the minimum dimension k of an ell_p-space such that any realizable distance function of G is realizable in ell_p^k. We characterize graphs with large f_p(G) value in terms of unavoidable minors for p = 2 and p = ∞. Roughly speaking, a family of graphs gives unavoidable minors for a minor-monotone parameter if these graphs “explain” why the parameter is high.The second problem studies the minimal excluded minors of the class of graphs such that φ(G) is bounded by some constant k, where φ(G) is a parameter related to the cut dominant of a graph G. This unbounded polyhedron contains all points that are componentwise larger than or equal to a convex combination of incidence vectors of cuts in G. The parameter φ(G) is equal to the maximum right-hand side of a facet-defining inequality of the cut dominant of G in minimum integer form. We study minimal excluded graphs for the property φ(G) <= 4 and provide also a new bound of φ(G) in terms of the vertex cover number.The last problem has a different flavor as it studies a packing-covering relation in classes of graphs excluding a minor. Given a graph G, a ball of center v and radius r is the set of all vertices in G that are at distance at most r from v. Given a graph and a collection of balls, we can define a hypergraph H such that its vertices are the vertices of G and its edges correspond to the balls in the collection. It is well-known that, in the hypergraph H, the transversal number τ(H) is at least the packing number ν(H). We show that we can bound τ(H) from above by a linear function of ν(H) for every graphs G and ball collections H if the graph G excludes a minor, solving an open problem by Chepoi, Estellon et Vaxès.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished
34
Larchevêque, Hubert. "Agrégation de ressources avec contrainte de distance : applications aux plateformes de grande échelle." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2010. http://tel.archives-ouvertes.fr/tel-00580962.
Full textAbstract:
Durant cette thèse, nous avons introduit les problèmes de Bin Covering avec Contrainte de Distance (BCCD) et de Bin Packing avec Contrainte de Distance (BPCD), qui trouvent leur application dans les réseaux de grande échelle, tel Internet. L'étude de ces problèmes que nous effectuons dans des espaces métriques quelconques montre qu'il est impossible de travailler dans un tel cadre sans avoir recours à de l'augmentation de ressources, un procédé qui permet d'élaborer des algorithmes construisant des solutions moins contraintes que la solution optimale à laquelle elles sont comparées. En plus de résultats d'approximation intéressants, nous prouvons la difficulté de ces problèmes si ce procédé n'est pas utilisé. Par ailleurs, de nombreux outils ont pour objectif de plonger les grands réseaux qui nous intéressent dans des espaces métriques bien décrits. Nous avons alors étudié nos problèmes dans les espaces métriques générés par certains de ces outils, comme Vivaldi et Sequoia.
35
Rodrigues, Marcos Okamura. "Modelos matemáticos para o problema de empacotamento em faixas de peças irregulares." Universidade de São Paulo, 2015. http://www.teses.usp.br/teses/disponiveis/55/55134/tde-25062015-111716/.
Full textAbstract:
O problema de empacotamento em faixas de peças irregulares consiste em cortar um conjunto de peças bidimensionais a partir de um objeto de largura fixa utilizando o menor comprimento possível. Apesar de sua importância econômica para diversos setores industriais, há poucos trabalhos que abordam o problema de forma exata devido a sua dificuldade de resolução. Recentemente, Toledo et al. (2013) propuseram um modelo inteiro misto para este problema, no qual as peças são posicionadas em uma malha de pontos. Este modelo obteve bons resultados, provando a otimalidade para instâncias com até 21 peças. No entanto, o modelo possui um grande número de restrições de não-sobreposição, que cresce rapidamente de acordo com a discretização utilizada e a quantidade de peças distintas que devem ser alocadas. Neste trabalho, são propostas novas formulações matemáticas baseadas neste modelo, com o objetivo de reduzir o número de restrições. Na primeira abordagem, são propostos dois modelos reduzidos que mostraram ser eficientes para instâncias com poucas repetições de peças. Na segunda abordagem, foi proposto um modelo de cobertura por cliques para o problema. Este modelo obteve desempenho igual ou superior ao modelo da literatura para todas as instâncias avaliadas, obtendo uma solução ótima para instâncias com até 28 peças.The irregular strip packing problem consists of cutting a set of two-dimensional pieces from an object of fixed width using the smallest possible length. Despite its economic importance for many industrial sectors, few exact studies have been made on this problem due to its difficulty of resolution. Recently, Toledo et al. (2013) proposed a mixed-integer model to this problem in which the pieces are placed on a grid. This model has worked successfully proving the optimality for instances up to 21 pieces. However, the model has a large number of non-overlapping constraints, which grows quickly in accordance with the discretization resolution and number of distinct pieces. In this work, we propose new mathematical formulations based on this model in order to reduce the number of constraints. In the first approach, we present two reduced models that have shown to be effective for instances with few repetitions of pieces. In the second approach, it was proposed a clique covering model for the problem. This model achieved a greater or equal performance than the literature for all instances, getting an optimal solution for instances up to 28 pieces.
36
Andrade, Diego Fernando. "Patterning and Customization: Evaluating Tensor Field Generation For Mechanical Design On Free-Form Surfaces." Research Showcase @ CMU, 2017. http://repository.cmu.edu/dissertations/889.
Full textAbstract:
This dissertation delivers a new computational framework for the automatic generation of geometric feature patterns for industrial design and architectural facades on free-form surfaces. Such patterns include holes in a speaker grill, showerhead holes, protrusions on ceramics or bumpy textures on a panel. These patterns play a key role in making a designed object aesthetically pleasing as well as functional. Computer Aided Design (CAD) systems currently offer tools for generating simple patterns, such as uniformly spaced rectangular or radial patterns. However, they are not applicable to more general cases required in industrial design, including arbitrarily shaped target geometry and graded feature sizes. These tools are limited in several ways: (1) They cannot be applied to free-form geometries used in industrial design, (2) Patterning of these features happens within a single working plane and is not applicable to highly curved surfaces, and (3) Created features lack anisotropy and spatial variations, such as changes in the size and orientation of geometric features within a given region. This thesis proposes a new method of taking input for a target region along with sizing metrics. It will generate feature patterns automatically in three steps: (1) packing isotropic or anisotropic cells tightly in a target region, (2) scaling features according to the specified sizing metrics, and (3) adding features on the base geometry. This approach automatically generates complex patterns that conform to the boundary of any specified region. User input of a small number of geometric features (called “seed features”) of desired size and orientation in preferred locations also can be specified within the target domain. These geometric seed features are then transformed into tensors and used as boundary conditions to generate a Riemannian metric tensor field. A form of the Laplace heat equation is used to generate the field over the target domain, subject to specified boundary conditions. The field represents the anisotropic pattern of the geometric features. The system is implemented as a plugin module in a commercial CAD package to add geometric features to the target region of the model using two set operations, union and subtraction. This method facilitates the creation of a complex pattern of hundreds of geometric features in minutes. All the features are accessible from the CAD system and can be manipulated individually if required by the user. This allows the industrial designer or architect to explore more alternatives by avoiding the tedious and time-consuming manual generation of these geometric patterns.
37
Raymond, Jean-Florent. "Structural and algorithmic aspects of partial orderings of graphs." Doctoral thesis, Montpellier, 2016. https://depotuw.ceon.pl/handle/item/1814.
Full textAbstract:
This thesis falls within the field of Graph Theory. A central theme is the study of exclusion theorems and their uses in related topics. One of them is well-quasi-ordering: we identify well-quasi-ordered subclasses for several orderings of graphs using structural decompositions. A second one the the study of the relations between combinatorial invariants related to problems of packing and covering of combinatorial structures. In this direction, we establish new connections between these invariants for some classes of graphs. We also present algorithmic applications of the results.Tematyka rozprawy należy do teorii grafów. Głównym tematem rozprawy są twierdzenia opisujące grafy z zabronioną podstrukturą i ich zastosowania. Rozważamy zastosowania takich twierdzeń do teorii dobrego uporządkowania. W szczególności, korzystając z twierdzeń strukturalnych, wskazujemy kilka dobrze uporządkowanych podklas ze względu na różne porządki. Zajmujemy się rownież badaniem relacji pomiędzy niezmiennikami w kontekście problemów pokrywania i pakowania różnych struktur kombinatorycznych. W rozprawie opisujemy rownież algorytmiczne konsekwencje naszych wyników.
38
Datta, Krupa R. "Generalization of Hitting, Covering and Packing Problems on Intervals." Thesis, 2017. http://etd.iisc.ernet.in/2005/3628.
Full textAbstract:
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.
39
Lafreniere, Benjamin J. "Packing Unit Disks." Thesis, 2008. http://hdl.handle.net/10012/3907.
Full textAbstract:
Given a set of unit disks in the plane with union area A, what fraction of A can be covered by selecting a pairwise disjoint subset of the disks? Richard Rado conjectured 1/4 and proved 1/4.41. In this thesis, we consider a variant of this problem where the disjointness constraint is relaxed: selected disks must be k-colourable with disks of the same colour pairwise-disjoint. Rado's problem is then the case where k = 1, and we focus our investigations on what can be proven for k > 1.
Motivated by the problem of channel-assignment for Wi-Fi wireless access points, in which the use of 3 or fewer channels is a standard practice, we show that for k = 3 we can cover at least 1/2.09 and for k = 2 we can cover at least 1/2.82. We present a randomized algorithm to select and colour a subset of n disks to achieve these bounds in O(n) expected time. To achieve the weaker bounds of 1/2.77 for k = 3 and 1/3.37 for k = 2 we present a deterministic O(n^2) time algorithm.
We also look at what bounds can be proven for arbitrary k, presenting two different methods of deriving bounds for any given k and comparing their performance. One of our methods is an extension of the method used to prove bounds for k = 2 and k = 3 above, while the other method takes a novel approach.
Rado's proof is constructive, and uses a regular lattice positioned over the given set of disks to guide disk selection. Our proofs are also constructive and extend this idea: we use a k-coloured regular lattice to guide both disk selection and colouring. The complexity of implementing many of the constructions used in our proofs is dominated by a lattice positioning step. As such, we discuss the algorithmic issues involved in positioning lattices as required by each of our proofs. In particular, we show that a required lattice positioning step used in the deterministic O(n^2) algorithm mentioned above is 3SUM-hard, providing evidence that this algorithm is optimal among algorithms employing such a lattice positioning approach. We also present evidence that a similar lattice positioning step used in the constructions for our better bounds for k = 2 and k = 3 may not have an efficient exact implementation.
40
Adams, Patrick Guy. "A numerical approach to Tamme's problem in euclidean n-space." Thesis, 1997. http://hdl.handle.net/1957/33911.
Full text
41
Tsai, Yen-Shing, and 蔡彥興. "Bin Packing and Bin Covering of Subsets." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/76209328907620997913.
Full textAbstract:
博士國立交通大學
資訊管理研究所
104
Bin packing and bin covering are two of the most commonly arising computational tasks in resource allocation. Both problems aim to partition a set of items abiding by some constraints to achieve specific objectives. This work provides a unifying framework to deal with bin packing and bin covering for various constraints and objectives. Mostly, we focus on the study of the coverage of subsets, which is one of the most commonly addressed submodular functions. The thesis identifies several related problems of interests and proposes approximations with perfomance guarantees.
42
Fang, Yuan-Ling, and 方瑗蔆. "Optimal Packing and Covering of λKv, with Quadruples." Thesis, 1998. http://ndltd.ncl.edu.tw/handle/34081363964246914843.
Full textAbstract:
碩士國立交通大學
應用數學研究所
86
In this thesis, we study the optimal packing and covering of Kv with quadruples (K4). Mainly, minimum leave and minimum padding are utilized to describe a maximum packing and a minimum covering respectively. Other than the general optimal packing and covering, we also consider the optimal packing and covering in which their leave and padding are restricted to be simple respectively.
43
Chen, Guan-Fan, and 陳冠帆. "A study of t-packing and t-covering." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/50732350341796590718.
Full textAbstract:
碩士國立交通大學
應用數學系
91
A t-packing of a graph G is a collection of t edge-disjoint isomorphic subgraphs of G such that each subgraph is of size [|E(G)|/t]. A t-covering of a graph G is a collection of t edge-disjoint isomorphic graphs H1,H2,...,Ht such that all edges of G contians in all union of edges of H's. In this thesis, we study the remainder graph (respectively, surplus graph) of each t-packing (respectively, t-covering) of the complete graph. For t is small than six, we determine all possible remainder graphs and respectively surplus graphs.
44
Chen, Wei-Lin, and 陳薇琳. "Packing And Covering The Complete Multigraphs With Short Paths." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/44275201122977376775.
Full textAbstract:
碩士嶺東科技大學
資訊科技應用研究所
100
Graph packing and covering, graph decomposition included, has been and continues to be a popular topic of research in graph theory since many mathematical structures are linked to it and its results can be applied in coding theory, synchronous optical networks (SONET), multicomputer networks, experimental design, DNA library screening, scheduling and other fields. A k-path is a path of length k. In this thesis we completely solve the problem of finding maximum packings and minimum coverings of complete multigraphs with k-paths for k =3,4,5.
45
Fraser, Robert. "Algorithms for Geometric Covering and Piercing Problems." Thesis, 2012. http://hdl.handle.net/10012/7190.
Full textAbstract:
This thesis involves the study of a range of geometric covering and piercing problems, where the unifying thread is approximation using disks. While some of the problems addressed in this work are solved exactly with polynomial time algorithms, many problems are shown to be at least NP-hard. For the latter, approximation algorithms are the best that we can do in polynomial time assuming that P is not equal to NP.
One of the best known problems involving unit disks is the Discrete Unit Disk Cover (DUDC) problem, in which the input consists of a set of points P and a set of unit disks in the plane D, and the objective is to compute a subset of the disks of minimum cardinality which covers all of the points. Another perspective on the problem is to consider the centre points (denoted Q) of the disks D as an approximating set of points for P. An optimal solution to DUDC provides a minimal cardinality subset Q*, a subset of Q, so that each point in P is within unit distance of a point in Q*. In order to approximate the general DUDC problem, we also examine several restricted variants.
In the Line-Separable Discrete Unit Disk Cover (LSDUDC) problem, P and Q are separated by a line in the plane. We write that l^- is the half-plane defined by l containing P, and l^+ is the half-plane containing Q. LSDUDC may be solved exactly in O(m^2n) time using a greedy algorithm. We augment this result by describing a 2-approximate solution for the Assisted LSDUDC problem, where the union of all disks centred in l^+ covers all points in P, but we consider using disks centred in l^- as well to try to improve the solution.
Next, we describe the Within-Strip Discrete Unit Disk Cover (WSDUDC) problem, where P and Q are confined to a strip of the plane of height h. We show that this problem is NP-complete, and we provide a range of approximation algorithms for the problem with trade-offs between the approximation factor and running time.
We outline approximation algorithms for the general DUDC problem which make use of the algorithms for LSDUDC and WSDUDC. These results provide the fastest known approximation algorithms for DUDC. As with the WSDUDC results, we present a set of algorithms in which better approximation factors may be had at the expense of greater running time, ranging from a 15-approximate algorithm which runs in O(mn + m log m + n log n) time to a 18-approximate algorithm which runs in O(m^6n+n log n) time.
The next problems that we study are Hausdorff Core problems. These problems accept an input polygon P, and we seek a convex polygon Q which is fully contained in P and minimizes the Hausdorff distance between P and Q. Interestingly, we show that this problem may be reduced to that of computing the minimum radius of disk, call it k_opt, so that a convex polygon Q contained in P intersects all disks of radius k_opt centred on the vertices of P. We begin by describing a polynomial time algorithm for the simple case where P has only a single reflex vertex. On general polygons, we provide a parameterized algorithm which performs a parametric search on the possible values of k_opt. The solution to the decision version of the problem, i.e. determining whether there exists a Hausdorff Core for P given k_opt, requires some novel insights. We also describe an FPTAS for the decision version of the Hausdorff Core problem.
Finally, we study Generalized Minimum Spanning Tree (GMST) problems, where the input consists of imprecise vertices, and the objective is to select a single point from each imprecise vertex in order to optimize the weight of the MST over the points. In keeping with one of the themes of the thesis, we begin by using disks as the imprecise vertices. We show that the minimization and maximization versions of this problem are NP-hard, and we describe some parameterized and approximation algorithms. Finally, we look at the case where the imprecise vertices consist of just two vertices each, and we show that the minimization version of the problem (which we call 2-GMST) remains NP-hard, even in the plane. We also provide an algorithm to solve the 2-GMST problem exactly if the combinatorial structure of the optimal solution is known.
We identify a number of open problems in this thesis that are worthy of further study.
Among them:
Is the Assisted LSDUDC problem NP-complete?
Can the WSDUDC results be used to obtain an improved PTAS for DUDC?
Are there classes of polygons for which the determination of the Hausdorff Core is easy?
Is there a PTAS for the maximum weight GMST problem on (unit) disks?
Is there a combinatorial approximation algorithm for the 2-GMST problem (particularly with an approximation factor under 4)?
46
Pan, Jiangwei. "Algorithms for Geometric Matching, Clustering, and Covering." Diss., 2016. http://hdl.handle.net/10161/12902.
Full textAbstract:
With the popularization of GPS-enabled devices such as mobile phones, location data are becoming available at an unprecedented scale. The locations may be collected from many different sources such as vehicles moving around a city, user check-ins in social networks, and geo-tagged micro-blogging photos or messages. Besides the longitude and latitude, each location record may also have a timestamp and additional information such as the name of the location. Time-ordered sequences of these locations form trajectories, which together contain useful high-level information about people's movement patterns.
The first part of this thesis focuses on a few geometric problems motivated by the matching and clustering of trajectories. We first give a new algorithm for computing a matching between a pair of curves under existing models such as dynamic time warping (DTW). The algorithm is more efficient than standard dynamic programming algorithms both theoretically and practically. We then propose a new matching model for trajectories that avoids the drawbacks of existing models. For trajectory clustering, we present an algorithm that computes clusters of subtrajectories, which correspond to common movement patterns. We also consider trajectories of check-ins, and propose a statistical generative model, which identifies check-in clusters as well as the transition patterns between the clusters.
The second part of the thesis considers the problem of covering shortest paths in a road network, motivated by an EV charging station placement problem. More specifically, a subset of vertices in the road network are selected to place charging stations so that every shortest path contains enough charging stations and can be traveled by an EV without draining the battery. We first introduce a general technique for the geometric set cover problem. This technique leads to near-linear-time approximation algorithms, which are the state-of-the-art algorithms for this problem in either running time or approximation ratio. We then use this technique to develop a near-linear-time algorithm for this
shortest-path cover problem.
Dissertation
47
Francetic, Nevena. "Covering Arrays with Row Limit." Thesis, 2012. http://hdl.handle.net/1807/34006.
Full textAbstract:
Covering arrays with row limit, CARLs, are a new family of combinatorial objects
which we introduce as a generalization of group divisible designs and covering arrays. In the same manner as their predecessors, CARLs have a natural application as combinatorial models for interaction test suites. A CARL(N;t,k,v:w), is an N×k array with some empty cells. A component, which is represented by a column, takes values from a v-set called the alphabet. In each row, there are exactly w non-empty cells, that is the corresponding components have an assigned value from the alphabet. The parameter w is called the row limit. Moreover, any N×t subarray contains every of v^t distinct t-tuples of alphabet symbols at least once.
This thesis is concerned with the bounds on the size and with the construction of
CARLs when the row limit w(k) is a positive integer valued function of the number
of columns, k. Here we give a lower bound, and probabilistic and algorithmic upper
bounds for any CARL. Further, we find improvements on the upper bounds when
w(k)ln(w(k)) = o(k) and when w(k) is a constant function. We also determine the
asymptotic size of CARLs when w(k) = Θ(k) and when w(k) is constant.
Next, we study constructions of CARLs. We provide two combinatorial constructions
of CARLs, which we apply to construct families of CARLs with w(k)=ck, where c<1.
Also, we construct optimal CARLs when t=2 and w=4, and prove that there exists a
constant δ, such that for any v and k≥4, an optimal CARL(2,k,v:4) differs from the lower bound by at most δ rows, with some possible exceptions.
Finally, we define a packing array with row limit, PARL(N;t,k,v:w), in the same
way as a CARL(N;t,k,v:w) with the difference that any t-tuple is contained at most
once in any N×t subarray. We find that when w(k) is a constant function, the results on
the asymptotic size of CARLs imply the results on the asymptotic size of PARLs. Also, when t=2, we consider a transformation of optimal CARLs with row limit w=3 to
optimal PARLs with w=3.
48
Hu, Nan. "Approximation Algorithms for Geometric Covering Problems for Disks and Squares." Thesis, 2013. http://hdl.handle.net/10012/7703.
Full textAbstract:
Geometric covering is a well-studied topic in computational geometry. We study three covering problems: Disjoint Unit-Disk Cover, Depth-(≤ K) Packing and Red-Blue Unit-Square Cover.
In the Disjoint Unit-Disk Cover problem, we are given a point set and want to cover the maximum number of points using disjoint unit disks. We prove that the problem is NP-complete and give a polynomial-time approximation scheme (PTAS) for it.
In Depth-(≤ K) Packing for Arbitrary-Size Disks/Squares, we are given a set of arbitrary-size disks/squares, and want to find a subset with depth at most K and maximizing the total area. We prove a depth reduction theorem and present a PTAS.
In Red-Blue Unit-Square Cover, we are given a red point set, a blue point set and a
set of unit squares, and want to find a subset of unit squares to cover all the blue points and the minimum number of red points. We prove that the problem is NP-hard, and give a PTAS for it. A "mod-one" trick we introduce can be applied to several other covering problems on unit squares.
49
Tiwari, Praveen 1985. "On Covering Points with Conics and Strips in the Plane." Thesis, 2012. http://hdl.handle.net/1969.1/148314.
Full textAbstract:
Geometric covering problems have always been of focus in computer scientific research. The generic geometric covering problem asks to cover a set S of n objects with another set of objects whose cardinality is minimum, in a geometric setting. Many versions of geometric cover have been studied in detail, one of which is line cover: Given a set of points in the plane, find the minimum number of lines to cover them. In Euclidean space Rm, this problem is known as Hyperplane Cover, where lines are replaced by affine hyperplanes bounded by dimension d. Line cover is NP-hard, so is its hyperplane analogue. Our thesis focuses on few extensions of hyperplane cover and line cover.
One of the techniques used to study NP-hard problems is Fixed Parameter Tractability (FPT), where, in addition to input size, a parameter k is provided for input instance. We ask to solve the problem with respect to k, such that the running time is a function in both n and k, strictly polynomial in n, while the exponential component is limited to k. In this thesis, we study FPT and parameterized complexity theory, the theory of classifying hard problems involving a parameter k.
We focus on two new geometric covering problems: covering a set of points in the plane with conics (conic cover) and covering a set of points with strips or fat lines of given width in the plane (fat line cover). A conic is a non-degenerate curve of degree two in the plane. A fat line is defined as a strip of finite width w. In this dissertation, we focus on the parameterized versions of these two problems, where, we are asked to cover the set of points with k conics or k fat lines. We use the existing techniques of FPT algorithms, kernelization and approximation algorithms to study these problems. We do a comprehensive study of these problems, starting with NP-hardness results to studying their parameterized hardness in terms of parameter k.
We show that conic cover is fixed parameter tractable, and give an algorithm of running time O∗ ((k/1.38)^4k), where, O∗ implies that the running time is some polynomial in input size. Utilizing special properties of a parabola, we are able to achieve a faster algorithm and show a running time of O∗ ((k/1.15)^3k).
For fat line cover, first we establish its NP-hardness, then we explore algorithmic possibilities with respect to parameterized complexity theory. We show W [1]-hardness of fat line cover with respect to the number of fat lines, by showing a parameterized reduction from the problem of stabbing axis-parallel squares in the plane. A parameterized reduction is an algorithm which transforms an instance of one parameterized problem into an instance of another parameterized problem using a FPT-algorithm. In addition, we show that some restricted versions of fat line cover are also W [1]-hard. Further, in this thesis, we explore a restricted version of fat line cover, where the set of points are integer coordinates and allow only axis-parallel lines to cover them. We show that the problem is still NP-hard. We also show that this version is fixed parameter tractable having a kernel size of O (k^2) and give a FPT-algorithm with a running time of O∗ (3^k). Finally, we conclude our study on this problem by giving an approximation algorithm for this version having a constant approximation ratio 2.
50
"From a multi-skilled staff-scheduling problem to the mixed set covering, packing and partitioning polytope." 2013. http://library.cuhk.edu.hk/record=b5549742.
Full textAbstract:
本文分為個部分：多技能員工調問題，和集合覆蓋、裝運和劃分混合問題多面體研究，其中第一部分問題啟發我們第二部分的探。首先，我們研究在一個大型機場的國際客運站中客戶服務人員的調問題。員工有同的技能和技能水平。技能定義是二維的，包括操作技能和語言能。在學模型中，我們也考慮用餐和休息時間的調和多處工作地點。我們證明該問題是NP-hard 的。我們推導出有效等式，以方計算過程。我們的學模型能夠幫助規劃者做出決策，及可計算同型的活性對業務的影響。我們的模型也可以幫助決策者計劃長遠工作調和培訓。
多技能人員調問題啟發我們這篇文的第二部分：集合覆蓋、裝運和劃分混合問題多面體研究。我們首先證明如覆蓋（或裝運）的等式被删去，該多面體是相當於一個放寬的裝運（或覆蓋）多面體的投影。然後我們考慮混合奇穴多面體（即是一個由覆蓋和裝運等式組成的多面體），並採用圖方法研究，通過考慮同型的等式的互動，推導出混合奇穴等式和完全描繪多面體的特徵。我們再推導出集合覆蓋和裝運混合問題的混合奇穴等式。計算結果顯示，混合奇穴等式有助於減少計算時間。我們還提供子明如何用等式幫助決策。
This thesis is divided into two parts: Multi-Skilled Staff-Scheduling Problem and a polyhedral study on the Mixed Set Covering, Packing and Partitioning Problem, where the first part is a motivating example of the latter.
In the multi-skilled staff-scheduling problem, we study the problem of scheduling customer service agents at an international terminal of a large airport. The staff members are heterogeneous with different skills and skill levels. The skill specification is two-dimensional, defined by operational skills and language proficiency. In the mathematical model, we also consider the scheduling of meal and rest breaks, and multiple locations. The problem is shown to be NP-hard. We derive valid inequalities to speed up the computational procedure. With our mathematical model, we are able to help schedule planners make decisions and examine the impacts of different types of flexibility on the level of service provided. Our model can also help decision makers with long-term work-schedule planning.
Motivated by the staff-scheduling problem, the second part of this thesis studies the polyhedral structure of the mixed set covering, packing and partitioning problem, i.e., a problem that contains set covering, set packing and set partitioning constraints. We first study the mixed odd hole polytope, which is the polytope associated with a mixed odd hole consisting of covering and packing "edges". Adopting a graphical approach and considering the "interactions" between the different types of inequalities, we derive the mixed odd hole inequality, thereby completely characterizing the mixed odd hole polytope. We then generalize the mixed odd hole inequality for the general mixed covering and packing polytope. Computational results show that the mixed odd hole inequalities are helpful in reducing solution time. We also provide examples of problem settings in which the inequalities can be used to help decision making.
Detailed summary in vernacular field only.
Detailed summary in vernacular field only.
Detailed summary in vernacular field only.
Kuo, Yong Hong.
Thesis (Ph.D.)--Chinese University of Hong Kong, 2013.
Includes bibliographical references (leaves 119-129).
Abstracts also in Chinese.
Abstract --- p.i
Acknowledgement --- p.iii
Chapter I --- Scheduling of Multi-skilled Staff Across Multiple Locations --- p.1
Chapter 1 --- Introduction --- p.2
Chapter 2 --- Literature Review --- p.8
Chapter 3 --- Mathematical Model --- p.14
Chapter 3.1 --- Problem Formulation --- p.14
Chapter 3.2 --- Valid Inequalities --- p.20
Chapter 3.3 --- Shift Scheduling and Longer-Term Work-Schedule Planning --- p.21
Chapter 4 --- Computational Studies --- p.24
Chapter 4.1 --- Dataset and Input Parameters --- p.24
Chapter 4.1.1 --- Staffing Requirements and Shortage Penalties --- p.24
Chapter 4.2 --- Computational Study: Managerial Insights --- p.26
Chapter 4.2.1 --- Effect of Three Types of Flexibility --- p.26
Chapter 4.2.2 --- Impact of Different Types of Flexibility --- p.28
Chapter 4.3 --- Computational Study: Benefits Compared with Benchmarks --- p.33
Chapter 4.3.1 --- Heuristic H1: CSA Assignment by Time Period --- p.35
Chapter 4.3.2 --- Heuristic H2: CSA Assignment by Criticality --- p.35
Chapter 4.3.3 --- Comparison with Benchmarks --- p.37
Chapter 4.4 --- Computational Study: Computational Efficiency --- p.40
Chapter 5 --- Conclusions --- p.44
Chapter II --- On the Polyhedral Structure of the Mixed Set Covering, Packing and Partitioning Polytope --- p.47
Chapter 6 --- Introduction --- p.48
Chapter 7 --- Preliminaries --- p.51
Chapter 8 --- Overview of Packing, Covering and Partitioning Polyhedra --- p.58
Chapter 8.1 --- Set Packing Polytope --- p.58
Chapter 8.1.1 --- Intersection Graph --- p.59
Chapter 8.1.2 --- Lifting Procedures --- p.63
Chapter 8.1.3 --- Facet-Producing Subgraphs --- p.66
Chapter 8.2 --- Set Covering Polytope --- p.71
Chapter 8.2.1 --- Polyhedral Structure and the Associated Graphs --- p.71
Chapter 8.3 --- Set Partitioning Polytope --- p.76
Chapter 8.4 --- Blocking and Anti-Blocking Pairs --- p.78
Chapter 8.4.1 --- Blocking polyhedra --- p.78
Chapter 8.4.2 --- Anti-blocking polyhedra --- p.80
Chapter 8.5 --- Perfect, Ideal and Balanced Matrices --- p.81
Chapter 8.5.1 --- Perfect Matrices --- p.81
Chapter 8.5.2 --- Ideal Matrices --- p.83
Chapter 8.5.3 --- Balanced Matrices --- p.84
Chapter 9 --- Mixed Set Covering, Packing and Partitioning Polytope --- p.87
Chapter 9.1 --- Mixed Set Partitioning and Covering/Packing Polytope --- p.87
Chapter 9.2 --- Mixed Set Covering and Packing Polytope --- p.88
Chapter 9.2.1 --- Mixed odd hole --- p.90
Chapter 9.2.2 --- General Mixed Covering and Packing Polytope --- p.97
Chapter 9.3 --- Computational Experiments --- p.108
Chapter 9.4 --- Applications of the Mixed Odd Hole Inequality --- p.112
Chapter 9.4.1 --- Railway Time-Tabling --- p.112
Chapter 9.4.2 --- Team Formation --- p.113
Chapter 9.4.3 --- Course Registration --- p.114
Chapter 10 --- Conclusions --- p.117
Bibliography --- p.119