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

A software engineering perspective on algorithmics

ACM COMPUTING SURVEYS 2001年第1期33卷 89-134页

作者： Weihe, K Forschungsinst Diskrete Math D-53113 Bonn Germany

An algorithm component is an implementation of an algorithm which is not intended to be a stand-alone module, but to perform a specific task within a large software package or even within several distinct software packages. Therefore, the design of algorithm components must also incorporate software-engineering aspects. A key design goal is adaptability. This goal is important for maintenance throughout a project, prototypical development, and reuse in new, unforeseen contexts. From a theoretical viewpoint most algorithms apply to a range of possible use scenarios. Ideally, each algorithm is implemented by one algorithm component, which is easily, safely, and efficiently adaptable to all of these contexts. Various techniques have been developed for the design and implementation of algorithm components. However, a common basis for systematic, detailed evaluations and comparisons in view of the real practical needs is still missing. Basically, this means a set of concrete criteria, which specify what sort of adaptability is really required in practice, and which are well-justified by convincing, representative use scenarios. This paper is intended to be a first "milestone" on the way towards such a system of criteria. We will present a set of concrete goals, which are general and problem-independent and might appear ubiquitously in the algorithmic realm. These goals are illustrated, motivated, and justified by an extensive requirements analysis for a particular algorithm from a particular algorithmic domain: Dijkstra's algorithm for shortest paths in networks. Clearly, the field of algorithmics might be too versatile to allow a comprehensive, yet concise set of precise, justified criteria. Even a domain as restricted as graph and network algorithms includes aspects that are not fully understood. The analysis will include a discussion of the limits of the case study and the scope of the goals. The case study was chosen because it seems to be close to the "borderline" b

关键词： algorithms design languages algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Reactive and dynamic local search for max-clique: engineering effective building blocks

引用

COMPUTERS & OPERATIONS RESEARCH 2010年第3期37卷 534-542页

作者： Battiti, Roberto Mascia, Franco Univ Trent Dipartimento Ingn & Sci Informaz I-38100 Trento Italy

This paper presents the results of an ongoing investigation about how different algorithmic building blocks contribute to solving the maximum clique problem. We consider greedy constructions, plateau searches, and more complex schemes based on dynamic penalties and/or prohibitions, in particular the recently proposed technique of dynamic local search and the previously proposed reactive local search (RLS). We design a variation of the original RLS algorithm where the role of long-term memory (LTM) is increased (RLS-LTM). In addition, we consider in detail the effect of the low-level implementation choices on the CPU time per iteration. We present experimental results on randomly generated graphs with different statistical properties, showing the crucial effects of the implementation, the robustness of different techniques, and their empirical scalability. (C) 2009 Elsevier Ltd. All rights reserved.

关键词： Hybrid metaheuristics Reactive local search Dynamic local search Stochastic local search algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

engineering efficient paging algorithms

引用

ACM Journal of Experimental algorithmics 2014年第2期19卷 1-19页

作者： Moruz, Gabriel Negoescu, Andrei Neumann, Christian Weichert, Volker Department of Computer Science Goethe University Frankfurt Am Main Robert-Mayer-Str. 11-15 Frankfurt am Main 60325 Germany

In the field of online algorithms, paging is a well-studied problem. LRU is a simple paging algorithm that incurs few cache misses and supports efficient implementations. algorithms outperforming LRU in terms of cache misses exist but are in general more complex and thus not automatically better, since their increased runtime might annihilate the gains in cache misses. In this article, we focus on efficient implementations for the ONOPT class described inMoruz and Negoescu [2012], particularly on an algorithm in this class, denoted RDM, that was shown to typically incur fewer misses than LRU. We provide experimental evidence on a wide range of cache traces showing that our implementation of RDM is competitive to LRU with respect to runtime. In a scenario incurring realistic time penalties for cache misses, we show that our implementation consistently outperforms LRU, even if the runtime of LRU is set to zero. © 2014 ACM.

关键词： algorithm engineering Paging

来源：评论

学校读者我要写书评

暂无评论

engineering a PTAS for Minimum Feedback Vertex Set in Planar Graphs 1

引用

Conference on Analysis of Experimental algorithms (SEA2)

作者： Borradaile, Glencora Le, Hung Zheng, Baigong Oregon State Univ Corvallis OR 97331 USA

ISBN: (数字)9783030340292

