检索结果-内蒙古大学图书馆

A Multi-Commodity Flow Based Model for Multi Layer Hierarchical Ring Network Design

Electronic Notes in Discrete Mathematics 2016年 52卷 189-196页

作者： Schauer, Christian Raidl, Günther R. Institute of Computer Graphics and Algorithms TU Wien Vienna Austria

We address the Multi Layer Hierarchical Ring Network Design Problem. The aim of this problem is to connect nodes that are assigned to different layers using a hierarchy of rings of bounded length. We present a multi-commodity flow based mixed integer linear programming formulation and experimentally evaluate it on various graphs. Instances up to 76 nodes and 281 edges could be solved to optimality. © 2016 Elsevier B.V.

关键词： Dual homing Hierarchical network design Multi-commodity flow

来源：评论

学校读者我要写书评

暂无评论

Solving a k-node minimum label spanning arborescence problem to compress fingerprint templates

引用

Journal of Mathematical Modelling and algorithms 2009年第3期8卷 293-334页

作者： Chwatal, Andreas M. Raidl, Günther R. Oberlechner, Karin Institute of Computer Graphics and Algorithms Vienna University of Technology Vienna Austria

We present a novel approach for compressing relatively small unordered data sets by means of combinatorial optimization. The application background comes from the field of biometrics, where the embedding of fingerprint template data into images by means of watermarking techniques requires extraordinary compression techniques. The approach is based on the construction of a directed tree, covering a sufficient subset of the data points. The arcs are stored via referencing a dictionary, which contains "typical" arcs w.r.t. the particular tree solution. By solving a tree-based combinatorial optimization problem we are able to find a compact representation of the input data. As optimization method we use on the one hand an exact branch-and-cut approach, and on the other hand heuristics including a greedy randomized adaptive search procedure (GRASP) and a memetic algorithm. Experimental results show that our method is able to achieve higher compression rates for fingerprint (minutiae) data than several standard compression algorithms. © Springer Science + Business Media B.V. 2009.

关键词： Biometric template compression Combinatorial optimization Fingerprint minutiae GRASP Memetic algorithm Metaheuristics Unordered data set compression

来源：评论

学校读者我要写书评

暂无评论

Branch-and-Cut-and-Price for Capacitated Connected Facility Location

引用

Journal of Mathematical Modelling and algorithms 2011年第3期10卷 245-267页

作者： Leitner, Markus Raidl, Günther R. Institute of Computer Graphics and Algorithms Vienna University of Technology Vienna Austria

We consider a generalization of the Connected Facility Location Problem (ConFL), suitable to model real world network extension scenarios such as fiber-to-the-curb. In addition to choosing a set of facilities and connecting them by a Steiner tree as in ConFL, we aim to maximize the resulting profit by potentially supplying only a subset of all customers. Furthermore, capacity constraints on potential facilities need to be considered. We present two mixed integer programming based approaches which are solved using branch-and-cut and branch-and-cut-and-price, respectively. By studying the corresponding polyhedra we analyze both approaches theoretically and show their advantages over previously presented models. Furthermore, using a computational study we are able to additionally show significant advantages of our models over previously presented ones from a practical point of view. © 2011 Springer Science+Business Media B.V.

关键词： Branch-and-cut Branch-and-cut-and-price Connected facility location Mixed integer programming Network design

来源：评论

学校读者我要写书评

暂无评论

A sky dome visualisation for identification of astronomical orientations

A sky dome visualisation for identification of astronomical ...

引用

2005 IEEE Symposium on Information Visualization, INFO VIS 05

作者： Zotti, Georg Gröller, Meister Eduard Institute of Computer Graphics and Algorithms Vienna University of Technology

ISBN: (纸本)078039464X

It has long been known that ancient temples were frequently oriented along the cardinal directions or to certain points along the horizon where Sun or Moon rise or set on special days of the year. In the last decades, archaeologists have found evidence of even older building structures buried in the soil, with doorways that also appear to have distinct orientations. This paper presents a novel diagram combining archaeological maps with a folded-apart, flattened view of the whole sky, showing the local horizon and the daily paths of sun, moon and brighter stars. By use of this diagram, interesting groupings of astronomical orientation directions, e.g. to certain sunrise and sunset points could be identified, which were evidently used to mark certain days of the year. Orientations to a few significant stars very likely indicated the beginning of the agricultural year in the middle neolithic period. © 2005 IEEE.

关键词： Domes

来源：评论

学校读者我要写书评

暂无评论

Solving the 3-staged 2-dimensional cutting stock problem by dynamic programming and variable neighborhood search

引用

Electronic Notes in Discrete Mathematics 2015年 47卷 133-140页

作者： Dusberger, Frederico Raidl, Günther R. Institute of Computer Graphics and Algorithms Vienna University of Technology Vienna Austria

We present a variable neighborhood search (VNS) for the 3-staged 2-dimensional cutting stock problem employing "ruin-and-recreate"-based very large neighborhood search in which parts of the incumbent solution are destroyed and rebuilt using construction heuristics and dynamic programming. Experimental results show that for instances where the sizes of the elements are not too small compared to the sheet size the hybridization of VNS with dynamic programming significantly outperforms a VNS relying solely on construction heuristics. © 2014 Elsevier B.V.

关键词： Cutting stock Dynamic programming Variable neighborhood search

来源：评论

学校读者我要写书评

暂无评论

Label number maximization in the slider model

Label number maximization in the slider model

引用

