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

Note on generalization in experimental algorithmics

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2000年第4期26卷 568-580页

作者： Ramakrishnan, N Valdés-Pérez, RE Virginia Polytech Inst & State Univ Dept Comp Sci Blacksburg VA 24061 USA Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA

A recurring theme in mathematical software evaluation is the generalization of rankings of algorithms on test problems to build knowledge-based recommender systems for algorithm selection. A key issue is to profile algorithms in terms of the qualitative characteristics of benchmark problems. In this methodological note, we adapt a novel all-pairs algorithm for the profiling task;given performance rankings for m algorithms on n problem instances, each described with p features, identify a (minimal) subset of p that is useful for assessing the selective superiority of an algorithm over another, for all pairs of m algorithms. We show how techniques presented in the mathematical software literature are inadequate for such profiling purposes. In conclusion, we also address various statistical issues underlying the effective application of this technique.

关键词： algorithms performance profiling performance evaluation benchmark studies experimental algorithmics

来源：评论

学校读者我要写书评

暂无评论

How experimental algorithmics can benefit from Mayo's extensions to Neyman-Pearson theory of testing

引用

SYNTHESE 2008年第3期163卷 385-396页

作者： Bartz-Beielstein, Thomas Cologne Univ Appl Sci Fac Comp Sci & Engn Sci D-51643 Gummersbach Germany

Although theoretical results for several algorithms in many application domains were presented during the last decades, not all algorithms can be analyzed fully theoretically. Experimentation is necessary. The analysis of algorithms should follow the same principles and standards of other empirical sciences. This article focuses on stochastic search algorithms, such as evolutionary algorithms or particle swarm optimization. Stochastic search algorithms tackle hard real-world optimization problems, e.g., problems from chemical engineering, airfoil optimization, or bio-informatics, where classical methods from mathematical optimization fail. Nowadays statistical tools that are able to cope with problems like small sample sizes, non-normal distributions, noisy results, etc. are developed for the analysis of algorithms. Although there are adequate tools to discuss the statistical significance of experimental data, statistical significance is not scientifically meaningful per se. It is necessary to bridge the gap between the statistical significance of an experimental result and its scientific meaning. We will propose some ideas on how to accomplish this task based on Mayo's learning model (NPT*).

关键词： new experimentalism experimental algorithmics optimization theory of testing Mayo's learning model significance

来源：评论

学校读者我要写书评

暂无评论

Guidelines for experimental algorithmics: A Case Study in Network Analysis

引用

ALGORITHMS 2019年第7期12卷 127-127页

作者： Angriman, Eugenio van der Grinten, Alexander von Looz, Moritz Meyerhenke, Henning Noellenburg, Martin Predari, Maria Tzovas, Charilaos Humboldt Univ Dept Comp Sci D-10099 Berlin Germany TU Wien Inst Log & Computat Algorithms & Complex Grp A-1040 Vienna Austria

The field of network science is a highly interdisciplinary area;for the empirical analysis of network data, it draws algorithmic methodologies from several research fields. Hence, research procedures and descriptions of the technical results often differ, sometimes widely. In this paper we focus on methodologies for the experimental part of algorithm engineering for network analysis-an important ingredient for a research area with empirical focus. More precisely, we unify and adapt existing recommendations from different fields and propose universal guidelines-including statistical analyses-for the systematic evaluation of network analysis algorithms. This way, the behavior of newly proposed algorithms can be properly assessed and comparisons to existing solutions become meaningful. Moreover, as the main technical contribution, we provide SimexPal, a highly automated tool to perform and analyze experiments following our guidelines. To illustrate the merits of SimexPal and our guidelines, we apply them in a case study: we design, perform, visualize and evaluate experiments of a recent algorithm for approximating betweenness centrality, an important problem in network analysis. In summary, both our guidelines and SimexPal shall modernize and complement previous efforts in experimental algorithmics;they are not only useful for network analysis, but also in related contexts.

关键词： experimental algorithmics network analysis applied graph algorithms statistical analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

On Mining Dynamic Graphs for k Shortest Paths 16th

On Mining Dynamic Graphs for k Shortest Paths

引用

16th International Conference on Social Networks Analysis and Mining

作者： D'Ascenzo, Andrea D'Emidio, Mattia Luiss Univ Rome Italy Univ Aquila Laquila Italy

ISBN: (纸本)9783031785405;9783031785412

Mining graphs, upon query, for k shortest paths between vertex pairs is a prominent primitive to support several analytics tasks on complex networked datasets. The state-of-the-art method to implement this primitive is KPLL, a framework that provides very fast query answering, even for large inputs and volumes of queries, by pre-computing and exploiting an appropriate index of the graph. However, if the graph's topology undergoes changes over time, such index might become obsolete and thus yield incorrect query results. Re-building the index from scratch, upon every modification, induces unsustainable time overheads, incompatible with applications using k shortest paths for analytics purposes. Motivated by this limitation, in this paper, we introduce DECKPLL, the first dynamic algorithm to maintain a KPLL index under decremental modifications. We assess the effectiveness and scalability of our algorithm through extensive experimentation and show it updates KPLL indices orders of magnitude faster than the re-computation from scratch, while preserving its compactness and query performance. We also combine DECKPLL with INCKPLL, the only known dynamic algorithm to maintain a KPLL index under incremental modifications, and hence showcase, on real-world datasets, the first method to support fast extraction of k shortest paths from graphs that evolve by arbitrary topological changes.

