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

algorithmICA 2011年第1期60卷 60-94页

作者： Delling, Daniel Univ Karlsruhe TH D-76128 Karlsruhe Germany

In recent years, many speed-up techniques for Dijkstra's algorithm have been developed that make the computation of shortest paths in static road networks a matter of microseconds. However, only few of those techniques work in time-dependent networks which, unfortunately, appear quite frequently in reality: Roads are predictably congested by traffic jams, and efficient timetable information systems rely on time-dependent networks. Hence, a fast technique for routing in such networks is needed. In this work, we present an efficient time-dependent route planning algorithm. It is based on our recently introduced SHARC algorithm, which we adapt by augmenting its basic ingredients such that correctness can still be guaranteed in a time-dependent scenario. As a result, we are able to efficiently compute exact shortest paths in time-dependent continental-sized transportation networks, both of roads and of railways. It should be noted that time-dependent SHARC was the first efficient algorithm for time-dependent route planning.

关键词： algorithm engineering Graph algorithms Time-dependent shortest paths Timetable information

来源：评论

学校读者我要写书评

暂无评论

engineering Parallel Sorting for the Intel SCC

引用

Procedia Computer Science 2012年 9卷 1890-1899页

作者： Nicolas Melot Christoph Kessler Kenan Avdic Patrick Cichowski Jörg Keller Department Computer and Information Science (IDA) Linköping University Sweden Fac. Mathematics and Computer Science FernUniversit¬at in Hagen Germany

The Single-Chip Cloud Computer (SCC) is an experimental processor created by Intel Labs. It comprises 48 Intel-x86 cores linked by an on-chip high performance mesh network, as well as four DDR3 memory controllers to access an off-chip main memory. We investigate the adaptation of sorting onto SCC as an algorithm engineering problem. We argue that a combination of pipelined mergesort and sample sort will fit best to SCC's architecture. We also provide a mapping based on integer linear programming to address load balancing and latency considerations. We describe a prototype implementation of our proposal together with preliminary runtime measurements, that indicate the usefulness of this approach. As mergesort can be considered as a representative of the class of streaming applications, the techniques developed here should also apply to the other problems in this class, such as many applications for parallel embedded systems, i.e. MPSoC.

关键词： Parallel sorting algorithm engineering on-chip pipelining streaming applications

来源：评论

学校读者我要写书评

暂无评论

engineering a Combinatorial Laplacian Solver: Lessons Learned

引用

algorithmS 2016年第4期9卷 72-72页

作者： Hoske, Daniel Lukarski, Dimitar Meyerhenke, Henning Wegner, Michael KIT Inst Theoret Informat Fasanengarten 5 D-76131 Karlsruhe Germany Google Inc 1600 Amphitheatre Pkwy Mountain View CA 94043 USA Paralut Labs UG & Co KG D-76571 Gaggenau Germany

Linear system solving is a main workhorse in applied mathematics. Recently, theoretical computer scientists contributed sophisticated algorithms for solving linear systems with symmetric diagonally-dominant (SDD) matrices in provably nearly-linear time. These algorithms are very interesting from a theoretical perspective, but their practical performance was unclear. Here, we address this gap. We provide the first implementation of the combinatorial solver by Kelner et al. (STOC 2013), which is appealing for implementation due to its conceptual simplicity. The algorithm exploits that a Laplacian matrix (which is SDD) corresponds to a graph;solving symmetric Laplacian linear systems amounts to finding an electrical flow in this graph with the help of cycles induced by a spanning tree with the low-stretch property. The results of our experiments are ambivalent. While they confirm the predicted nearly-linear running time, the constant factors make the solver much slower for reasonable inputs than basic methods with higher asymptotic complexity. We were also not able to use the solver effectively as a smoother or preconditioner. Moreover, while spanning trees with lower stretch indeed reduce the solver's running time, we experience again a discrepancy in practice: in our experiments, simple spanning tree algorithms perform better than those with a guaranteed low stretch. We expect that our results provide insights for future improvements of combinatorial linear solvers.

关键词： Laplacian linear systems graph algorithms low-stretch spanning trees electrical graph flows algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Evaluation of a Flow-Based Hypergraph Bipartitioning algorithm 27

Evaluation of a Flow-Based Hypergraph Bipartitioning Algorit...

引用

27th Annual European Symposium on algorithms (ESA)

作者： Gottesbueren, Lars Hamann, Michael Wagner, Dorothea Karlsruhe Inst Technol Inst Theoret Informat Karlsruhe Germany

ISBN: (纸本)9783959771245