ISBN: (纸本)9783030340292;9783030340285

We investigate the practicality of approximation schemes for optimization problems in planar graphs based on balanced separators. The first polynomial-time approximation schemes (PTASes) for problems in planar graphs were based on balanced separators, wherein graphs are recursively decomposed into small enough pieces in which optimal solutions can be found by brute force or other methods. However, this technique was supplanted by the more modern and (theoretically) more efficient approach of decomposing a planar graph into graphs of bounded treewidth, in which optimal solutions are found by dynamic programming. While the latter approach has been tested experimentally, the former approach has not. To test the separator-based method, we examine the minimum feed-back vertex set (FVS) problem in planar graphs. We propose a new, simple O(n log n)-time approximation scheme for FVS using balanced separators and a linear kernel. The linear kernel reduces the size of the graph to be linear in the size of the optimal solution. In doing so, we correct a reduction rule in Bonamy and Kowalik's linear kernel [11] for FVS. We implemented this PTAS and evaluated its performance on large synthetic and real-world planar graphs. Unlike earlier planar PTAS engineering results [8,36], our implementation guarantees the theoretical error bounds on all tested graphs.

关键词： Feedback vertex set Planar graph algorithms Approximation schemes algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

engineering a Textbook Approach to Index Massive String Dictionaries 1

引用

30th International Symposium on String Processing and Information Retrieval (SPIRE) / 18th Workshop on Compression, Text, and algorithms (WCTA)

作者： Ferragina, Paolo Rotundo, Mariagiovanna Vinciguerra, Giorgio Univ Pisa Dept Comp Sci Pisa Italy

ISBN: (数字)9783031439803

ISBN: (纸本)9783031439797;9783031439803

We study the problem of engineering space-time efficient indexes that support membership and lexicographic (rank) queries on very large static dictionaries of strings. Our solution is based on a very simple approach that consists of decoupling string storage and string indexing by means of a blockwise compression of the sorted dictionary strings (to be stored in external memory) and a succinct implementation of a Patricia trie (to be stored in internal memory) built on the first string of each block. Our experimental evaluation on two new datasets, which are at least one order of magnitude larger than the ones used in the literature, shows that (i) the state-of-the-art compressed string dictionaries (such as FST, PDT, CoCo-trie) do not provide significant benefits if used in an indexing setting compared to Patricia tries, and (ii) our two-level approach enables the indexing of 3.5 billion strings taking 273 GB in less than 200 MB of internal memory, which is available on any commodity machine, while still guaranteeing comparable or faster query performance than those offered by array-based solutions used in modern storage systems, such as RocksDB, thus possibly influencing their future designs.

关键词： String dictionary problem Trie data structure String compression algorithm engineering Key-value store

来源：评论

学校读者我要写书评

暂无评论

engineering efficient error-correcting geocoding 11

Engineering efficient error-correcting geocoding

引用

19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2011

作者： Jung, Christian Karch, Daniel Knopp, Sebastian Luxen, Dennis Sanders, Peter PTV AG Stumpfstraße 1 76131 Karlsruhe Germany TU Berlin Straße des 17. Juni 135 10623 Berlin Germany Karlsruhe Institute of Technology Kaiserstraße 12 76131 Karlsruhe Germany

We study the problem of resolving a perhaps misspelled address of a location into geographic coordinates of latitude and longitude. Our solution does not require any prefixed rule set and is able to recover even heavi... 详细信息

ISBN: (纸本)9781450310314

关键词： data structures algorithm engineering geocoding approximate string indexing

来源：评论

学校读者我要写书评

暂无评论

Modeling and engineering algorithms for mobile data

Modeling and engineering algorithms for mobile data

引用

12th International Symposium on Spatial Data Handling, SDH 2006

作者： Blunck, Henrik Hinrichs, Klaus H. Sondern, Joëlle Vahrenhold, Jan Institut für Informatik Westfälische Wilhelms-Universität Münster 48149 Muenster Germany

ISBN: (纸本)354035588X

In this paper, we present an object-oriented approach to modeling mobile data and algorithms operating on such data. Our model is general enough to capture any kind of continuous motion while at the same time allowing for encompassing algorithms optimized for specific types of motion. Such motion may be available in a specific form, e.g., described by polynomials or splines, or implicitly restricted using bounds for speed or acceleration given by the application context. © 2006 Springer-Verlag Berlin Heidelberg.

