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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Improved characters distance sampling for online and offline text searching

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期946卷

作者： Faro, Simone Marino, Francesco Pio Pavone, Arianna Univ Catania Dept Math & Comp Sci Viale ADoria n6 I-95125 Catania Italy Univ Messina Dept Cognit Sci Via Concez n6 I-98121 Messina Italy

Sampled string matching is a very effective technique to reduce the search time for a pattern within a text at the cost of a small amount of additional memory, used for storing a partial index of the text. This approach has recently received some interest and has been applied to improve both online and offline string matching solutions, improving standard solutions by more than 50%. However, this improvement is currently only achievable in the case of texts on large-sized alphabets, and remains small (or absent) in the case of small-sized alphabets. In this article we propose an extension of the approach to text-sampling, known as Character Distance Sampling, to the case of small alphabets, obtaining an improvement of up to 98% compared to standard solutions in the case of online string matching. We also extend this approach to the case of offline string matching, introducing a sampled version of the suffix array, obtaining performances up to 5 times higher than the search obtained on the standard suffix array. Differently from what has been done by previous solutions, our idea is not based on the reduction of the number of indexed suffixes, but on the construction of the index directly on the sampled text. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Text processing experimental algorithms String matching

来源：评论

学校读者我要写书评

暂无评论

New Instances for Maximum Weight Independent Set From a Vehicle Routing Application

引用

Operations Research Forum 2021年第4期2卷 48页

作者： Dong, Yuanyuan Goldberg, Andrew V. Noe, Alexander Parotsidis, Nikos Resende, Mauricio G. C. Spaen, Quico Dallas TX United States *** East Palo Alto CA United States University of Vienna Vienna Austria Department of Computer Science University of Copenhagen Copenhagen Denmark *** and Industrial & Systems Engineering University of Washington Seattle WA United States

We present a set of new instances of the maximum weight independent set problem. These instances are derived from a real-world vehicle routing problem and are challenging to solve in part because of their large size. ... 详细信息

关键词： experimental algorithms Maximum weight independent set Problem instances

来源：评论

学校读者我要写书评

暂无评论

The order-preserving pattern matching problem in practice

引用

DISCRETE APPLIED MATHEMATICS 2020年 274卷 11-25页

作者： Cantone, Domenico Faro, Simone Kulekci, M. Oguzhan Univ Catania Dipartimento Matemat & Informat Catania Italy Istanbul Tech Univ Informat Inst Istanbul Turkey

Given a pattern x of length m and a text y of length n, both over a totally ordered alphabet, the order-preserving pattern matching (OPPM) problem consists in finding all substrings of the text with the same relative order as the pattern. The OPPM problem, which might be viewed as an approximate variant of the well-known exact pattern matching problem, has gained attention in recent years. This interesting problem finds applications in such diverse fields as time series analysis (as share prices on stock markets or weather data analysis) and musical melody matching, just to mention a few. In this paper we present two new filtering approaches which turn out to be much more effective in practice than the previously presented methods, reducing the number of false positives up to 99%. We also present a new efficient approach inspired by the well-known Skip Search algorithm for the exact string matching problem. It makes use of efficient SIMD SSE instructions for speeding up the searching phase. experimental results show that our proposed algorithms are up to twice faster than previous solutions. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Approximate text analysis experimental algorithms Filtering algorithms Text processing

来源：评论

学校读者我要写书评

暂无评论

Flexible and Efficient algorithms for Abelian Matching in Genome Sequence 7th

Flexible and Efficient Algorithms for Abelian Matching in Ge...

引用

7th International Work-Conference on Bioinformatics and Biomedical Engineering (IWBBIO)

作者： Faro, Simone Pavone, Arianna Univ Catania Dipartimento Matemat & Informat Viale Andrea Doria 6 I-95125 Catania Italy Univ Messina Dipartimento Sci Cognit Via Concez 6 I-98122 Messina Italy

ISBN: (纸本)9783030179380;9783030179373

Approximate matching in strings is a fundamental and challenging problem in computer science and in computational biology, and increasingly fast algorithms are highly demanded in many applications including text processing and dna sequence analysis. Recently efficient solutions to specific approximate matching problems on genomic sequences have been designed using a filtering technique, based on the general abelian matching problem, which firstly locates the set of all candidate matching positions and then perform an additional verification test on the collected positions. The abelian pattern matching problem consists in finding all substrings of a text which are permutations of a given pattern. In this paper we present a new class of algorithms based on a new efficient fingerprint computation approach, called Heap-Counting, which turns out to be fast, flexible and easy to be implemented. We prove that, when applied for searching short patterns on a dna sequence, our solutions have a linear worst case time complexity. In addition we present an experimental evaluation which shows that our newly presented algorithms are among the most efficient and flexible solutions in practice for the abelian matching problem in dna sequences.

关键词： Approximate string matching Abelian matching jumbled matching experimental algorithms

来源：评论

学校读者我要写书评

暂无评论

Towards experimental algorithms for Abstract Argumentation

Towards Experimental Algorithms for Abstract Argumentation

引用

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Minimum spanning tree under explorable uncertainty in theory and experiments 16

Minimum spanning tree under explorable uncertainty in theory...

引用

16th Symposium on experimental algorithms, SEA 2017

作者： Focke, Jacob Megow, Nicole Meifiner, Julie Department of Computer Science University of Oxford Oxford United Kingdom Department of Mathematics and Computer Science University of Bremen Bremen Germany Institute of Mathematics Technical University of Berlin Berlin Germany

ISBN: (纸本)9783959770361

We consider the minimum spanning tree (MST) problem in an uncertainty model where uncertain edge weights can be explored at extra cost. The task is to find an MST by querying a minimum number of edges for their exact weight. This problem has received quite some attention from the algorithms theory community. In this paper, we conduct the first practical experiments for MST under uncertainty, theoretically compare three known algorithms, and compare theoretical with practical behavior of the algorithms. Among others, we observe that the average performance and the absolute number of queries are both far from the theoretical worst-case bounds. Furthermore, we investigate a known general preprocessing procedure and develop an implementation thereof that maximally reduces the data uncertainty. We also characterize a class of instances that is solved completely by our preprocessing. Our experiments are based on practical data from an application in telecommunications and uncertainty instances generated from the standard TSPLib graph library. © Jacob Focke, Nicole Megow, and Julie Meifiner.

关键词： Competitive ratio experimental algorithms Explorable uncertainty MST

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：