In this paper, we propose HyperFlowCutter, an algorithm for balanced hypergraph bipartitioning that is based on minimum S-T hyperedge cuts and maximum flows. It computes a sequence of bipartitions that optimize cut size and balance in the Pareto sense, being able to trade one for the other. HyperFlowCutter builds on the FlowCutter algorithm for partitioning graphs. We propose additional features, such as handling disconnected hypergraphs, novel methods for obtaining starting S, T pairs as well as an approach to refine a given partition with HyperFlowCutter. Our main contribution is ReBaHFC, a new algorithm which obtains an initial partition with the fast multilevel hypergraph partitioner PaToH and then improves it using HyperFlowCutter as a refinement algorithm. ReBaHFC is able to significantly improve the solution quality of PaToH at little additional running time. The solution quality is only marginally worse than that of the best-performing hypergraph partitioners KaHyPar and hMETIS, while being one order of magnitude faster. Thus ReBaHFC offers a new time-quality trade-off in the current spectrum of hypergraph partitioners. For the special case of perfectly balanced bipartitioning, only the much slower plain HyperFlowCutter yields slightly better solutions than ReBaHFC, while only PaToH is faster than ReBaHFC.

关键词： Hypergraph Partitioning Maximum Flows algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Efficient Routing in Road Networks with Turn Costs

引用

10th International Symposium on Experimental algorithms

作者： Geisberger, Robert Vetter, Christian Karlsruhe Inst Technol D-76128 Karlsruhe Germany

ISBN: (纸本)9783642206610

We present an efficient algorithm for shortest path computation in road networks with turn costs. Each junction is modeled as a node, and each road segment as an edge in a weighted graph. Turn costs are stored in tables that are assigned to nodes. By reusing turn cost tables for identical junctions, we improve the space efficiency. Preprocessing based on an augmented node contraction allows fast shortest path queries. Compared to an edge-based graph, we reduce preprocessing time by a factor of 3.4 and space by a factor of 2.4 without change in query time.

关键词： route planning banned turn turn cost algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Graph Spanners in the Streaming Model: An Experimental Study

Graph Spanners in the Streaming Model: An Experimental Study

引用

15th Annual European Symposium on algorithms (ESA 2007)

作者： Ausiello, Giorgio Demetrescu, Camil Franciosa, Paolo G. Italiano, Giuseppe F. Ribichini, Andrea Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00185 Rome Italy Univ Roma La Sapienza Dipartimento Stat Probabilita & Stat Applicate I-00185 Rome Italy