关键词： algorithm engineering Object-oriented modeling Spatio-temporal data

来源：评论

学校读者我要写书评

暂无评论

Fast local search for the maximum independent set problem

引用

JOURNAL OF HEURISTICS 2012年第4期18卷 525-547页

作者： Andrade, Diogo V. Resende, Mauricio G. C. Werneck, Renato F. AT&T Labs Res Florham Pk NJ 07932 USA Google Inc New York NY 10011 USA Microsoft Res Silicon Valley Mountain View CA 94043 USA

Given a graph G=(V,E), the independent set problem is that of finding a maximum-cardinality subset S of V such that no two vertices in S are adjacent. We introduce two fast local search routines for this problem. The first can determine in linear time whether a maximal solution can be improved by replacing a single vertex with two others. The second routine can determine in O(m Delta) time (where Delta is the highest degree in the graph) whether there are two solution vertices than can be replaced by a set of three. We also present a more elaborate heuristic that successfully applies local search to find near-optimum solutions to a wide variety of instances. We test our algorithms on instances from the literature as well as on new ones proposed in this paper.

关键词： Maximum independent set Local search Iterated local search algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Fixed-parameter algorithms for DAG Partitioning

引用

DISCRETE APPLIED MATHEMATICS 2017年 220卷 134-160页

作者： van Bevern, Rene Bredereck, Robert Chopin, Morgan Hartung, Sepp Hueffner, Falk Nichterlein, Andre Suchy, Ondfej Novosibirsk State Univ Novosibirsk Russia TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Univ Ulm Inst Optimierung & Operat Res D-89069 Ulm Germany Czech Tech Univ Fac Informat Technol Prague Czech Republic

Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al. (2009) as DAG PARTITIONING: given an arc-weighted directed acyclic graph on n vertices and m arcs, delete arcs with total weight at most k such that each resulting weakly-connected component contains exactly one sink-a vertex without outgoing arcs. DAG PARTITIONING iS NP-hard. We show an algorithm to solve DAG PARTITIONING in O(2(k) . (n m)) time, that is, in linear time for fixed k. We complement it with linear-time executable data reduction rules. Our experiments show that, in combination, they can optimally solve DAG PARTITIONING CM simulated citation networks within five minutes for k <= 190 and m being 10(7) and larger. We use our obtained optimal solutions to evaluate the solution quality of Leskovec et al.'s heuristic. We show that Leskovec et al.'s heuristic works optimally on trees and generalize this result by showing that DAG PARTITIONING is solvable in 2(0(t2)) " n time if a width-t tree decomposition of the input graph is given. Thus, we improve an algorithm and answer an open question of Alamdari and Mehrabian (2012). We complement our algorithms by lower bounds on the running time of exact algorithms and on the effectivity of data reduction. (C) 2016 Elsevier B.V. All rights reserved.

关键词： NP-hard problem Graph algorithms Polynomial-time data reduction Multiway cut Linear-time algorithms algorithm engineering Evaluating heuristics

来源：评论

学校读者我要写书评

暂无评论

Isolation concepts for clique enumeration: Comparison and computational experiments

引用

THEORETICAL COMPUTER SCIENCE 2009年第52期410卷 5384-5397页

作者： Hueffner, Falk Komusiewicz, Christian Moser, Hannes Niedermeier, Rolf Univ Jena Inst Informat D-07743 Jena Germany Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

We do Computational studies concerning the enumeration of isolated cliques in graphs. Isolation, as recently introduced, measures the degree of connectedness of the cliques to the rest of the graph. Isolation helps both in getting faster algorithms for the enumeration of maximal general cliques and in filtering out cliques with special semantics. We compare three isolation concepts and their combination with two enumeration modi for maximal cliques ("isolated maximal" vs "maximal isolated"). All studied concepts exhibit the fixed-parameter tractability of the enumeration task with respect to the parameter "degree of isolation". We provide a first systematic experimental study of the corresponding enumeration algorithms, using synthetic graphs (in the G(n,m,p) model), financial networks, and a music artist similarity network, proposing the enumeration of isolated cliques as a useful instrument in analyzing financial and social networks. (C) 2009 Elsevier B.V. All rights reserved.

关键词： NP-hard problem Fixed-parameter tractability Exact algorithm algorithm engineering Dense subgraph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：