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

4th Conference on Computational Models of Argument (COMMA)

作者： Nofal, Samer Dunne, Paul Atkinson, Katie Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England

ISBN: (纸本)9781614991113;9781614991106

From theoretical computational perspectives, decision problems in Dung's abstract argumentation frameworks (AFs) are either polynomial solvable or intractable. To investigate practical efficiency, theoretical evaluation of applied algorithms does not necessarily reveal performance dissimilarities. Although experimental analysis of algorithms is a well-established alternative exploited in other domains, such methodology is given a little attention in the context of AFs. The main purpose of this paper is to give an example of how such experiments can be conducted to get meaningful conclusions about algorithms' behavior in situations where theoretical analysis might be of little help. To this end, we pick an extended model of AFs as a case study to empirically examine the efficiency of algorithms related to the acceptability of arguments.

关键词： experimental algorithms credulous acceptance skeptical acceptance

来源：评论

学校读者我要写书评

暂无评论

Temporal betweenness centrality on shortest walks variants

引用

APPLIED NETWORK SCIENCE 2025年第1期10卷 1-25页

作者： Naima, Mehdi Sorbonne Univ LIP6 CNRS F-75005 Paris France

Betweenness centrality has been extensively studied since its introduction in 1977 as a measure of node importance in graphs. This measure has found use in various applications and has been extended to temporal graphs with time-labeled edges. Recent research by Bu ss et al. and Rymar et al. has shown that it is possible to compute the shortest walks betweenness centrality of all nodes in a temporal graph in On3T2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O\left( n<^>3\,T<^>2\right)$$\end{document} and On2mT2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O\left( n<^>2\,m\,T<^>2\right)$$\end{document} time, respectively, where T is the maximum time, m is the number of temporal edges, and n is the number of nodes. These approaches considered walks that do not take into account contributions from intermediate temporal nodes. In this paper, we study the temporal betweenness centrality on classical walks that we call passive, as well as on a variant that we call active walks, which takes into account contributions from all temporal nodes. We present an improved analysis of the running time of the classical algorithm for computing betweenness centrality of all nodes, reducing the time complexity to OnmT+n2T\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O\left( n\,m\,T+ n<^>2\,T\right)$$\end{document}. Furthermore, for active walks, we show that the betweenness centrality can be computed in OnmT+n2T2\documentclass[12pt]{minimal} \u

关键词： Graph algorithms experimental algorithms Betweenness centrality Temporal graphs Shortest paths Time centrality Restless walks

来源：评论

学校读者我要写书评

暂无评论

experimental evaluation of various register-pressure-reduction heuristics

引用

SOFTWARE-PRACTICE & EXPERIENCE 2015年第11期45卷 1497-1517页

作者： Shobaki, Ghassan Sakka, Laith Abu Rmaileh, Najm Eldeen Al-Hamash, Hasan Princess Sumaya Univ Technol Amman Jordan

Minimizing the amount of spill code is still an open problem in code generation and optimization. The amount of spill code depends on both the register allocation algorithm and the pre-allocation instruction scheduling algorithm that controls the register pressure. In this paper, we focus on the impact of pre-allocation instruction scheduling on the amount of spill code. Many heuristic techniques have been proposed to do instruction scheduling with the objective of minimizing register pressure and consequently the amount of spill code. However, the performance of these heuristic techniques has not been studied relative to optimality on real large-scale programs. In this paper, we present an experimental study that evaluates the performance of several pre-allocation scheduling heuristics. The evaluation involves computing an experimental lower bound on the size of gap between each heuristic's performance and optimal performance. We also propose a simple heuristic technique based on a specific permutation of two basic priority schemes and experimentally evaluate the performance of this technique compared with other heuristics, including the heuristics implemented in the LLVM open-source Compiler. The evaluation is carried out by running SPEC CPU2006 on real x86-64 hardware and measuring both the amount of spill code and the execution time. The results of our study show that the proposed heuristic technique gives better overall performance than LLVM's best heuristic on x86-64, although it produces slightly more spilling. The proposed heuristic has better overall performance, because it achieves a better balance between register pressure and instruction-level parallelism (ILP). This result shows the importance of ILP in pre-allocation scheduling even on out-of-order machines. Furthermore, the results of the study show that there is a large gap between the performance of any of the studied heuristics and optimal performance;even the best heuristic in the study produces s

关键词： compiler optimizations instruction scheduling register pressure reduction spill code minimization performance optimization combinatorial optimization NP-complete problems experimental algorithms