This article reports the results of an extensive experimental analysis of efficient algorithms for computing graph spanners in the data streaming model, where an (alpha, beta)-spanner of a graph G is a subgraph S subset of G such that for each pair of vertices the distance in S is at most a times the distance in G plus beta. To the best of our knowledge, this is the first computational study of graph spanner algorithms in a streaming setting. We compare experimentally the randomized algorithms proposed by Baswana (http://***/abstract?id=oai:***:cs/0611023) and by Elkin (In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), Wroclaw, Poland, pp. 716-727, 9-13 July 2007) for general stretch factors with the deterministic algorithm presented by Ausiello et al. (In: Proceedings of the 15th Annual European Symposium on algorithms (ESA 2007), engineering and Applications Track, Eilat, Israel, 8-10 October 2007. LNCS, vol. 4698, pp. 605-617, 2007), designed for building small stretch spanners. All the algorithms we implemented work in a data streaming model where the input graph is given as a stream of edges in arbitrary order, and all of them need a single pass over the data. Differently from the algorithm in Ausiello et al., the algorithms in Baswana (http://***/abstract?id=oai:***:cs/0611023) and Elkin (In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), Wroclaw, Poland, pp. 716-727, 9-13 July 2007) need to know in advance the number of vertices in the graph. The results of our experimental investigation on several input families confirm that all these algorithms are very efficient in practice, finding spanners with stretch and size much smaller than the theoretical bounds and comparable to those obtainable by off-line algorithms. Moreover, our experimental findings confirm that small values of the stretch factor are the case of

关键词： Graph algorithms Graph spanners Data streams Experimental algorithmics algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Exploring the Potential of JuLeS: A White Box Framework for Local Search Metaheuristics

Exploring the Potential of JuLeS: A White Box Framework for ...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Da Ros, Francesca Di Gaspero, Luca Univ Udine DMIF Intelligent Optimizat Lab Udine Italy Univ Udine DPIA Intelligent Optimizat Lab Udine Italy

ISBN: (纸本)9798400701207

The JuLeS framework (short for Julia Local Search)(1) is a versatile and highly customizable platform for quickly creating Local Search solvers. Developed using the Julia programming language, JuLeS enables efficient implementation of solvers, facilitates the development of new meta-heuristic algorithms, and easily integrates with existing tools. The overhead of the framework with respect to existing C++ frameworks is moderate, but it benefits from a lower programming effort and integrability into the Julia ecosystem. The design, architecture, and features of JuLeS are explained and its effectiveness is demonstrated through three use cases that highlight its design achievements.

关键词： Software tools algorithm engineering Local search Metaheuristics

来源：评论

学校读者我要写书评

暂无评论

Nested Monte Carlo Search Expression Discovery for the Automated Design of Fuzzy ART Category Choice Functions 19

Nested Monte Carlo Search Expression Discovery for the Autom...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Illetskova, Marketa Elnabarawy, Islam Brito da Silva, Leonardo Enzo Tauritz, Daniel R. Wunsch, Donald C., II Missouri Univ Sci & Technol Rolla MO 65409 USA Minist Educ Brazil CAPES Fdn Brasilia DF Brazil

ISBN: (纸本)9781450367486

While the performance of many neural network and machine learning schemes has been improved through the automated design of various components of their architectures, the automated improvement of Adaptive Resonance Theory (ART) neural networks remains relatively unexplored. Recent work introduced a genetic programming (GP) approach to improve the performance of the Fuzzy ART neural network employing a hyper-heuristic approach to tailor Fuzzy ART's category choice function to specific problems. The GP method showed promising results. However, GP is not the only tool that can be used for automatic improvement. Among other methods, Nested Monte Carlo Search (NMCS) was recently applied to expression discovery and outperformed traditional evolutionary approaches by finding better solutions in fewer evaluations. This work applies NMCS to the discovery of new Fuzzy ART category choice functions targeted to specific problems with results demonstrating its ability to find better performing Fuzzy ART networks than the GP approach.

关键词： genetic programming neural networks metaheuristics algorithm engineering empirical study

来源：评论

学校读者我要写书评

暂无评论

Dynamic Public Transit Labeling 19th

Dynamic Public Transit Labeling

引用

19th International Conference on Computational Science and Its Applications (ICCSA)

作者： D'Emidio, Mattia Khan, Imran Univ Aquila Dept Informat Engn Comp Sci & Math Laquila Italy Gran Sasso Sci Inst GSSI Laquila Italy

ISBN: (纸本)9783030242893

We study the journey planning problem in transit networks which, given the timetable of a schedule-based transit system, asks to answer to queries such as, e.g., "seek a journey that arrives at a given destination as early as possible". The state-of-the-art solution to such problem, in terms of query time, is Public Transit Labeling (PTL), proposed in [Delling et al., SEA 2015], that consists of three main ingredients: (i) a graph data structure for storing transit networks;(ii) a compact labeling-based representation of the transitive closure of such graph, computed via a time-consuming preprocessing routine;(iii) an efficient query algorithm exploiting both graph and precomputed data to answer quickly to queries of interest at runtime. The major drawback of PTL is not being practical in dynamic scenarios, when the network's timetable can undergo updates (e.g. delays). In fact, even after a single change, precomputed data become outdated and queries can return incorrect results. Recomputing the labeling-based representation from scratch, after a modification, is not a viable option as it yields unsustainable time overheads. Since transit networks are inherently dynamic, the above represents a major limitation of PTL. In this paper, we overcome such limit by introducing a dynamic algorithm, called D-PTL, able to update the preprocessed data whenever a delay affects the network, without recomputing it from scratch. We demonstrate the effectiveness of D-PTL through a rigorous experimental evaluation showing that its update times are orders of magnitude smaller than the time for recomputing the preprocessed data from scratch.

关键词： Journey planning Dynamic graph algorithms 2-Hop-Cover labeling algorithm engineering Massive datasets Networks

来源：评论

学校读者我要写书评

暂无评论

Fast and Simple Approach for Polygon Schematization 1

引用

12th International Conference on Computational Science and Its Applications (ICCSA)

作者： Cicerone, Serafino Cermignani, Matteo Univ Aquila Dept Elect & Informat Engn I-67100 Laquila Italy

ISBN: (数字)9783642311253

ISBN: (纸本)9783642311246;9783642311253

The schematization of simple polygons into octilinear polygons is a computational problem arising in the context of electronic CAD systems. In particular, it appears when the generation and propagation of electromagnetic noise into real-world multi-layer PCBs has to be detected. In this paper we provide a fast and simple heuristic for solving such a problem. Experimental evaluations over real-world data show the efficiency and the good performance of the proposed approach.

关键词： Computational geometry polygon schematization CAD applications algorithm engineering experimental analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：