关键词： Graph Algorithms Dynamic Networks Algorithm Engineering experimental algorithmics

来源：评论

学校读者我要写书评

暂无评论

Graph Spanners in the Streaming Model: An experimental Study

引用

ALGORITHMICA 2009年第2期55卷 346-374页

作者： 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

来源：评论

学校读者我要写书评

暂无评论

An experimental evaluation of refinement techniques for the subgraph isomorphism backtracking algorithms

引用

OPEN COMPUTER SCIENCE 2020年第1期11卷 33-42页

作者： Mihelic, Jurij Cibej, Uros Univ Ljubljana Fac Comp & Informat Sci Vecna Pot 113 Ljubljana 1000 Slovenia

In this paper, we study a well-known computationally hard problem, called the subgraph isomorphism problem where the goal is for a given pattern and target graphs to determine whether the pattern is a sub graph of the target graph. Numerous algorithms for solving the problem exist in the literature and most of them are based on the backtracking approach. Since straightforward backtracking is usually slow, many algorithmic refinement techniques are used in practical algorithms. The main goal of this paper is to study such refinement techniques and to determine their ability to speed up backtracking algorithms. To do this we use a methodology of experimental algorithmics. We perform an experimental evaluation of the techniques and their combinations and, hence, demonstrate their usefulness in practice.

关键词： graph subgraph isomorphism backtracking algorithm experimental algorithmics SEARCH GRAPHS

来源：评论

学校读者我要写书评

暂无评论

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)

关键词： Graph algorithms Graph spanners Data streams experimental algorithmics Algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

A unified framework to experiment with algorithm optimality and efficiency

引用

COMPUTER APPLICATIONS IN ENGINEERING EDUCATION 2021年第6期29卷 1793-1810页

作者： Angel Velazquez-Iturbide, J. Rey Juan Carlos Univ Higher Tech Sch Comp Engn C Tulipan S-N Madrid 28933 Spain

It is common in algorithm courses to assess the correctness of algorithms via testing as well as conducting experiments to measure their run-time performance. However, two severe problems must be addressed: both activities are conducted using different procedures and tools, and algorithm assessment systems do not support well optimization problems due to their unique characteristics. Given the relevant role of optimization algorithms in computing, we present a unified framework to support experimentation with both criteria, that is, optimality and efficiency. The contributions of the article are twofold. First, we present a unified framework to experiment with both criteria, by using explicit principles and by presenting its instantiation in the AlgorEx system. The homogeneous treatment of optimality and time efficiency contributes to smoother integration of experimentation into a course syllabus and to easier adoption of the system. Second, we present our experience in several academic years in an algorithm course. Initially, it was noticed that students had severe difficulties dealing with experimentation, but their academic performance sharply increased by fully integrating experimentation along the complete course. The article also identifies some opportunities for extension in AlgorEx.

关键词： educational assessment experimental algorithmics optimality optimization algorithms software tool time efficiency

来源：评论

学校读者我要写书评

暂无评论

The Price of Resiliency: a Case Study on Sorting with Memory Faults

引用

ALGORITHMICA 2009年第4期53卷 597-620页

作者： Ferraro-Petrillo, Umberto Finocchi, Irene Italiano, Giuseppe F. Univ Roma La Sapienza Dipartimento Stat Probabilita & Stat Applicate I-00185 Rome Italy Univ Roma La Sapienza Dipartimento Informat I-00198 Rome Italy Univ Roma Tor Vergata Dipartimento Informat Sistemi & Prod I-00133 Rome Italy

We address the problem of sorting in the presence of faults that may arbitrarily corrupt memory locations, and investigate the impact of memory faults both on the correctness and on the running times of mergesort-based algorithms. To achieve this goal, we develop a software testbed that simulates different fault injection strategies, and perform a thorough experimental study using a combination of several fault parameters. Our experiments give evidence that simple-minded approaches to this problem are largely impractical, while the design of more sophisticated resilient algorithms seems really worth the effort. Another contribution of our computational study is a carefully engineered implementation of a resilient sorting algorithm, which appears robust to different memory fault patterns.

关键词： Sorting Memory faults Memory models Fault injection Computing with unreliable information experimental algorithmics

来源：评论

学校读者我要写书评

暂无评论

Restart strategies for GRASP with path-relinking heuristics

引用

OPTIMIZATION LETTERS 2011年第3期5卷 467-478页

作者： Resende, Mauricio G. C. Ribeiro, Celso C. AT&T Labs Res Florham Pk NJ 07932 USA Univ Fed Fluminense BR-24210240 Niteroi RJ Brazil

GRASP with path-relinking is a hybrid metaheuristic, or stochastic local search (Monte Carlo) method, for combinatorial optimization. A restart strategy in GRASP with path-relinking heuristics is a set of iterations {i (1), i (2), aEuro broken vertical bar} on which the heuristic is restarted from scratch using a new seed for the random number generator. Restart strategies have been shown to speed up stochastic local search algorithms. In this paper, we propose a new restart strategy for GRASP with path-relinking heuristics. We illustrate the speedup obtained with our restart strategy on GRASP with path-relinking heuristics for the maximum cut problem, the maximum weighted satisfiability problem, and the private virtual circuit routing problem.

关键词： GRASP Path-relinking Restart strategy experimental algorithmics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：