来源：评论

学校读者我要写书评

暂无评论

Distance-preserving approximations of polygonal paths

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2007年第3期36卷 183-196页

作者： Gudmundsson, Joachim Narasimhan, Giri Smid, Michiel Florida Int Univ Sch Comp Sci Miami FL 33199 USA Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada

Given a polygonal path P with vertices p(1), p(2),..., p(n) is an element of R-d and a real number t >= 1, a path Q = (p(i1), p(i2),...,P-ik) is a t-distance-preserving approximation of P if 1 = i(1) < i(2) < ... < i(k) = n and each straight-line edge (p(ij), p(ij+1)) of Q approximates the distance between pi(j) and pi(j+1) along the path P within a factor of t. We present exact and approximation algorithms that compute Such a path Q that minimizes k (when given t) or t (when given k). We also present some experimental results. (c) 2006 Elsevier B.V. All rights reserved.

关键词： path simplification t-spanners well-separated pair decomposition experimental algorithms

来源：评论

学校读者我要写书评

暂无评论

Engineering Quicksort

引用

COMPUTER LANGUAGES 1996年第1期22卷 39-47页

作者： Sarwar, SM Sarwar, SA Jaragh, MHA Brandeburg, J NEW YORK INST TECHNOL ACAD COMP LABSOLD WESTBURYNY 11568 KUWAIT UNIV FAC ENGN & PETRDEPT ELECT & COMP ENGNSAFAT 13060KUWAIT

This paper describes the results of a large empirical study to measure the run-time behavior of Quicksort by using various methods of computing the pivot element for medium to large size randomly generated integer data. The results of our study contradict the common notion that Quicksort gives best performance if median of three scheme is used to compute the pivot element and array partitions having <10 elements are sorted by using insertion sort. It was found that Quicksort performs best when median of three scheme is used to decide the pivot element and arrays with <4 elements are hand sorted. Our method gives an average speedup of >9% when compared to the method with a cutoff of 10 and sub-arrays with <10 elements insertion sorted for 1000 less than or equal to N less than or equal to 1.5 x 10(6). Our study shows that advanced hardware features allow for implementation of very fast codes for sorting small arrays, and using such codes instead of insertion sort can lead to substantial improvements for Quicksort, as conjectured by Sedgewick many years ago. Copyright (C) 1996 Elsevier Science Ltd

关键词： experimental algorithms sorting algorithms Quicksort

来源：评论

学校读者我要写书评

暂无评论

Implicit Generation of Pattern-Avoiding Permutations by Using Permutation Decision Diagrams

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2014年第6期E97A卷 1171-1179页

作者： Inoue, Yuma Toda, Takahisa Minato, Shin-ichi Hokkaido Univ Grad Sch Informat Sci & Technol Sapporo Hokkaido 0600814 Japan JST ERATO MINATO Discrete Struct Manipulat Syst P Sapporo Hokkaido 0600814 Japan

Pattern-avoiding permutations are permutations where none of the subsequences matches the relative order of a given pattern. Pattern-avoiding permutations are related to practical and abstract mathematical problems and can provide simple representations for such problems. For example, some floorplans, which are used for optimizing very-large-scale integration (VLSI) circuit design, can be encoded into pattern-avoiding permutations. The generation of pattern-avoiding permutations is an important topic in efficient VLSI design and mathematical analysis of patten-avoiding permutations. In this paper, we present an algorithm for generating pattern-avoiding permutations, and extend this algorithm beyond classical patterns to generalized patterns with more restrictions. Our approach is based on the data structure pi DDs, which can represent a permutation set compactly and has useful set operations. We demonstrate the efficiency of our algorithm by computational experiments.

关键词： pattern-avoiding permutations generating algorithms decision diagrams pi DD experimental algorithms

来源：评论

学校读者我要写书评

暂无评论

Scheduling periodic messages on a shared link without buffering

引用

JOURNAL OF SCHEDULING 2024年第5期27卷 461-484页

作者： Guiraud, Mael Strozecki, Yann CESI Nanterre LINEACT BP 60293 Blvd Seine F-92006 Nanterre France Univ Versailles St Quentin DAVID Lab 45 Ave Etats Unis F-78000 Versailles France

