To see the other types of publications on this topic, follow the link: Steiner problem.
Dissertations / Theses on the topic 'Steiner problem'
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 'Steiner problem.'
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
Alex, Jerome. "The periodic Steiner problem." Phd thesis, Technische Universität Darmstadt, 2019. http://tuprints.ulb.tu-darmstadt.de/8538/1/AlexDiss.pdf.
Full textAbstract:
We study a problem of geometric graph theory: We determine the triply periodic graph in Euclidean 3-space which minimizes length among all graphs spanning a fundamental domain of 3-space with the same volume. This problem is related to minimizing the Willmore energy of triply periodic surfaces under a volume constraint.
2
Minkoff, Maria 1976. "The Prize Collecting Steiner Tree problem." Thesis, Massachusetts Institute of Technology, 2000. http://hdl.handle.net/1721.1/86544.
Full text
3
Swanepoel, Konrad Johann. "The local Steiner problem in Minkowski spaces." Doctoral thesis, Universitätsbibliothek Chemnitz, 2010. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-201000873.
Full textAbstract:
The subject of this monograph can be described as the local properties of geometric Steiner minimal trees in finite-dimensional normed spaces. A Steiner minimal tree of a finite set of points is a shortest connected set interconnecting the points. For a quick introduction to this topic and an overview of all the results presented in this work, see Chapter 1. The relevant mathematical background knowledge needed to understand the results and their proofs are collected in Chapter 2. In Chapter 3 we introduce the Fermat-Torricelli problem, which is that of finding a point that minimizes the sum of distances to a finite set of given points. We only develop that part of the theory of Fermat-Torricelli points that is needed in later chapters. Steiner minimal trees in finite-dimensional normed spaces are introduced in Chapter 4, where the local Steiner problem is given an exact formulation. In Chapter 5 we solve the local Steiner problem for all two-dimensional spaces, and generalize this solution to a certain class of higher-dimensional spaces (CL spaces). The twodimensional solution is then applied to many specific norms in Chapter 6. Chapter 7 contains an abstract solution valid in any dimension, based on the subdifferential calculus. This solution is applied to two specific high-dimensional spaces in Chapter 8. In Chapter 9 we introduce an alternative approach to bounding the maximum degree of Steiner minimal trees from above, based on the illumination problem from combinatorial convexity. Finally, in Chapter 10 we consider the related k-Steiner minimal trees, which are shortest Steiner trees in which the number of Steiner points is restricted to be at most kDas Thema dieser Habilitationsschrift kann als die lokalen Eigenschaften der geometrischen minimalen Steiner-Bäume in endlich-dimensionalen normierten Räumen beschrieben werden. Ein minimaler Steiner-Baum einer endlichen Punktmenge ist eine kürzeste zusammenhängende Menge die die Punktmenge verbindet. Kapitel 1 enthält eine kurze Einführung zu diesem Thema und einen Überblick über alle Ergebnisse dieser Arbeit. Die entsprechenden mathematischen Vorkenntnisse mit ihren Beweisen, die erforderlich sind die Ergebnisse zu verstehen, erscheinen in Kapitel 2. In Kapitel 3 führen wir das Fermat-Torricelli-Problem ein, das heißt, die Suche nach einem Punkt, der die Summe der Entfernungen der Punkte einer endlichen Punktmenge minimiert. Wir entwickeln nur den Teil der Theorie der Fermat-Torricelli-Punkte, der in späteren Kapiteln benötigt wird. Minimale Steiner-Bäume in endlich-dimensionalen normierten Räumen werden in Kapitel 4 eingeführt, und eine exakte Formulierung wird für das lokale Steiner-Problem gegeben. In Kapitel 5 lösen wir das lokale Steiner-Problem für alle zwei-dimensionalen Räume, und diese Lösung wird für eine bestimmte Klasse von höher-dimensionalen Räumen (den sog. CL-Räumen) verallgemeinert. Die zweidimensionale Lösung wird dann auf mehrere bestimmte Normen in Kapitel 6 angewandt. Kapitel 7 enthält eine abstrakte Lösung die in jeder Dimension gilt, die auf der Analysis von Subdifferentialen basiert. Diese Lösung wird auf zwei bestimmte höher-dimensionale Räume in Kapitel 8 angewandt. In Kapitel 9 führen wir einen alternativen Ansatz zur oberen Schranke des maximalen Grads eines minimalen Steiner-Baums ein, der auf dem Beleuchtungsproblem der kombinatorischen Konvexität basiert ist. Schließlich betrachten wir in Kapitel 10 die verwandten minimalen k-Steiner-Bäume. Diese sind die kürzesten Steiner-Bäume, in denen die Anzahl der Steiner-Punkte auf höchstens k beschränkt wird
4
Wang, Xinhui. "Exact algorithms for the Steiner tree problem." Enschede : University of Twente [Host], 2008. http://doc.utwente.nl/59035.
Full text
5
Srinivasan, Sangeetha Rodger C. A. "Disjoint Intersection problem For Steiner triple systems." Auburn, Ala., 2007. http://repo.lib.auburn.edu/2007%20Fall%20Theses/Srinivasan_Sangeetha_36.pdf.
Full text
6
Vahdati-Daneshmand, Siavash. "Algorithmic approaches to the Steiner problem in networks." [S.l. : s.n.], 2004. http://www.bsz-bw.de/cgi-bin/xvms.cgi?SWB11051778.
Full text
7
Mussafi, Noor Saif Muhammad. "Complexity and Approximation of the Rectilinear Steiner Tree Problem." Master's thesis, Universitätsbibliothek Chemnitz, 2009. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-200901213.
Full textAbstract:
Given a finite set K of terminals in the plane. A
rectilinear Steiner minimum tree for K (RST) is
a tree which interconnects among these terminals
using only horizontal and vertical lines of shortest
possible length containing Steiner point. We show the
complexity of RST i.e. belongs to NP-complete.
Moreover we present an approximative method of
determining the solution of RST problem proposed by Sanjeev Arora
in 1996, Arora's Approximation Scheme. This algorithm
has time complexity polynomial in the number of
terminals for a fixed performance ratio 1 + Epsilon.
8
Logan, Andrew. "The Steiner Problem on Closed Surfaces of Constant Curvature." BYU ScholarsArchive, 2015. https://scholarsarchive.byu.edu/etd/4420.
Full textAbstract:
The n-point Steiner problem in the Euclidean plane is to find a least length path network connecting n points. In this thesis we will demonstrate how to find a least length path network T connecting n points on a closed 2-dimensional Riemannian surface of constant curvature by determining a region in the covering space that is guaranteed to contain T. We will then provide an algorithm for solving the n-point Steiner problem on such a surface.
9
Van, Laarhoven Jon William. "Exact and heuristic algorithms for the Euclidean Steiner tree problem." Diss., University of Iowa, 2010. https://ir.uiowa.edu/etd/755.
Full textAbstract:
In this thesis, we study the Euclidean Steiner tree problem (ESTP) which arises in the field of combinatorial optimization. The ESTP asks for a network of minimal total edge length spanning a set of given terminal points in Rd with the ability to add auxiliary connecting points (Steiner points) to decrease the overall length of the network. The graph theory literature contains extensive studies of exact, approximation, and heuristic algorithms for ESTP in the plane, but less is known in higher dimensions. The contributions of this thesis include a heuristic algorithm and enhancements to an exact algorithm for solving the ESTP.
We present a local search heuristic for the ESTP in Rd for d ≥ 2. The algorithm utilizes the Delaunay triangulation to generate candidate Steiner points for insertion, the minimum spanning tree to create a network on the inserted points, and second order cone programming to optimize the locations of Steiner points. Unlike other ESTP heuristics relying on the Delaunay triangulation, the algorithm inserts Steiner points probabilistically into Delaunay triangles to achieve different subtrees on subsets of terminal points. The algorithm extends effectively into higher dimensions, and we present computational results on benchmark test problems in Rd for 2 ≤ d ≤ 5.
We develop new geometric conditions derived from properties of Steiner trees which bound below the number of Steiner points on paths between terminals in the Steiner minimal tree. We describe conditions for trees with a Steiner topology and show how these conditions relate to the Voronoi diagram. We describe more restrictive conditions for trees with a full Steiner topology and their implementation into the algorithm of Smith (1992). We present computational results on benchmark test problems in Rd for 2 ≤ d ≤ 5.
10
Cinel, Sertac. "Sequential And Parallel Heuristic Algorithms For The Rectilinear Steiner Tree Problem." Master's thesis, METU, 2006. http://etd.lib.metu.edu.tr/upload/12607896/index.pdf.
Full textAbstract:
The Steiner Tree problem is one of the most popular graph problems and has many application areas. The rectilinear version of this problem, introduced by Hanan, has taken special attention since it addresses a fundamental matter in &ldquoPhysical Design&rdquo
phase of the Very Large Scale Integrated (VLSI) Computer Aided Design (CAD) process. The Rectilinear Steiner Tree Problem asks for a minimum length tree that interconnects a given set of points by only horizontal and vertical line segments, enabling the use of extra points. There are various exact algorithms. However the problem is NP-complete hence approximation algorithms have to be used especially for large instances. In this thesis work, first a survey on heuristics for the Rectilinear Steiner Tree Problem is conducted and then two recently developed successful algorithms, BGA by Kahng et. al. and RST by Zhou have been studied and investigated deeply. Both algorithms have subproblems, most of which have individual backgrounds in literature. After an analysis of BGA and RST, the thesis proposes a modification on RST, which leads to a faster and non-recursive version. The efficiency of the modified algorithm has been validated by computational tests using both random and VLSI benchmark instances. A partially parallelized version of the modified algorithm is also proposed for distributed computing environments. It is implemented using MPI (message passing interface) middleware and the results of comparative tests conducted on a cluster of workstations are presented. The proposed distributed algorithm has also proved to be promising especially for large problem instances.
11
Alex, Jerome [Verfasser], Karsten [Akademischer Betreuer] Große-Brauckmann, and John [Akademischer Betreuer] Sullivan. "The periodic Steiner problem / Jerome Alex ; Karsten Große-Brauckmann, John Sullivan." Darmstadt : Universitäts- und Landesbibliothek Darmstadt, 2019. http://d-nb.info/1180602285/34.
Full text
12
KO, MYUNG CHUL. "VISUALIZATION OF THE STEINER TREE HEURISTIC SOLUTIONS WITH LEDA." University of Cincinnati / OhioLINK, 2002. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1029528330.
Full text
13
SOUZA, CID CARVALHO DE. "THE STEINER PROBLEM IN RECTILINEAR METRIC: PROPERTIES, NEW HEURISTICS AND COMPUTATIONAL STUDY." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 1989. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=10236@1.
Full textAbstract:
IBM BRASILCOORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
Nesta tese faz-se uma extensa revisão bibliográfica sobre o problema de Steiner na métrica retilínea, destacando-se a aplicação do mesmo no projeto de VLSI. São descritas em detalhes várias heurísticas existentes na literatura para as quais estudam-se a complexidade computacional e a qualidade das soluções obtidas. Além disso, são estabelecidos novos resultados relativos ao comportamento de pior caso destas heurísticas. Propõe-se, ainda, duas novas heurísticas para o problema de Steiner na métrica retilínea para as quais são estudadas a complexidade computacional e a qualidade da solução, inclusive com a análise do pior caso. Uma grande quantidade de testes computacionais permitiu a realização de uma comparação do desempenho das diversas heurísticas implementadas, concluindo-se que uma das novas heurísticas propostas fornece, em média, soluções melhores do que aquelas fornecidas pelas demais heurísticas conhecidas na literatura.
In this dissertation we present a survey about the Steiner problem in the rectilinear metric, illustrating its applications to the VLSI desing. A large number of heurístics already described in literature is studied in details. Moreover, we study the complexity of these heuristics and the quality of their solutions. New results concerning their worst case behavior are stated. We also propose two new heuristics for thew Steiner problem in the rectilinear metric, for which we study the complexity and the quality of the solutions, including the worst case analysis. A large nember of computational experiments was conducted and allowed the comparison of the performances of the heuristics implemented. We conclude from these experiments that, in the average, the solutions obtained by one of the new heuristics are better than the solutions obtained by those alreafy available in the literature.
14
Braga, Hugo Vinícius Vaz. "Algorithms for the directed k-spanner with minimum degree steiner tree problem." reponame:Repositório Institucional da UFBA, 2013. http://www.repositorio.ufba.br/ri/handle/ri/13146.
Full textAbstract:
Submitted by LIVIA FREITAS (livia.freitas@ufba.br) on 2013-10-08T15:47:13Z
No. of bitstreams: 1
Hugo_Braga-Dissertacao_Mestrado-PPGM.pdf: 1341699 bytes, checksum: dd5c4a50e2339c29a293547d6f02c9de (MD5)Approved for entry into archive by LIVIA FREITAS(livia.freitas@ufba.br) on 2013-10-08T15:47:22Z (GMT) No. of bitstreams: 1 Hugo_Braga-Dissertacao_Mestrado-PPGM.pdf: 1341699 bytes, checksum: dd5c4a50e2339c29a293547d6f02c9de (MD5)
Made available in DSpace on 2013-10-08T15:47:22Z (GMT). No. of bitstreams: 1 Hugo_Braga-Dissertacao_Mestrado-PPGM.pdf: 1341699 bytes, checksum: dd5c4a50e2339c29a293547d6f02c9de (MD5)
Arvores Steiner são comumente utilizadas para modelar restrições na execução da operação de multicast. Nesta dissertação nós tratamos um novo problema denominado árvore Steiner com Grau Mínimo e fator de dilatação k em Grafos Direcionados (cujo acrônimo em inglês é DSMDStP). Este problema consiste em: dado um grafo direcionado G(V,E), um n´o origem s ∈ V , um fator de dilatação k (k ∈ R+, k ≥ 1) e um conjunto de terminais T ⊆ V \ {s}, encontrar uma arborescência onde o custo entre o nó de origem s em G e cada t ∈ T é menor ou igual a k vezes o custo da menor distância entre este par de nós, ao passo que o grau máximo de saída é minimizado. DSMDStP não admite aproximação sublogarítmica (a menos que NP ⊂ DTIME(nlog log n). Nós descrevemos um algoritmo de aproximação que gera uma arborescência com grau máximo de saída limitado por 2q|T| + 2 + O(log |T|) · d∗, onde d∗ consiste no grau máximo da solução ótima e a arborescência é uma spanner com fator de dilatação (a partir da raiz) de k ·1 + maxt2T {dist(s,t,G)}mint2T dist(s,t,G)}, onde dist(s, t,G) representa o caminho de menor custo entre s e t em G. Embora nosso fator de dilata¸c˜ao viole k, nos experimentos, a restrição de spanner foi satisfeita ou, em média, quase satisfeita. Além disso, o grau de saída medido nos experimentos foi baixo. Nós também descrevemos uma heurística que garante um fator de dilatação de k · (⌊q|T|⌋ + 2), mas não limita o grau máximo de saída. Nos experimentos, a heurística mostrou-se extensível com relação ao grau máximo, além de sempre superar os outros algoritmos nesta métrica. A heurística gerou, adicionalmente, uma spanner com fator de violaçãao baixo.
Salvador
15
Matsubara, Camila Mari. "Algoritmos para o problema da árvore de Steiner com coleta de prêmios." Universidade de São Paulo, 2012. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-18082014-170526/.
Full textAbstract:
Neste projeto estudamos algoritmos de aproximação para o problema da árvore de Steiner com coleta de prêmios. Trata-se de uma generalização do problema da árvore de Steiner, onde é dado um grafo com custos positivos nas arestas e penalidades positivas nos vértices. O objetivo é encontrar uma subárvore do grafo que minimize a soma dos custos das arestas mais a soma das penalidades dos vértices que não pertencem à subárvore. Em 2009, os autores Archer, Bateni, Hajiaghayi e Karloff obtiveram pela primeira vez um algoritmo com fator de aproximação estritamente menor do que 2. Além de analisarmos este algoritmo, estudamos também a implementação de algoritmos 2-aproximação para o problema da árvore de Steiner e da árvore de Steiner com coleta de prêmios.In this project we analyze approximation algorithms for the prize-collecting Steiner tree problem. This is a generalization of the Steiner tree problem, in which it is given a graph with positive costs in edges and positive penalties in vertices. The goal is to find a subtree of the graph that minimizes the sum of costs of edges plus the sum of the penalties of the vertices that don\'t belong to the subtree. In 2009, the authors Archer, Bateni, Hajiaghayi e Karloff described, for the first time an algorithm with approximation factor strictly less than 2. Besides analyzing this algorithm, we also study the implementation of 2-approximation algorithms to the Steiner tree problem and prize-collecting Steiner tree problem.
16
Schornstein, Nancy M. "Computing the chromatic number of t-(v, k, [lambda]) designs. /." Online version of thesis, 1989. http://hdl.handle.net/1850/10617.
Full text
17
Amorim, Neto Alcides de Castro. "Problema de Steiner Euclidiano aplicado a moléculas de interesse biológico." Universidade Federal do Amazonas, 2007. http://tede.ufam.edu.br/handle/tede/3687.
Full textAbstract:
Made available in DSpace on 2015-04-22T22:16:13Z (GMT). No. of bitstreams: 1
Alcides de Castro Amorim Neto.pdf: 1160215 bytes, checksum: 9d45c01bd11518c19b4c0577a41c7455 (MD5)
Previous issue date: 2007-05-26CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
An old problem and of great application in the Applied Mathematics is known as problem of Steiner, with consists of the determination of a point that minimizes certain distances, problem this that was studied by famous mathematical as Fermat and Torricelli. A fundamental result in biochemistry and molecular modelling is the determination of the configurations of minimum energy (MECs) for structures such macromoleculares like proteins and DNA. The Steiner minimal trees (SMT) are seen as a useful algorithm paradigm to model these structures. In this work, we will examine how SMTs and the value of the ratio Steiner (½) compared with the MSTs are correlated with the energies MECs in a way physically significant. We verified that carbon and nitrogen atoms are Steiner points in the proteins minimal Steiner trees.
Um problema antigo e de grande aplicação na Matemática Aplicada é conhecido como problema de Steiner, que consiste na determinação de um ponto que minimize certas distâncias, problema este que foi estudado por outros matemáticos renomados como Fermat e Torricelli. Um dos resultados fundamentais em bioquímica e modelagem molecular é a determinação das Configurações de Energia Mínima (MECs) para estruturas macromoleculares tais como proteínas e DNA. As árvores mínimas de Steiner (SMTs) servem de base para elaboração de algoritmos úteis para modelar estas estruturas. Nesta dissertação, faremos uma revisão bibliográfica sobre o problema de Steiner e verificaremos, através de resultados da literatura, como as SMTs e o valor da razão de Steiner (½) comparado com as árvores geradoras mínimas MSTs estão correlacionadas com as MECs de uma maneira fisicamente significativa. Uma das observações relevantes é que os átomos de carbono e nitrogênio atuam como pontos de Steiner nas árvores mínimas de Steiner das proteínas.
18
Feldman, Jon 1975. "The Directed Steiner Network problem is tractable for a constant number of terminals." Thesis, Massachusetts Institute of Technology, 2000. http://hdl.handle.net/1721.1/86450.
Full text
19
Myung, Young-soo. "Valid Inequalities and Facets for the Steinger Problem in a Directed Graph." Massachusetts Institute of Technology, Operations Research Center, 1991. http://hdl.handle.net/1721.1/5223.
Full textAbstract:
In this paper, we describe the facial structure of the steiner problem in a directed graph by formulating it as a set covering problem. We first characterize trivial facets and derive a necessary condition for nontrivial facets. We also introduce a class of valid inequalities with 0-1 coefficients and show when such inequalities define facets.
20
Oliveira, Marcos Antônio Almeida de. "Heurística aplicada ao problema árvore de Steiner Euclidiano com representação nó-profundidade-grau." Universidade Federal de Goiás, 2014. http://repositorio.bc.ufg.br/tede/handle/tede/4171.
Full textAbstract:
Submitted by Luanna Matias (lua_matias@yahoo.com.br) on 2015-02-06T19:23:12Z
No. of bitstreams: 2
Dissertação - Marcos Antônio Almeida de Oliveira - 2014..pdf: 1092566 bytes, checksum: 55edbdaf5b3ac84fe3f6835682fe2a13 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-02-19T14:34:20Z (GMT) No. of bitstreams: 2 Dissertação - Marcos Antônio Almeida de Oliveira - 2014..pdf: 1092566 bytes, checksum: 55edbdaf5b3ac84fe3f6835682fe2a13 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Made available in DSpace on 2015-02-19T14:34:20Z (GMT). No. of bitstreams: 2 Dissertação - Marcos Antônio Almeida de Oliveira - 2014..pdf: 1092566 bytes, checksum: 55edbdaf5b3ac84fe3f6835682fe2a13 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-09-03
Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG
A variation of the Beasley (1992) algorithm for the Euclidean Steiner tree problem is presented. This variation uses the Node-Depth-Degree Encoding, which requires an average time of O(n) in operations to generate and manipulate spanning forests. For spanning tree problems, this representation has linear time complexity when applied to network design problems with evolutionary algorithms. Computational results are given for test cases involving instances up to 500 vertices. These results demonstrate the use of the Node-Depth-Degree in an exact heuristic, and this suggests the possibility of using this representation in other techniques besides evolutionary algorithms. An empirical comparative and complexity analysis between the proposed algorithm and a conventional representation indicates the efficiency advantages of the solution found.
É apresentada uma variação do algoritmo de Beasley (1992) para o Problema árvore de Steiner Euclidiano. Essa variação utiliza a Representação Nó-Profundidade-Grau que requer, em média, tempo O(n) em operações para gerar e manipular florestas geradoras. Para problemas de árvore geradora essa representação possui complexidade de tempo linear sendo aplicada em problemas de projeto de redes com algoritmos evolutivos. Resultados computacionais são dados para casos de teste envolvendo instâncias de até 500 vértices. Esses resultados demonstram a utilização da representação Nó-Profundidade-Grau em uma heurística exata, e isso sugere a possibilidade de utilização dessa representação em outras técnicas além de algoritmos evolutivos. Um comparativo empírico e da análise de complexidade entre o algoritmo proposto e uma representação convencional indica vantagens na eficiência da solução encontrada.
21
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.
22
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.
23
San, Felice Mário César 1985. "Online facility location and Steiner problems = Problemas online de localização de instalações e de Steiner." [s.n.], 2015. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275552.
Full textAbstract:
Orientador: Orlando LeeTese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-27T12:18:11Z (GMT). No. of bitstreams: 1 SanFelice_MarioCesar_D.pdf: 1457706 bytes, checksum: 4813f4ed44c52462656d56537d73d5dc (MD5) Previous issue date: 2015
Resumo: Nesta tese estudamos problemas online das famílias de localização de instalações e de Steiner, através da abordagem de análise competitiva. O objetivo nestes problemas é construir uma rede de custo mínimo para atender a uma determinada demanda. Nós apresentamos resultados conhecidos para o problema Online da Localização de Instalações (OFL), o problema Online da Árvore de Steiner (OST) e o problema Online Single-Source Rent-or-Buy (OSRoB). O OFL consiste em atender a um conjunto de clientes, através da abertura de algumas instalações e da conexão de cada cliente com uma instalação aberta. O OST tem por objetivo conectar um conjunto de terminais utilizando uma árvore, que pode conter vértices não terminais, chamados vértices de Steiner. O OSRoB é uma versão rent-or-buy do OST, onde todos os terminais devem ser conectados a um nó especial chamado raíz. Os algoritmos e técnicas que apresentamos para estes problemas são importantes no desenvolvimento dos nossos algoritmos para os problemas que consideramos. Apresentamos novos resultados para o problema Online da Localização de Instalações com Coleta de Prêmios (OPFL), o problema Online da Árvore Estrela de Steiner (OSTS), e o problema Online da Localização de Instalações Conectadas (OCFL). O OPFL é uma generalização do OFL, em que alguns clientes podem ficar desconectados mediante o pagamento de penalidades. O OSTS é uma variante do OST, em que os vértices possuem custos não negativos. O OCFL é uma combinação do OFL e do OST, em que um conjunto de clientes precisa ser atendido através da abertura de algumas instalações, da conexão de cada cliente com uma instalação aberta, e da construção de uma árvore, mais custosa, que conecta as instalações abertas
Abstract: In this thesis we study online problems from the facility location and Steiner families, through the point of view of competitive analysis. The goal in these problems is to build a minimum cost network to attend a certain demand. We present known results for the Online Facility Location problem (OFL), the Online Steiner Tree problem (OST) and the Online Single-Source Rent-or-Buy problem (OSRoB). The OFL consists of serving a set of clients by opening some facilities and by connecting each client to a facility. The OST aims to connect a set of terminals in order to create a tree network, that may contain nonterminals, called Steiner nodes. The OSRoB is a rent-or-buy version of the OST, in which all terminals must be connected to a special node called root. The algorithms and techniques that we present for these problems play an important role in the design of our algorithms for the problems we consider. We present new results for the Online Prize-Collecting Facility Location problem (OPFL), the Online Steiner Tree Star problem (OSTS), and the Online Connected Facility Location problem (OCFL). The OPFL is a generalization of the OFL, in which some clients may be left unconnected by paying a penalty. The OSTS is a variant of the OST, in which the nodes have non-negative costs. The OCFL is a combination of the OFL and the OST, in which a set of clients needs to be served by opening some facilities, by connecting each client to a facility, and by creating a more expensive tree network that connects the open facilities
Doutorado
Ciência da Computação
Doutor em Ciência da Computação
24
Merabet, Massinissa. "Solutions optimales des problèmes de recouvrement sous contraintes sur le degré des nœuds." Thesis, Montpellier 2, 2014. http://www.theses.fr/2014MON20138/document.
Full textAbstract:
Le travail que nous développons dans le cadre de cette thèse s'articule autour des problèmes de recherche de structure de recouvrement de graphes sous contrainte sur le degré des sommets. Comme l'arbre de recouvrement couvre les sommets d'un graphe connexe avec un minimum de liens, il est généralement proposé comme solution à ce type de problèmes. Cependant, pour certaines applications telles que le routage dans les réseaux optiques, les solutions ne sont pas nécessairement des sous-graphes. Nous supposons dans cette thèse que la contrainte sur le degré est due à une capacité limitée instantanée des sommets et que la seule exigence sur le recouvrement est sa connexité. Dans ce cas, la solution peut être différente d'un arbre. Nous reformulons ces problèmes de recouvrement en nous appuyant sur une extension du concept d'arbre appelée hiérarchie de recouvrement. Notre objectif principal est de démontrer son intérêt vis-à-vis de l'arbre en termes de faisabilité et de coût du recouvrement. Nous considérons deux types de contraintes sur le degré : des bornes sur le degré des sommets ou une borne sur le nombre de sommets de branchement et cherchons dans les deux cas un recouvrement de coût minimum. Nous illustrons aussi l'applicabilité des hiérarchies en étudiant un problème prenant davantage en compte la réalité du routage optique. Pour ces différents problèmes NP-difficiles, nous montrons, tant sur le coût des solutions optimales que sur la garantie de performance des solutions approchées, l'intérêt des hiérarchies de recouvrement. Ce constat se voit conforté par des expérimentations sur des graphes aléatoiresThe work conducted in this thesis is focused on the minimum spanning problems in graphs under constraints on the vertex degrees. As the spanning tree covers the vertices of a connected graph with a minimum number of links, it is generally proposed as a solution for this kind of problems. However, for some applications such as the routing in optical networks, the solution is not necessarily a sub-graph. In this thesis, we assume that the degree constraints are due to a limited instantaneous capacity of the vertices and that the only pertinent requirement on the spanning structure is its connectivity. In that case, the solution may be different from a tree. We propose the reformulation of this kind of spanning problems. To find the optimal coverage of the vertices, an extension of the tree concept called hierarchy is proposed. Our main purpose is to show its interest regarding the tree in term of feasibility and costs of the coverage. Thus, we take into account two types of degree constraints: either an upper bound on the degree of vertices and an upper bound on the number of branching vertices. We search a minimum cost spanning hierarchy in both cases. Besides, we also illustrate the applicability of hierarchies by studying a problem that takes more into account the reality of the optical routing. For all those NP-hard problems, we show the interest of the spanning hierarchy for both costs of optimal solutions and performance guarantee of approximate solutions. These results are confirmed by several experimentations on random graphs
25
Mudgal, Apurva. "Worst-case robot navigation in deterministic environments." Diss., Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/33924.
Full textAbstract:
We design and analyze algorithms for the following two robot navigation problems:
1. TARGET SEARCH. Given a robot located at a point s in the plane, how will a robot navigate to a goal t in the presence of unknown
obstacles ?
2. LOCALIZATION. A robot is "lost" in an environment with a map of its surroundings. How will it find its true location by traveling the minimum distance ?
Since efficient algorithms for these two problems will make a robot completely autonomous, they have held the interest of both robotics and computer science communities.
Previous work has focussed mainly on designing competitive algorithms where the robot's performance is compared to that of an omniscient adversary. For example, a competitive algorithm for target search will compare the distance traveled by the robot with the shortest path from
s to t.
We analyze these problems from the worst-case perspective, which, in our view, is a more appropriate measure. Our results are :
1. For target search, we analyze an algorithm called Dynamic A*. The robot continuously moves to the goal on the shortest path which it recomputes on the discovery of obstacles. A variant of this algorithm has been employed in Mars Rover prototypes.
We show that D* takes O(n log n) time on planar graphs and also show a comparable bound on arbitrary graphs. Thus, our results show that D* combines the optimistic possibility of reaching the goal very soon while competing with depth-first search within a logarithmic factor.
2. For the localization problem, worst-case analysis compares the performance of the robot with the optimal decision tree over the set of possible locations.
No approximation algorithm has been known. We give a polylogarithmic approximation algorithm and also show a near-tight lower bound for the grid graphs commonly used in practice. The key idea is to plan travel on a "majority-rule map" which eliminates uncertainty and permits a link to the half-Group Steiner problem. We also extend the problem to polygonal maps by discretizing the domain using novel geometric techniques.
26
Vyoral, Martin. "Aplikácia modifikovaného Steinerovho stromu na problém rozvodu elektrickej siete v projekte Desertec." Master's thesis, Vysoká škola ekonomická v Praze, 2012. http://www.nusl.cz/ntk/nusl-163927.
Full textAbstract:
The aim of the thesis was minimize the planned cost of construction of the electricity network in North Africa and the Arabian peninsula between solar power plant in Desertec project. The work is divided into three chapters. The first chapter is devoted Desertec concept, its key technologies, benefits and barriers. Another chapter is devoted to the theory of graphs. It consists of an introduction to graph theory, minimum spanning tree and Steiner tree. The third practical chapter is devoted to reduction of the initial projected cost of constructing Electric Supply network using Steiner tree and its modifications. It also addresses the issue of valuation of edges and nodes to which it is necessary to include a number of factors such as energy capacity to be transmitted, the type of transmission medium, environmental conditions, geomorphological aspects and other safety regulatory requirements.
27
Capelli, Lorenzo. "Alcuni problemi enumerativi sulle coniche." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2020. http://amslaurea.unibo.it/20621/.
Full textAbstract:
Un problema in geometria è di tipo enumerativo se si cerca di calcolare il numero di certi oggetti geometrici, sotto certe condizioni che lo rendano finito. Tra questi, uno dei più noti, risale al 1848 ed è il problema di Jacob Steiner, professore di geometria all’Università di Berlino: “Date cinque coniche del piano proiettivo, quante sono le coniche tangenti a tutte cinque?”. Nel primo capitolo di questa tesi si richiamano le definizioni sulle coniche affini e proiettive mentre nel secondo si studia il problema di Steiner.
28
Tan, Kunlun. "On the Role of Partition Inequalities in Classical Algorithms for Steiner Problems in Graphs." Thesis, University of Waterloo, 2006. http://hdl.handle.net/10012/1123.
Full textAbstract:
The Steiner tree problem is a classical, well-studied, $\mathcal{NP}$-hard optimization problem. Here we are given an undirected graph $G=(V,E)$, a subset $R$ of $V$ of terminals, and non-negative costs $c_e$ for all edges $e$ in $E$. A feasible Steiner tree for a given instance is a tree $T$ in $G$ that spans all terminals in $R$. The goal is to compute a feasible Steiner tree of smallest cost. In this thesis we will focus on approximation algorithms for this problem: a $c$-approximation algorithm is an algorithm that returns a tree of cost at most $c$ times that of an optimum solution for any given input instance. In a series of papers throughout the last decade, the approximation guarantee $c$ for the Steiner tree problem has been improved to the currently best known value of 1. 55 (Robins, Zelikovsky). Robins' and Zelikovsky's algorithm as well as most of its predecessors are greedy algorithms.
Apart from algorithmic improvements, there also has been substantial work on obtaining tight linear-programming relaxations for the Steiner tree problem. Many undirected and directed formulations have been proposed in the course of the last 25 years; their use, however, is to this point mostly restricted to the field of exact optimization. There are few examples of algorithms for the Steiner tree problem that make use of these LP relaxations. The best known such algorithm for general graphs is a 2-approximation (for the more general Steiner forest problem) due to Agrawal, Klein and Ravi. Their analysis is tight as the LP-relaxation used in their work is known to be weak: it has an IP/LP gap of approximately 2.
Most recent efforts to obtain algorithms for the Steiner tree problem that are based on LP-relaxations has focused on directed relaxations. In this thesis we present an undirected relaxation and show that the algorithm of Robins and Zelikovsky returns a Steiner tree whose cost is at most 1. 55 times its optimum solution value. In fact, we show that this algorithm can be viewed as a primal-dual algorithm.
The Steiner forest problem is a generalization of the Steiner tree problem. In the problem, instead of only one set of terminals, we are given more than one terminal set. An feasible Steiner forest is a forest that connects all terminals in the same terminal set for each terminal set. The goal is to find a minimum cost feasible Steiner forest. In this thesis, a new set of facet defining inequalities for the polyhedra of the Steiner forest is introduced.
29
Silva, Thiago Gouveia da. "Métodos heurísticos aplicados ao problema da árvore de Steiner rectilinear." Universidade Federal da Paraíba, 2009. http://tede.biblioteca.ufpb.br:8080/handle/tede/6140.
Full textAbstract:
Made available in DSpace on 2015-05-14T12:36:55Z (GMT). No. of bitstreams: 1
parte1.pdf: 1169586 bytes, checksum: 685986454ee5e2cc58d709e7d646732f (MD5)
Previous issue date: 2009-08-28Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
This work presents a new heuristic, called Heurística 1, and the implementations of the GRASP, Simulated Annealing and Genetic Algorithms metaheuristics for the rectilinear Steiner minimum tree problem (RSMTP), talking about its theoretical aspects, like computational complexity, and practical ones, like pseudo-codes and implementation strategies. The new techniques for RSMTP presented, especially the Genetic Algorithms, have computational results of superior quality in comparison to the best heuristics in present litera
Este trabalho apresenta uma nova heurística, denominada Heurística 1, e a implementação das metaheurísticas GRASP, Simulated Annealing e Algoritmos Genéticos para o problema da árvore retilínea mínima de Steiner (RSMTP), discorrendo sobre seus aspectos teóricos, como a complexidade computacional; e práticos, como pseudocódigos e estratégias de implementação. As novas abordagens para o RSMTP apresentadas, em especial os Algoritmos Genéticos, ostentam resultados computacionais de qualidade superior às apresentadas pelas melhores heurísticas da literatura atual.
30
Lenel, Friederike [Verfasser], Georg [Gutachter] Weizsäcker, and Susan [Gutachter] Steiner. "Informal Support and Insurance / Friederike Lenel ; Gutachter: Georg Weizsäcker, Susan Steiner." Berlin : Humboldt-Universität zu Berlin, 2017. http://d-nb.info/1189428091/34.
Full text
31
Fonseca, Ricardo Santos. "Problemas de otimização na Geometria: uma abordagem para o Ensino Médio." Universidade Federal do Amazonas, 2016. http://tede.ufam.edu.br/handle/tede/5473.
Full textAbstract:
Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-01T19:31:46Z
No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertação - Ricardo Santos Fonseca.pdf: 3884170 bytes, checksum: c7f03d9fc12e685aabc06b6b6794a61b (MD5)Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-01T19:32:02Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Ricardo Santos Fonseca.pdf: 3884170 bytes, checksum: c7f03d9fc12e685aabc06b6b6794a61b (MD5)
Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-01T19:32:17Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Ricardo Santos Fonseca.pdf: 3884170 bytes, checksum: c7f03d9fc12e685aabc06b6b6794a61b (MD5)
Made available in DSpace on 2017-02-01T19:32:17Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Ricardo Santos Fonseca.pdf: 3884170 bytes, checksum: c7f03d9fc12e685aabc06b6b6794a61b (MD5) Previous issue date: 2016-08-04
CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
In this work, lectures on Optimization Problems Applied Geometry. It presents initially a little history of some classic optimization problems in Euclidean Geometry Plana, as the Isoperimétrico Problem, the Heron Problem an the Steiner Problem. From there, he used that knowledge to build definitions, theorems and propositions regarding the Optimization of Geometry which provided grandiose tools for problem solving that can be applied in high school or in Mathematics Olympics.
Neste trabalho, disserta-se sobre Problemas de Otimização Aplicados à Geometria. Apresentase inicialmente um pouco da história de alguns problemas clássicos de otimização em Geometria Euclidiana Plana, como, o Problema Isoperimétrico, o Problema de Heron e o Problema de Steiner. A partir daí, usou-se esse conhecimento para construir definições, teoremas e proposições a respeito da Otimização em Geometria o que proporcionou grandiosas ferramentas para a resolução de problemas que podem ser aplicados no Ensino Médio ou em Olimpíadas de Matemática.
32
Baïou, Mourad. "Le probleme du sous-graphe steiner 2-arete connexe : approche polyedrale." Rennes 1, 1996. http://www.theses.fr/1996REN10197.
Full textAbstract:
Un graphe g est dit 2-arete-connexe si entre chaque paire de sommets de g, il existe au moins deux chaines arete-disjointes. Si les aretes sont munies d'un systeme de poids, et si s est un ensemble de sommets distingues de g, le probleme du sous-graphe steiner 2-arete-connexe de g est de determiner un sous-graphe 2-arete-connexe contenant s, de poids minimum. Ce probleme a des applications dans les domaines des telecommunications et de transport. Dans cette these nous etudions une approche polyedrale pour ce probleme. Dans une premiere partie, nous etudions le polyedre associe a ce probleme. Nous donnons une description lineaire complete de ce polyedre quand le graphe est serie-parallele. Nous discutons par la suite de certains polyedres lies au polytope des sous-graphes steiner 2-arete-connexes. Nous examinons tout particulierement le polytope du voyageur de commerce steiner et nous en donnons une description lineaire complete dans la classe des graphes serie-paralleles. Dans la deuxieme partie, nous etudions une methode de coupes pour le probleme du sous-graphe 2-arete-connexe (ou tous les sommets de s ont le meme comportement). Dans un premier temps nous etudions la famille de contraintes dites de partition. En utilisant un algorithme recent de queyranne pour determiner le minimum d'une fonction sous-modulaire symetrique, nous montrons que le probleme de separation associe a ces contraintes peut etre resolu en temps polynomial. Ces contraintes sont utilisees par la suite dans un algorithme de coupes et branchement pour resoudre certaines instances du probleme du sous-graphe 2-arete-connexe. La meme approche est aussi utilisee pour resoudre des instances du probleme du voyageur de commerce. Les resultats experimentaux montrent que les contraintes de partition sont tres efficaces pour resoudre ces problemes
33
Bennett, Geoffrey Keith. "Topological embeddings of Steiner triple systems and associated problems in design theory." Thesis, Open University, 2004. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.402268.
Full text
34
Judkovich, David. "Variations on the Matching Problem." Case Western Reserve University School of Graduate Studies / OhioLINK, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=case1554308993793382.
Full text
35
SILVA, Itacira Ataide. "Problema de Apolônio alguns números característicos das cônicas planas." Universidade Federal de Pernambuco, 2012. https://repositorio.ufpe.br/handle/123456789/11691.
Full textAbstract:
Submitted by Etelvina Domingos (etelvina.domingos@ufpe.br) on 2015-03-10T17:15:17Z
No. of bitstreams: 2
license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5)
dissertacao -Itacira Ataide Silva.pdf: 594325 bytes, checksum: a64733dd2d06f140c960cee9bf78c4bc (MD5)Made available in DSpace on 2015-03-10T17:15:17Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) dissertacao -Itacira Ataide Silva.pdf: 594325 bytes, checksum: a64733dd2d06f140c960cee9bf78c4bc (MD5) Previous issue date: 2012
Neste trabalho, faremos uma construção geométrica de soluções para o Problema de Apolônio e usaremos algumas ferramentas da Geometria Enumerativa para resolver o Problema de Steiner.
36
Giesbert, Lena-Anna [Verfasser], Tilman [Akademischer Betreuer] Brück, Susan [Akademischer Betreuer] Steiner, and Eva [Akademischer Betreuer] Terberger. "Microinsurance and risk management : evidence from Ghana / Lena-Anna Giesbert. Gutachter: Tilman Brück ; Susan Steiner ; Eva Terberger." Berlin : Humboldt Universität zu Berlin, Landwirtschaftlich-Gärtnerische Fakultät, 2014. http://d-nb.info/1047622408/34.
Full text
37
MONTLAUR, MARIE-CLAIRE. "Problemes respiratoires au cours de la dystrophie myotonique de steinert." Montpellier 1, 1993. http://www.theses.fr/1993MON11077.
Full text
38
Brás, Raúl Massano. "Uma variante do problema da floresta de Steiner em grafos com aplicações em biologia da conservação." Doctoral thesis, Instituto Superior de Economia e Gestão, 2013. http://hdl.handle.net/10400.5/6124.
Full textAbstract:
Doutoramento em Matemática Aplicada à Economia e à GestãoA fragmentação de habitats é uma ameaça séria à sustentabilidade das espécies ecológicas. Assim, a identificação de ligações eficientes entre unidades ecológicas, é uma questão importante em biologia da conservação. O estabelecimento de ligações eficientes, deve levar em conta que as áreas que são adequadamente permeáveis para a dispersão de algumas espécies, podem agir como obstáculos para outras. A determinação de ligações eficazes, com custo míınimo, é uma generalização dos problemas da árvore Steiner com custos nos nós e da floresta de Steiner com custos dos nós. A tese apresenta e compara formulações e heurísticas para este problema. As heurísticas foram especialmente concebidas para lidar com instâncias de grande dimensão, que ocorrem em biologia da conservação. As heurísticas são comparadas utilizando dados simulados e reais para a Península Ibérica. Uma vez que o problema da floresta de Steiner com custos nos nós é um caso particular do problema estudado, as heurísticas propostas são também comparadas com uma heurística bem conhecida para este caso. A elaboração da tese, levou ao desenvolvimento de uma aplicação informática de código aberto, que foi colocada à disposição da comunidade científica.
Habitat fragmentation is a serious threat for the sustainability of species. Thus, the identification of effective linkages to connect valuable ecological units is an important issue in conservation biology. The design of effective linkages should take into account that areas which are adequately permeable for some species’ dispersal may act as obstructions for other species. The determination of minimum cost effective linkages is a generalization of both node-weighted Steiner tree and node-weighted Steiner forest problems. The thesis presents and compares formulations and heuristics to this problem. The heuristics were specially conceived to handle large instances that occur in conservation biology. The heuristics are compared using both simulated and real data for the Iberian Peninsula. Since the node weighted Steiner forest problem is a special case of the problem studied, the proposed heuristics are also compared to a well established heuristic for this case. The dissertation resulted in the development of an open source application that was made available to the scientific community.
39
Steiger, Ignaz [Verfasser]. "Die Auswirkungen von Wohnungslosigkeit auf die Gesundheit und den Zugang in das Gesundheitssystem / Ignaz Steiger." Berlin : Medizinische Fakultät Charité - Universitätsmedizin Berlin, 2010. http://d-nb.info/1024004147/34.
Full text
40
Sahutoglu, Sonmez. "Compactness of the dbar-Neumann problem and Stein neighborhood bases." Texas A&M University, 2003. http://hdl.handle.net/1969.1/3879.
Full textAbstract:
This dissertation consists of two parts. In the first part we show that for 1 k 1, a complex manifold M of dimension at least k in the boundary of a smooth
bounded pseudoconvex domain
in Cn is an obstruction to compactness of the @-
Neumann operator on (p, q)-forms for 0 p k n, provided that at some point
of M, the Levi form of b
has the maximal possible rank n − 1 − dim(M) (i.e. the
boundary is strictly pseudoconvex in the directions transverse to M). In particular,
an analytic disc is an obstruction to compactness of the @-Neumann operator on
(p, 1)-forms, provided that at some point of the disc, the Levi form has only one
vanishing eigenvalue (i.e. the eigenvalue zero has multiplicity one). We also show
that a boundary point where the Levi form has only one vanishing eigenvalue can
be picked up by the plurisubharmonic hull of a set only via an analytic disc in the
boundary.
In the second part we obtain a weaker and quantified version of McNealÂs Property
( eP) which still implies the existence of a Stein neighborhood basis. Then we give
some applications on domains in C2 with a defining function that is plurisubharmonic
on the boundary.
41
Ma, Yilin. "Nonlinear Calderón Problem on Stein Manifolds." Thesis, The University of Sydney, 2021. https://hdl.handle.net/2123/25757.
Full textAbstract:
This thesis is devoted to the study of inverse problems for semilinear elliptic equations on Stein manifolds with Kähler metric. After developing some preliminary techniques, we will show that the Dirichlet-Neumann maps for certain semilinear elliptic equations determine the nonlinearities. We will consider two inverse problems of this kind with distinct geometric conditions imposed. The first one is the inverse problem for nonlinear Schrödinger equations on Kähler manifolds having specific Stein-like properties. The second one is the inverse problem for nonlinear magnetic Schrödinger equations on Riemann surfaces with partial data boundary measurements. In both cases, the nonlinearities involved are assumed to have certain analytic representations and vanishing lower order terms. The key observation is that, by a suitable linearisation procedure, one could transform the nonlinear problems into series of linear problems which have close connections to the techniques we develop.
42
Steiger, Lara [Verfasser]. "Gleiches Recht für alle – auch für Sexualstraftäter? : Sonderregelungen für Sexualstraftäter im Strafrecht und ihre kriminologische Berechtigung. / Lara Steiger." Berlin : Duncker & Humblot, 2016. http://d-nb.info/1238438547/34.
Full text
43
Jardrin, Jean-Louis. "Nouvelle approche du problème de Steiner dans les graphes pour un nombre fixe de sommets à connecter." Paris, EHESS, 1994. http://www.theses.fr/1994EHES0086.
Full textAbstract:
Ce travail porte sur le probleme de steiner dans les graphes (psg). Il presente des algorithmes exacts et des algorithmes approches originaux pour le psg, dans les deux cas : non orientes et orientes. Il propose une nouvelle caracterisation d'une solution du psg, comme reunion de plus courtes chaines ou de plus courts chemins du graphe considere, selon que celui-ci est non oriente ou oriente, et il montre qu'une solution du psg se deduit du minimum d'un certain ensemble de configurations qui peut etre determine explicitement, des lors que le nombre de sommets a connecter est fixe. Ces proprietes generales sont a la base des algorithmes proposes. Ceux-ci procedent par enumeration implicite (directe ou par recherche arborescente), et ils sont specialises, en ce que chacun d'entre eux ne traite que des problemes ayant un nombre fixe de sommets a connecter (6 au plus). Les resultats obtenus dans des experiences de calcul mettant en oeuvre ces algorithmes montrent que cette nouvelle approche du psg est digne d'interetThis work is concerned with the steiner problem in graphs (spg). It presents original exact and approximation algorithms for the spg, in the two cases : undirected and directed. It proposes a new characterization of a spg solution, as the union of shortest chains or paths of the considered graph, depending on whether it is undirected or directed, and it shows that a spg solution can be deduced from the minimum of some set of configurations which can be constructed explicity whenever the number of vertices to connect is fixed. These general properties are the basis of the proposed algorithms. These algorithms are (direct or tree search) implicit enumeration algorithms, and they are specialized in the sense that each only solves problems with a fixed number of vertices to connect (6 at most). The computational results about these algorithms show that this new approach of the spg is of some interest
44
Bernot, Marc. "Transport optimal et irrigation." Phd thesis, École normale supérieure de Cachan - ENS Cachan, 2005. http://tel.archives-ouvertes.fr/tel-00132078.
Full textAbstract:
L'objet de cette thèse est de modéliser et d'étudier des structures d'irrigation telles les nervures des feuilles, réseau sanguin, poumons,etc. Un modèle généralisant le problème de Gilbert Steiner est introduit ; on étudie alors les propriétés d'existence, de stabilité et régularité. Des algorithmes sont alors proposés pour la simulation.
45
Steiner, Barbara [Verfasser], and Hans-Werner [Akademischer Betreuer] Wahl. ""Unterstütztes Wohnen" für ältere Menschen mit Hilfe- und Pflegebedarf als neues Paradigma? Aspekte der Lebensqualität einer neuen kleingemeinschaftlichen Wohnform. / Barbara Steiner ; Betreuer: Hans-Werner Wahl." Heidelberg : Universitätsbibliothek Heidelberg, 2015. http://d-nb.info/1180614070/34.
Full text
46
Steimer, Michael [Verfasser], Harun [Akademischer Betreuer] Parlar, Roland [Akademischer Betreuer] Meyer-Pittroff, and Susanne [Akademischer Betreuer] Gerbl-Rieger. "Evaluierung von Rahmenbedingungen für Monitoring Systeme zur Erfassung der Pflanzenschutzmittelbelastung in den EU-Anrainerstaaten / Michael Steimer. Gutachter: Harun Parlar ; Roland Meyer-Pittroff. Betreuer: Susanne Gerbl-Rieger ; Harun Parlar." München : Universitätsbibliothek der TU München, 2011. http://d-nb.info/1014330092/34.
Full text
47
Moraes, Mak Alisson Borges de. "O problema mente-corpo na psicologia fenomenológica de Edith Stein : implicações para uma fundamentação da ciência psicológica." Universidade Federal de Ubelândia, 2016. https://repositorio.ufu.br/handle/123456789/17566.
Full textAbstract:
Fundação de Amparo a Pesquisa do Estado de Minas GeraisA Psicologia é um ramo científico relativamente novo e que ainda carece de alicerces metodológicos consistentes para sustentar suas investigações. Dado sua imaturidade, essa ciência encontra dificuldades para delimitar seu estatuto ontológico, o que gera diversos equívocos epistemológicos e metodológicos. Diante disso, a Psicologia não tem conseguido demarcar de forma precisa seu objeto de estudo, ocasionando assim o surgimento de inúmeras concepções a respeito do psíquico, o que resultou na fragmentação dessa ciência. Na sua constituição a ciência psicológica herdou um complexo problema filosófico: a questão mente-corpo. Portanto, para definir seu estatuto a Psicologia deve ainda enfrentar esse problema, buscando elucidar: o que é a mente, o que é o corpo e como eles se relacionam. Em virtude da importância dessa questão e para uma demarcação rigorosa do objeto psicológico, buscou-se nessa pesquisa investigar o problema mente-corpo à luz da Psicologia Fenomenológica de Edith Stein (1891-1942), filósofa e fenomenóloga que empreendeu notáveis esforços para uma fundamentação da Psicologia. Para isso, a discussão foi subsidiada a partir dos aportes da Filosofia da Mente e das contribuições do método fenomenológico para o problema mente-corpo. A partir daí, através de uma metodologia qualitativa bibliográfica, procurou-se examinar o problema de pesquisa através da análise de algumas obras filosófico-psicológicas da filósofa, a saber: “Causalidade Psíquica” (Psychische Kausalität, 1922) e “Introdução à Filosofia” (Einführung in die Philosophie, 1920). Para essa investigação, realizou-se sem prejuízo à discussão uma equivalência terminológica entre os termos mente e psique, visto que a fenomenóloga utilizou esse último para se referir ao objeto da Psicologia. Procurou-se analisar, portanto, como Stein concebeu a psique, o corpo e a relação entre ambos. Apesar de não ser o foco da investigação, levou-se em conta também a dimensão espiritual, visto que a filósofa concebeu a pessoa humana como constituída por três dimensões: corpo, psique e espírito. Assim, Stein destacou o mecanismo causal da psique, o qual tem como fundamento as variações da força vital que desponta a partir da esfera vital. Em relação à dimensão corpórea, a filósofa, seguindo as análises de Edmund Husserl (1859-1938), destacou o duplo aspecto do corpo, que é ao mesmo tempo uma coisa material (Körper) e também corpo-vivo (Leib). Em face disso, entende-se que a psique e o corpo estão intimamente conectados, de modo que constituem uma unidade-dual que se manifesta no Leib. Essa compreensão do problema psique-mente/corpo proporciona uma rica análise dessa questão, propiciando a superação de algumas incoerências das posições clássicas monistas e dualistas. Diante disso, possibilita uma rigorosa elucidação do objeto da Psicologia, contribuindo para a fundamentação dessa ciência.
Psychology is a relatively new scientific branch and still lacks consistent methodological foundation to support its investigations. Given its immaturity, this science finds difficulties to delimit its ontological status, which spawnes several epistemological and methodological misconceptions. Given this, Psychology failed to demarcate precisely its object of study, leading, thus, the emergence of numerous conceptions about the psychic, which resulted in the fragmentation of this science. In its constitution, psychological science inherited a complex philosophical problem: the mind-body issue. Therefore, to define their status, Psychology must still face this problem, seeking to elucidate what is the mind, the body and how they relate. In light of the importance of this issue to a strict demarcation of psychological object, it was sought in this research, to investigate the mind-body problem in the Phenomenological Psychology of Edith Stein (1891-1942), phenomenologist philosopher who undertook efforts for a foundation of Psychology. For that, the discussion was subsidized from the contributions of the Philosophy of Mind and the support of the phenomenological method to the mind-body problem. From there, by a qualitative bibliographical methodology, it sought to examine the problem of research through the analysis of some philosophical-psychological philosopher's works, named: "Psychic Causality” (Kausalität Psychische, 1922) and “Introduction to Philosophy" (Einführung in die Philosophie, 1920). For this investigation, it was made, without prejudice to the discussion, a terminological equivalence between the terms mind and psyche, as the philosopher used the latter to refer to the object of Psychology. It sought to examine, therefore, how Stein conceived the psyche, the body and the relationship between them. Although it wasn't the focus of the investigation, it also took into account the spiritual dimension, as the philosopher conceived the human person as consisting of three dimensions: body, psyche and spirit. Given this, Stein highlighted the causal mechanism of the psyche, which is based on the variations of the vital force that emerges from the vital sphere. In relation to the corporeal dimension, the philosopher, following the analysis of Edmund Husserl (1859-1938), highlighted the dual aspect of the body, because it is at the same time something material (Körper) and also a linving body (Leib). On the face of it, it is understood that the psyche and the body are closely connected, so that it constitutes a dual-unit which is manifested in the Leib. This understanding of the problem psyche-mind/body provides a rich analysis of this issue, enabling the overcoming of some inconsistencies of the monistic and dualistic positions. Given this, it allows a strict elucidation of the Psychology object, contributing to the foundation of this science.
Dissertação (Mestrado)
48
Steinig, Simeon [Verfasser], and Kunibert G. [Akademischer Betreuer] Siebert. "Adaptive finite elements for state-constrained optimal control problems - convergence analysis and a posteriori error estimation / Simeon Steinig. Betreuer: Kunibert G. Siebert." Stuttgart : Universitätsbibliothek der Universität Stuttgart, 2014. http://d-nb.info/106430897X/34.
Full text
49
Schmidt, Cristine Cunha. "Uma abordagem atrav?s de algoritmos transgen?ticos para o problema da configura??o do tra?ado de uma rede de distribui??o de g?s natural." Universidade Federal do Rio Grande do Norte, 2007. http://repositorio.ufrn.br:8080/jspui/handle/123456789/18118.
Full textAbstract:
Made available in DSpace on 2014-12-17T15:48:12Z (GMT). No. of bitstreams: 1
CristineCS.pdf: 714473 bytes, checksum: 61f78bdfcd48bd6e64e25178e846e81b (MD5)
Previous issue date: 2007-02-08Este trabalho apresenta um algoritmo transgen?tico h?brido para a solu??o de um Problema de Configura??o de uma Rede de Distribui??o de G?s Natural. O problema da configura??o dessas redes requer a defini??o de um tra?ado por onde os dutos devem ser colocados para atender aos clientes. ? estudada neste trabalho uma maneira de conectar os clientes em uma rede com arquitetura em forma de ?rvore. O objetivo ? minimizar o custo de constru??o da rede, mesmo que para isso alguns clientes que n?o proporcionam lucros deixem de ser atendidos. Esse problema pode ser formulado computacionalmente atrav?s do Problema de Steiner com Pr?mios. Este ? um problema de otimiza??o combinat?ria da classe dos NP?rduos. Este trabalho apresenta um algoritmo heur?stico para a solu??o do problema. A abordagem utilizada ? chamada de Algoritmos Transgen?ticos, que se enquadram na categoria dos algoritmos evolucion?rios. Para a gera??o de solu??es inicias ? utilizado um algoritmo primaldual, e pathrelinking ? usado como intensificador
50
Manouvrier, Jean-François. "Méthode de décomposition pour résoudre des problèmes combinatoires sur les graphes." Compiègne, 1998. http://www.theses.fr/1998COMP1152.
Full textAbstract:
Les travaux de cette thèse utilisent une méthode de décomposition pour résoudre des problèmes combinatoires NP-difficiles énoncés sous la forme de problèmes de graphes. Parmi les méthodes exactes existantes, les méthodes utilisant une décomposition-arbre du graphe permettent de résoudre certains problèmes NP-difficiles en temps polynomial pour un graphe de largeur-arbre inferieur à K. K est une constante fixée en fonction du problème et des capacités de la machine utilisée. Nous nommons ces méthodes de programmation dynamique : méthodes de décomposition. Dans cette thèse, nous utilisons une décomposition-chemin du graphe, basée sur une numérotation linéaire des sommets du graphe, pour résoudre certains problèmes NP-difficiles. Les problèmes que nous avons ainsi traites sont les problèmes de la fiabilité des réseaux (fiabilité tous-terminaux et fiabilité 2-arête-connexe tous-terminaux), le problème du voyageur de commerce et le problème de l'arbre de Steiner minimal. Pour chacun de ces problèmes, nous étudions les autres méthodes existantes, nous démontrons que la méthode de décomposition peut être appliquée, en modélisant des classes d'équivalences regroupant des solutions partielles, et nous analysons l'implémentation de ces méthodes. Une des difficultés essentielles de l'implémentation des programmes de décomposition consiste à gérer efficacement en mémoire les classes. Pour la fiabilité 2-arête-connexe tous-terminaux, la structure des classes nous a contraints à introduire un concept de forêts fictives et à développer un algorithme énumérant ces forêts. Nous obtenons ainsi des algorithmes de décomposition résolvant ces problèmes, dont les complexités en temps sont linéaires en fonction de la taille du graphe pour des graphes de largeur-chemin bornée.