12th International Symposium on Graph Drawing, GD 2004

作者： Ebner, Dietmar Klau, Gunnar W. Weiskircher, René Institute of Computer Graphics and Algorithms Vienna University of Technology

We consider the NP-hard label number maximization problem LNM: Given a set of rectangular labels, each of which belongs to a point feature in the plane, the task is to find a labeling for a largest subset of the labels. A labeling is a placement such that none of the labels overlap and each is placed so that its boundary touches the corresponding point feature. The purpose of this paper is twofold: We present a new force-based simulated annealing algorithm to heuristically solve the problem and we provide the results of a very thorough experimental comparison of the best known labeling methods on widely used benchmark sets. The design of our new method has been guided by the goal to produce labelings that are similar to the results of an experienced human performing the same task. So we are not only looking for a labeling where the number of labels placed is high but also where the distribution of the placed labels is good. Our experimental results show that the new algorithm outperforms the other methods in terms of quality while still being reasonably fast and confirm that the simulated annealing method is well-suited for map labeling problems. © Springer-Verlag Berlin Heidelberg 2004.

关键词： Problem solving

来源：评论

学校读者我要写书评

暂无评论

Boosting an exact logic-based benders decomposition approach by variable neighborhood search

引用

Electronic Notes in Discrete Mathematics 2015年 47卷 149-156页

作者： Raidl, Günther R. Baumhauer, Thomas Hu, Bin Institute of Computer Graphics and Algorithms Vienna University of Technology Vienna Austria

Logic-based Benders decomposition (BD) extends classic BD by allowing more complex subproblems with integral variables. Metaheuristics like variable neighborhood search are becoming useful here for faster solving the subproblems' inference duals in order to separate approximate Benders cuts. After performing such a purely heuristic BD approach, we continue by exactly verifying and possibly correcting each heuristic cut to finally obtain a proven optimal solution. On a bi-level vehicle routing problem, this new hybrid approach exhibits shorter overall runtimes and yields excellent intermediate solutions much earlier than the classical exact method. © 2014 Elsevier B.V.

关键词： Benders decomposition Variable neighborhood search Vehicle routing

来源：评论

学校读者我要写书评

暂无评论

Strong lower bounds for a survivable network design problem

引用

Electronic Notes in Discrete Mathematics 2010年第C期36卷 295-302页

作者： Leitner, Markus Raidl, Günther R. Institute of Computer Graphics and Algorithms Vienna University of Technology Vienna Austria

We consider a generalization of the Prize Collecting Steiner Tree Problem on a graph with special redundancy requirements on a subset of the customer nodes suitable to model a real world problem occurring in the extension of fiber optic communication networks. We strengthen an existing connection-based mixed integer programming formulation involving exponentially many variables using a recent result with respect to the orientability of two-node connected graphs. The linear programming relaxation of this model is then solved by means of column generation. We show that our new model is theoretically stronger than a previously described one and present promising preliminary computational results. © 2010 Elsevier B.V.

关键词： Column generation Mixed integer programming Survivable network design

来源：评论

学校读者我要写书评

暂无评论

Solving problems on graphs of high rank-width 14th

Solving problems on graphs of high rank-width

引用

14th International Symposium on algorithms and Data Structures, WADS 2015

作者： Eiben, Eduard Ganian, Robert Szeider, Stefan Algorithms and Complexity Group Institute of Computer Graphics and Algorithms TU Wien Vienna Austria

ISBN: (纸本)9783319218397

A modulator of a graph G to a specified graph class H is a set of vertices whose deletion puts G into H. The cardinality of a modulator to various graph classes has long been used as a structural parameter which can be exploited to obtain FPT algorithms for a range of hard problems. Here we investigate what happens when a graph contains a modulator which is large but "well-structured" (in the sense of having bounded rank-width). Can such modulators still be exploited to obtain efficient algorithms? And is it even possible to find such modulators efficiently? We first show that the parameters derived from such well-structured modulators are strictly more general than the cardinality of modulators and rank-width itself. Then, we develop an FPT algorithm for finding such well-structured modulators to any graph class which can be characterized by a finite set of forbidden induced subgraphs. We proceed by showing how well-structured modulators can be used to obtain efficient parameterized algorithms for MINIMUM VERTEX COVER and MAXIMUM CLIQUE. Finally, we use the concept of well-structured modulators to develop an algorithmic meta-theorem for efficiently deciding problems expressible in Monadic Second Order (MSO) logic, and prove that this result is tight in the sense that it cannot be generalized to LinEMSO problems. © Springer International Publishing Switzerland 2015.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

Procedural skeletons: Kinematic extensions to CGA-shape grammars 10

Procedural skeletons: Kinematic extensions to CGA-shape gram...

引用

Proceedings of the 26th Spring Conference on computer graphics

作者： Ilčík, Martin Fiedler, Stefan Purgathofer, Werner Wimmer, Michael Institute for Computer Graphics and Algorithms Vienna Technical University Austria

ISBN: (纸本)9781450305587

Procedural modeling for architectural scenes was as yet limited to static objects only. We introduce a novel extension layer for shape grammars which creates a skeletal system for posing and interactive manipulation of generated models. Various models can be derived with the same set of parametrized rules for geometric operations. Separation of geometry generation and pose synthesis improves design efficiency and reusability. Moreover, by formal analysis of production rules we show how to efficiently update complex kinematic hierarchies created by the skeletons, allowing state-of-the-art interactive visual rule editing.

关键词： Kinematics

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：