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

STXXL: standard template library for XXL data sets

SOFTWARE-PRACTICE & EXPERIENCE 2008年第6期38卷 589-637页

作者： Dementiev, R. Kettner, L. Sanders, P. Univ Karlsruhe Fak Informat Karlsruhe Germany Max Planck Inst Informat Saarbrucken Germany

We present the software library STXXL that is an implementation of the C++ standard template library (STL) for processing huge data sets that can fit only on hard disks. It supports parallel disks, overlapping between disk I/O and computation and it is the first I/O-efficient algorithm library that supports the pipelining technique that can save more than half of the I/Os. STXXL has been applied both in academic and industrial environments for a range of problems including text processing, graph algorithms, computational geometry, Gaussian elimination, visualization, and analysis of microscopic images, differential cryptographic analysis, etc. The performance of STXXL and its applications are evaluated on synthetic and real-world inputs. We present the design of the library, how its performance features are supported, and demonstrate how the library integrates with STL. Copyright (c) 2007 John Wiley & Sons, Ltd.

关键词： very large data sets software library C plus plus standard template library algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Drawing database schemas

引用

SOFTWARE-PRACTICE & EXPERIENCE 2002年第11期32卷 1065-1098页

作者： Di Battista, G Didimo, W Patrignani, M Pizzonia, M Univ Roma Tre Dipartimento Informat & Automazione I-00146 Rome Italy Univ Perugia Dipartimento Ingn Elett & Informazione I-06125 Perugia Italy

A wide number of practical applications would benefit from automatically generated graphical representations of database schemas. in which tables are represented by boxes, and table attributes correspond to distinct stripes inside each table. Links, connecting attributes of two different tables, represent referential constraints or join relationships, and may attach arbitrarily to the left- or to the right-hand side of the stripes representing the attributes. To our knowledge no drawing technique is available to automatically produce diagrams in such a strongly constrained drawing convention. In this paper we provide a polynomial time algorithm for solving this problem, and test its efficiency and effectiveness against a large test suite. Also, we describe an implementation of a system that uses such an algorithm and we study the main methodological problems we faced in developing such a technology. Copyright (C) 2002 John Wiley Sons, Ltd.

关键词： graph drawing algorithm engineering drawing standard orthogonal drawing database schema visualization upward drawing

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for side-chain placement in protein design

引用

OPTIMIZATION LETTERS 2011年第3期5卷 393-406页

作者： Canzar, Stefan Toussaint, Nora C. Klau, Gunnar W. CWI Life Sci Grp NL-1098 XG Amsterdam Netherlands Univ Tubingen Ctr Bioinformat D-72076 Tubingen Germany

Computational protein design aims at constructing novel or improved functions on the structure of a given protein backbone and has important applications in the pharmaceutical and biotechnical industry. The underlying combinatorial side-chain placement (SCP) problem consists of choosing a SCP for each residue position such that the resulting overall energy is minimum. The choice of the side-chain then also determines the amino acid for this position. Many algorithms for this NP-hard problem have been proposed in the context of homology modeling, which, however, reach their limits when faced with large protein design instances. In this paper, we propose a new exact method for the SCP problem that works well even for large instance sizes as they appear in protein design. Our main contribution is a dedicated branch-and-bound algorithm that combines tight upper and lower bounds resulting from a novel Lagrangian relaxation approach for SCP. Our experimental results show that our method outperforms alternative state-of-the-art exact approaches and makes it possible to optimally solve large protein design instances routinely.

关键词： Lagrangian relaxation Branch-and-bound algorithm engineering Protein design side-chain placement

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms for Cluster Editing: Evaluation and Experiments

引用

algorithmICA 2011年第2期60卷 316-334页

作者： Boecker, Sebastian Briesemeister, Sebastian Klau, Gunnar W. Univ Jena Inst Informat Jena Germany Jena Ctr Bioinformat Jena Germany Univ Tubingen Div Simulat Biol Syst ZBIT WSI Tubingen Germany CWI NL-1090 GB Amsterdam Netherlands