Cloud RAN, a novel architecture for modern mobile networks, relocates processing units from antenna to distant data centers. This shift introduces the challenge of ensuring low latency for the periodic messages exchanged between antennas and their respective processing units. In this study, we tackle the problem of devising an efficient periodic message assignment scheme under the constraints of fixed message size and period without contention nor buffering. We address this problem by modeling it on a common network topology, wherein contention arises from a single shared link servicing multiple antennas. While reminiscent of coupled task scheduling, the introduction of periodicity adds a unique dimension to the problem. We study how the problem behaves with regard to the load of the shared link, and we focus on proving that, for load as high as possible, a solution always exists and it can be found in polynomial time. The main contributions of this article are two polynomial time algorithms, which find a solution for messages of any size and load at most 2/5 or for messages of size one and load at most phi-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi - 1$$\end{document}, the golden ratio conjugate. We also prove that a randomized greedy algorithm finds a solution on almost all instances with high probability, shedding light on the effectiveness of greedy algorithms in practical applications.

关键词： Periodic scheduling Greedy algorithm Randomized algorithm experimental algorithms C-RAN

来源：评论

学校读者我要写书评

暂无评论

A weak approach to suffix automata simulation for exact and approximate string matching

引用

THEORETICAL COMPUTER SCIENCE 2022年 933卷 88-103页

作者： Faro, Simone Scafiti, Stefano Univ Catania Dept Math & Comp Sci Viale A Doria 6 I-95125 Catania Italy

String matching is one of the most extensively studied problems in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, information retrieval, data compression, computational biology and chemistry. In the last few decades a myriad of alternative solutions have been proposed, based on very different techniques. However, automata have always played a very important role in the design of efficient string matching algorithms. In this paper we present the Range Automaton, a weak yet efficient variant of the non-deterministic suffix automaton of a string whose configuration can be encoded in a very simple form and which is particularly suitable to be used for solving a multitude of text-searching problems. We will firstly develop our approach in the case of exact string matching and present an efficient algorithm, named Backward Range Automaton Matcher, which turns out to be very fast in many practical cases. Later, we will show how the Range Automaton can be adapted in an effective way also to non-standard string matching problems such as swap matching and multiple string matching. experimental results suggest that our approach is flexible and effective for all three search problems addressed, especially in the case of long patterns. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Exact string matching Swap matching Text processing Automata experimental algorithms Design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

On comparing algorithms for the maximum clique problem

引用

DISCRETE APPLIED MATHEMATICS 2018年 247卷 1-13页

作者： Zuge, Alexandre Prusch Carmo, Renato UFPR Campus Avanado Jandaia do Sul BR-86900000 Jandaia Do Sul PR Brazil Univ Fed Parana Ctr Politecn UFPR Dept Informat POB 19081 BR-81531990 Curitiba Parana Brazil

Several algorithms for the exact solution of the maximum clique problem are available in the literature. Some have been proposed with the aim of bounding the worst case complexity of the problem, while others focus on practical performance as evaluated experimentally. These two groups of works are somewhat independent, in the sense that little experimental investigation is available in the former group, and little theoretical analysis exists for the latter. Moreover, the experimental results seem to be much better than could be expected from the theoretical results. We show that a broad class of branch and bound algorithms for the maximum clique problem display sub-exponential average running time behavior, and also show how this helps to explain the apparent discrepancy between the theoretical and experimental results. We also propose a more structured methodology for the experimental analysis of algorithms for the maximum clique problem, which takes into account the peculiarities of cliques in random graphs, bringing the theoretical and experimental approaches closer together in the search for better algorithms. As a proof of concept, we apply the proposed methodology to thirteen algorithms from the literature. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Maximum clique experimental algorithms Random graphs Branch and bound

来源：评论

学校读者我要写书评

暂无评论

Hybrid string matching algorithm with a pivot

引用

JOURNAL OF INFORMATION SCIENCE 2015年第1期41卷 82-88页

作者： Al-Ssulami, Abdulrakeeb M. King Saud Univ Riyadh 11543 Saudi Arabia

Pattern matching is important in text processing, molecular biology, operating systems and web search engines. Many algorithms have been developed to search for a specific pattern in a text, but the need for an efficient algorithm is an outstanding issue. In this paper, we present a simple and practical string matching algorithm. The proposed algorithm is a hybrid that combines our modification of Horspool's algorithm with two observations on string matching. The algorithm scans the text from left to right and matches the pattern from right to left. experimental results on natural language texts, genomes and human proteins demonstrate that the new algorithm is competitive with practical algorithms.

关键词： Design of algorithms experimental algorithms online string searching

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：