Дисертації з теми "Geometric Covering and Packing"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся з топ-50 дисертацій для дослідження на тему "Geometric Covering and Packing".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Переглядайте дисертації для різних дисциплін та оформлюйте правильно вашу бібліографію.
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/.
Повний текст джерелаBezdek, Andras. "Packing and covering problems /." The Ohio State University, 1986. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487266691095136.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерелаNielsen, Torben Noerup. "Combinatorial Bin Packing Problems." Diss., The University of Arizona, 1985. http://hdl.handle.net/10150/187536.
Повний текст джерела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.
Повний текст джерелаPasha, Arfath. "Geometric bin packing algorithm for arbitrary shapes." [Gainesville, Fla.] : University of Florida, 2003. http://purl.fcla.edu/fcla/etd/UFE0000907.
Повний текст джерела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.
Повний текст джерела許眞眞 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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерелаLü, Lin, and 吕琳. "Geometric optimization for shape processing." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2011. http://hub.hku.hk/bib/B46483640.
Повний текст джерелаBossenger, Wayne. "2D irregular strip packing at Kohler signs." Thesis, Stellenbosch : Stellenbosch University, 2014. http://hdl.handle.net/10019.1/96129.
Повний текст джерела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.
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.
Повний текст джерелаSpirova, Margarita. "Discrete Geometry in Normed Spaces." Doctoral thesis, Universitätsbibliothek Chemnitz, 2010. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-62896.
Повний текст джерелаBhowmick, Santanu. "Multi-covering problems and their variants." Diss., University of Iowa, 2017. https://ir.uiowa.edu/etd/5418.
Повний текст джерелаKhan, Arindam. "Approximation algorithms for multidimensional bin packing." Diss., Georgia Institute of Technology, 2015. http://hdl.handle.net/1853/54371.
Повний текст джерела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/.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерелаDissertaçã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
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.
Повний текст джерелаMoustrou, Philippe. "Geometric distance graphs, lattices and polytopes." Thesis, Bordeaux, 2017. http://www.theses.fr/2017BORD0802/document.
Повний текст джерелаA 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
Sheppard, Nicholas Paul. "Self-Reduction for Combinatorial Optimisation." Thesis, The University of Sydney, 2001. http://hdl.handle.net/2123/797.
Повний текст джерелаSheppard, Nicholas Paul. "Self-Reduction for Combinatorial Optimisation." University of Sydney. Computer Science, 2001. http://hdl.handle.net/2123/797.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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
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.
Повний текст джерела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/.
Повний текст джерела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.
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.
Повний текст джерелаRaymond, Jean-Florent. "Structural and algorithmic aspects of partial orderings of graphs." Doctoral thesis, Montpellier, 2016. https://depotuw.ceon.pl/handle/item/1814.
Повний текст джерела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.
Datta, Krupa R. "Generalization of Hitting, Covering and Packing Problems on Intervals." Thesis, 2017. http://etd.iisc.ernet.in/2005/3628.
Повний текст джерелаLafreniere, Benjamin J. "Packing Unit Disks." Thesis, 2008. http://hdl.handle.net/10012/3907.
Повний текст джерелаAdams, Patrick Guy. "A numerical approach to Tamme's problem in euclidean n-space." Thesis, 1997. http://hdl.handle.net/1957/33911.
Повний текст джерелаTsai, Yen-Shing, and 蔡彥興. "Bin Packing and Bin Covering of Subsets." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/76209328907620997913.
Повний текст джерела國立交通大學
資訊管理研究所
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.
Fang, Yuan-Ling, та 方瑗蔆. "Optimal Packing and Covering of λKv, with Quadruples". Thesis, 1998. http://ndltd.ncl.edu.tw/handle/34081363964246914843.
Повний текст джерела國立交通大學
應用數學研究所
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.
Chen, Guan-Fan, and 陳冠帆. "A study of t-packing and t-covering." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/50732350341796590718.
Повний текст джерела國立交通大學
應用數學系
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.
Chen, Wei-Lin, and 陳薇琳. "Packing And Covering The Complete Multigraphs With Short Paths." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/44275201122977376775.
Повний текст джерела嶺東科技大學
資訊科技應用研究所
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.
Fraser, Robert. "Algorithms for Geometric Covering and Piercing Problems." Thesis, 2012. http://hdl.handle.net/10012/7190.
Повний текст джерелаPan, Jiangwei. "Algorithms for Geometric Matching, Clustering, and Covering." Diss., 2016. http://hdl.handle.net/10161/12902.
Повний текст джерела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
Francetic, Nevena. "Covering Arrays with Row Limit." Thesis, 2012. http://hdl.handle.net/1807/34006.
Повний текст джерелаHu, Nan. "Approximation Algorithms for Geometric Covering Problems for Disks and Squares." Thesis, 2013. http://hdl.handle.net/10012/7703.
Повний текст джерелаTiwari, Praveen 1985. "On Covering Points with Conics and Strips in the Plane." Thesis, 2012. http://hdl.handle.net/1969.1/148314.
Повний текст джерела"From a multi-skilled staff-scheduling problem to the mixed set covering, packing and partitioning polytope." 2013. http://library.cuhk.edu.hk/record=b5549742.
Повний текст джерела首先,我們研究在一個大型機場的國際客運站中客戶服務人員的調問題。員工有同的技能和技能水平。技能定義是二維的,包括操作技能和語言能。在學模型中,我們也考慮用餐和休息時間的調和多處工作地點。我們證明該問題是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