The Cluster Editing problem is defined as follows: Given an undirected, loopless graph, we want to find a set of edge modifications (insertions and deletions) of minimum cardinality, such that the modified graph consists of disjoint cliques. We present empirical results for this problem using exact methods from fixed-parameter algorithmics and linear programming. We investigate parameter-independent data reduction methods and find that effective preprocessing is possible if the number of edge modifications k is smaller than some multiple of vertical bar V vertical bar , where V is the vertex set of the input graph. In particular, combining parameter-dependent data reduction with lower and upper bounds we can effectively reduce graphs satisfying k <= 25 vertical bar V vertical bar In addition to the fastest known fixed-parameter branching strategy for the problem, we investigate an integer linear program (ILP) formulation of the problem using a cutting plane approach. Our results indicate that both approaches are capable of solving large graphs with 1000 vertices and several thousand edge modifications. For the first time, complex and very large graphs such as biological instances allow for an exact solution, using a combination of the above techniques. (A preliminary version of this paper appeared under the title "Exact algorithms for cluster editing: Evaluation and experiments" in the Proceedings of the 7th Workshop on Experimental algorithms, WEA 2008, in: LNCS, vol. 5038, Springer, pp. 289-302.).

关键词： Cluster editing algorithm engineering Computer experiments NP-complete problem Fixed-parameter tractability FPT Integer linear programming ILP Branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Energy-Optimal Routes for Battery Electric Vehicles

引用

algorithmICA 2020年第5期82卷 1490-1546页

作者： Baum, Moritz Dibbelt, Julian Pajor, Thomas Sauer, Jonas Wagner, Dorothea Zundorf, Tobias Karlsruhe Inst Technol Karlsruhe Germany

We study the problem of computing paths that minimize energy consumption of a battery electric vehicle. For that, we must cope with specific properties, such as regenerative braking and constraints imposed by the battery capacity. These restrictions can be captured by profiles, which are a functional representation of optimal energy consumption between two locations, subject to initial state of charge. Efficient computation of profiles is a relevant problem on its own, but also a fundamental ingredient to many route planning approaches for battery electric vehicles. In this work, we prove that profiles have linear complexity. We examine different variants of Dijkstra's algorithm to compute energy-optimal paths or profiles. Further, we derive a polynomial-time algorithm for the problem of finding an energy-optimal path between two locations that allows stops at charging stations. We also discuss a heuristic variant that is easy to implement, and carefully integrate it with the well-known Contraction Hierarchies algorithm and A* search. Finally, we propose a practical approach that enables computation of energy-optimal routes within milliseconds after fast (metric-dependent) preprocessing of the whole network. This enables flexible updates due to, e. g., weather forecasts or refinements of the consumption model. Practicality of our approaches is demonstrated in a comprehensive experimental study on realistic, large-scale road networks.

关键词： algorithm engineering Shortest paths Speedup techniques Electric vehicles Profile search

来源：评论

学校读者我要写书评

暂无评论

A lattice-based representation of independence relations for efficient closure computation

引用

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING 2020年 126卷 272-289页

作者： van der Gaag, Linda C. Baioletti, Marco Bolt, Janneke H. Dalle Molle Inst Artificial Intelligence Res Lugano Switzerland Univ Utrecht Dept Informat & Comp Sci Utrecht Netherlands Univ Perugia Dipartimento Matemat & Informat Perugia Italy

Independence relations in general include exponentially many statements of independence, that is, exponential in the number of variables involved. These relations are typically characterised however, by a small set of such statements and an associated set of derivation rules. While various computational problems on independence relations can be solved by manipulating these smaller sets without the need to explicitly generate the full relation, existing algorithms for constructing these sets are associated with often prohibitively high running times. In this paper, we introduce a lattice structure for organising sets of independence statements and show that current algorithms are rendered computationally less demanding by exploiting new insights in the structural properties of independence gained from this lattice organisation. By means of a range of experimental results, we subsequently demonstrate that through the lattice organisation indeed a substantial gain in efficiency is achieved for fast-closure computation of semi-graphoid independence relations in practice. (C) 2020 Published by Elsevier Inc.

关键词： Independence relations Representation Lattice-based partitioning Fast-closure computation algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

An experimental analysis of simple, distributed vertex coloring algorithms

引用

algorithmICA 2005年第1期41卷 1-23页

