Spelling suggestions: "subject:"combinatorial packing anda covering"" "subject:"combinatorial packing ando covering""
1 
The packing problem for finite projective geometries /Games, Richard Alan January 1980 (has links)
No description available.

2 
Packing and covering problems /Bezdek, Andras January 1986 (has links)
No description available.

3 
Combinatorial Bin Packing ProblemsNielsen, Torben Noerup January 1985 (has links)
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 NPhard 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 online and two offline. 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 offline. Both of these heuristics are shown to be asymptotically optimal in expectation when the sizes of the items input are assumed uniformly distributed.

4 
2D irregular strip packing at Kohler signsBossenger, Wayne 12 1900 (has links)
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 ruleset. 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, SuidAfrika.
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 TweeDimensionele 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.

5 
A numerical approach to Tamme's problem in euclidean nspaceAdams, Patrick Guy 09 June 1997 (has links)
Graduation date: 1998

6 
Improved Approximation Algorithms for Geometric Packing Problems With Experimental EvaluationSong, Yongqiang 12 1900 (has links)
Geometric packing problems are NPcomplete 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.

7 
A conjectura de Tuza sobre triângulos em grafos / The conjecture of Tuza about triangles in graphsFreitas, Lucas Ismaily Bezerra, 1987 06 February 2014 (has links)
Orientador: Orlando Lee / Dissertação (mestrado)  Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 20180825T17: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 arestadisjuntos em grafos. Em 1981, Tuza conjecturou que para todo grafo, o número máximo de triângulos arestadisjuntos é 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 contraexemplo mínimo para a conjectura de Tuza, então G é 4conexo. 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 edgedisjoint triangles in graphs. In 1981, Tuza conjectured that for any graph, the maximum number of edgedisjoint 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 4connected. 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

Page generated in 0.142 seconds