作者： Finocchi, I Panconesi, A Silvestri, R Univ Roma Tor Vergata Dept Comp Sci Syst & Prod I-00133 Rome Italy Univ Roma La Sapienza Dept Comp Sci I-00198 Rome Italy

We perform an extensive experimental evaluation of very simple, distributed, randomized algorithms for(Delta+1) and so-called Brooks-Vizing vertex colorings, i.e., colorings using considerably fewer than Delta Colors (here Delta denotes the maximum degree of the graph). We consider variants of algorithms known from the literature, boosting them with a distributed independent set computation. Our study clearly determines the relative performance of the algorithms with respect to the number of communication rounds and the number of colors. The results are confirmed by all the experiments and instance families. The empirical evidence shows that some algorithms use very few rounds and are rather effective, thus being amenable to be used in practice.

关键词： distributed graph algorithms vertex coloring algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Enumeration of 2-level polytopes

引用

MATHEMATICAL PROGRAMMING COMPUTATION 2019年第1期11卷 173-210页

作者： Bohn, Adam Faenza, Yuri Fiorini, Samuel Fisikopoulos, Vissarion Macchia, Marco Pashkovich, Kanstantsin Univ Libre Bruxelles Brussels Belgium Columbia Univ LEOR Dept New York NY USA Univ Waterloo C&O Dept Waterloo ON Canada

A (convex) polytope P is said to be 2-level if for each hyperplane H that supports a facet of P, the vertices of P can be covered with H and exactly one other translate of H. The study of these polytopes is motivated by questions in combinatorial optimization and communication complexity, among others. In this paper, we present the first algorithm for enumerating all combinatorial types of 2-level polytopes of a given dimension d, and provide complete experimental results for d <= 7. Our approach is inductive: for each fixed (d - 1)-dimensional 2-level polytope P-0, we enumerate all d-dimensional 2-level polytopes P that have P-0 as a facet. This relies on the enumeration of the closed sets of a closure operator over a finite ground set. By varying the prescribed facet P-0, we obtain all 2-level polytopes in dimension d.

关键词： Polyhedral computation Polyhedral combinatorics Optimization Formal concept analysis algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Multiline Addressing by Network Flow

引用

algorithmICA 2009年第4期53卷 583-596页

作者： Eisenbrand, Friedrich Karrenbauer, Andreas Skutella, Martin Xu, Chihao Ecole Polytech Fed Lausanne CH-1015 Lausanne Switzerland Max Planck Inst Informat D-66123 Saarbrucken Germany Tech Univ Berlin Inst Math D-10623 Berlin Germany Univ Saarland Lehrstuhl Mikroelekt Saarbrucken Germany

We consider an optimization problem arising in the design of controllers for OLED displays. Our objective is to minimize amplitude of the electrical current through the diodes which has a direct impact on the lifetime of such a display. Modeling the problem in mathematical terms yields a class of network flow problems where we group the arcs and pay in each group only for the arc carrying the maximum flow. We develop (fully) combinatorial approximation heuristics suitable for being implemented in the hardware of a control device that drives an OLED display.

关键词： Combinatorial optimization Network design OLED algorithm engineering Matrix decomposition

来源：评论

学校读者我要写书评

暂无评论

Shortest Feasible Paths with Charging Stops or Battery Electric Vehicles

引用

TRANSPORTATION SCIENCE 2019年第6期53卷 1627-1655页

作者： Baum, Moritz Dibbelt, Julian Gemsa, Andreas Wagner, Dorothea Zuendorf, Tobias KIT D-76131 Karlsruhe Germany

We study the problem of minimizing overall trip time for battery electric vehicles in road networks. As battery capacity is limited, stops at charging stations may be inevitable. Careful route planning is crucial because charging stations are scarce and recharging is timeconsuming. We extend the constrained shortest-path problem for electric vehicles with realistic models of charging stops, including varying charging power and battery-swapping stations. Although the resulting problem is theoretically hard, we propose a combination of algorithmic techniques to achieve good performance in practice. Extensive experimental evaluation shows that our approach (CHArge) enables computation of optimal solutions on realistic inputs even of continental scale. Finally, we investigate heuristic variants of CHArge that derive high-quality routes in well below a second on sensible instances.

关键词： route planning road networks speedup techniques algorithm engineering shortest paths electric vehicles energy consumption charging stations

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：