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

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

来源：评论

学校读者我要写书评

暂无评论

Customization strategies for the solution of linear programming problems arising from large scale model predictive control of a paper machine

引用

JOURNAL OF PROCESS CONTROL 1999年第5期9卷 385-396页

作者： Dave, P Doyle, FJ Pekny, JF Univ Delaware Dept Chem Engn Newark DE 19716 USA Purdue Univ Sch Chem Engn W Lafayette IN 47907 USA

This paper presents an application of a customized linear programming (LP) based model predictive control strategy to the paper machine cross direction (CD) control problem. The objective of CD control is to maintain flat profiles of variables of interest by minimizing worst case deviations from setpoints (defects). These control problems can have as many as 200 actuators (inputs) and 400 sensor measurements (outputs). This large size coupled with the stringent real-time requirement of computing a control move in a few seconds poses a very challenging control problem. Computational results that demonstrate the effectiveness of this strategy will be presented. For typical disturbances this algorithm can compute provably optimal control moves for a 400 input x 400 output control problem in approximately 5 s versus approximately 90 s for a generic LP algorithm on a HP 9000/770 workstation. (C) 1999 Elsevier Science Ltd. All rights reserved.

关键词： model predictive control paper machine control large scale systems linear programming algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

An effective hybrid algorithm for university course timetabling

引用

JOURNAL OF SCHEDULING 2006年第5期9卷 403-432页

作者： Chiarandini, Marco Birattari, Mauro Socha, Krzysztof Rossi-Doria, Olivia Univ So Denmark Dept Math & Comp Sci DK-5230 Odense M Denmark Univ Libre Bruxelles IRIDIA B-1050 Brussels Belgium Napier Univ Sch Comp Edinburgh EH10 5DT Midlothian Scotland

The university course timetabling problem is an optimisation problem in which a set of events has to be scheduled in timeslots and located in suitable rooms. Recently, a set of benchmark instances was introduced and used for an 'International Timetabling Competition' to which 24 algorithms were submitted by various research groups active in the field of timetabling. We describe and analyse a hybrid metaheuristic algorithm which was developed under the very same rules and deadlines imposed by the competition and outperformed the official winner. It combines various construction heuristics, tabu search, variable neighbourhood descent and simulated annealing. Due to the complexity of developing hybrid metaheuristics, we strongly relied on an experimental methodology for configuring the algorithms as well as for choosing proper parameter settings. In particular, we used racing procedures that allow an automatic or semi-automatic configuration of algorithms with a good save in time. Our successful example shows that the systematic design of hybrid algorithms through an experimental methodology leads to high performing algorithms for hard combinatorial optimisation problems.

关键词： university course timetabling local search methods metaheuristics hybrid algorithms experimental methodology algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Improved online algorithms for jumbled matching

引用

DISCRETE APPLIED MATHEMATICS 2020年 274卷 54-66页

作者： Ghuman, Sukhpal Singh Tarhio, Jorma Chhabra, Tamanna Sheridan Coll Fac Appl Sci & Technol 7899 McLaughlin Rd Brampton ON L6Y 5H9 Canada Aalto Univ Dept Comp Sci POB 15400 FI-00076 Aalto Finland Seneca Coll 70 Pond Rd Toronto ON M3J 3M6 Canada

We consider the problem of jumbled matching where the objective is to find all permuted occurrences of a pattern in a text. Besides exact matching we study approximate matching where each occurrence is allowed to contain at most k wrong or superfluous characters. We present online algorithms applying bit-parallelism to both types of jumbled matching. Two of our algorithms are filtration methods applying SIMD (Single Instruction Multiple Data) computation. Most of the other new algorithms are variations of earlier methods. We show by practical experiments that our algorithms are competitive with previous solutions. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Jumbled matching Abelian matching Approximate string matching SIMD computation Comparison of algorithms algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

A fast algorithm for the all-pairs suffix-prefix problem

引用

THEORETICAL COMPUTER SCIENCE 2017年 698卷 14-24页

作者： Lim, Jihyuk Park, Kunsoo Seoul Natl Univ Dept Comp Sci & Engn Seoul 08826 South Korea

The all-pairs suffix-prefix problem occurs as a subproblem of DNA sequence assembly where it is the most time-consuming part of the whole assembly. Although there are algorithms for the all-pairs suffix-prefix problem which are optimal in the asymptotic time complexity, they are slower than SOF and Readjoiner which are state-of-the-art algorithms used in practice. In this paper we present an algorithm for the all-pairs suffix-prefix problem that uses a simple data structure for storing input strings and advanced algorithmic techniques for matching, which together lead to fast running time in practice. Our algorithm is 14 times faster than SOF and 18 times faster than Readjoiner on average in real datasets and random datasets. (C) 2017 Elsevier B.V. All rights reserved.

关键词： All-pairs suffix-prefix problem algorithm engineering DNA sequence assembly

来源：评论

学校读者我要写书评

暂无评论

A hybrid algorithm for the unbounded knapsack problem

引用

DISCRETE OPTIMIZATION 2009年第1期6卷 110-124页

作者： Poirriez, Vincent Yanev, Nicola Andonov, Rumen INRIA Rennes Bretagne Atlantique F-35042 Rennes France Univ Valenciennes LAMIH ROI CNRSUMR 8530 F-59313 Valenciennes 9 France Univ Sofia Fac Math & Informat Sofia 1164 Bulgaria Bulgarian Acad Sci Inst Math & Informat BU-1113 Sofia Bulgaria

This paper presents a new approach for exactly solving the Unbounded Knapsack Problem (UKP) and proposes a new bound that was proved to dominate the previous bounds on a special class of UKP instances. Integrating bounds within the framework of sparse dynamic programming led to the creation of an efficient and robust hybrid algorithm, called EDUK2. This algorithm takes advantage of the majority of the known properties of UKP, particularly the diverse dominance relations and the important periodicity property. Extensive computational results show that, in all but a very few cases, EDUK2 significantly outperforms both MTU2 and EDUK, the currently available UKP solvers, as well the well-known general purpose mathematical programming optimizer CPLEX of ILOG. These experimental results demonstrate that the class of hard UKP instances needs to be redefined, and the authors offer their insights into the creation of such instances. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Integer programming Knapsack problem Branch and bound Dynamic programming algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

High-Efficiency Microsatellite-Using Super-Resolution algorithm Based on the Multi-Modality Super-CMOS Sensor

引用

SENSORS 2020年第14期20卷 4019.-4019页

作者： Zhang, Ke Yang, Cankun Li, Xiaojuan Zhou, Chunping Zhong, Ruofei Capital Normal Univ Key Lab 3D Informat Acquisit & Applicat MOE Beijing 100048 Peoples R China Capital Normal Univ Engn Res Ctr Spatial Informat Technol MOE Beijing 100048 Peoples R China Inst Remote Sensing Beijing 100011 Peoples R China

To realize the application of super-resolution technology from theory to practice, and to improve microsatellite spatial resolution, we propose a special super-resolution algorithm based on the multi-modality super-CMOS sensor which can adapt to the limited operation capacity of microsatellite computers. First, we designed an oblique sampling mode with the sensor rotated at an angle of26.56 degrees(arctan1/2)to obtain high overlap ratio images with sub-pixel displacement. Secondly, the proposed super-resolution algorithm was applied to reconstruct the final high-resolution image. Because the satellite equipped with this sensor is scheduled to be launched this year, we also designed the simulation mode of conventional sampling and the oblique sampling of the sensor to obtain the comparison and experimental data. Lastly, we evaluated the super-resolution quality of images, the effectiveness, the practicality, and the efficiency of the algorithm. The results of the experiments showed that the satellite-using super-resolution algorithm combined with multi-modality super-CMOS sensor oblique-mode sampling can increase the spatial resolution of an image by about 2 times. The algorithm is simple and highly efficient, and can realize the super-resolution reconstruction of two remote-sensing images within 0.713 s, which has good performance on the microsatellite.

关键词： multi-modality rotatable sensor microsatellite spatial resolution oblique sampling mode super-resolution algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Real-time Avionics Optimization

引用

IT-INFORMATION TECHNOLOGY 2011年第6期53卷 274-279页

作者： Eisenbrand, Friedrich Niemeier, Martin Skutella, Martin Verschae, Jose Wiese, Andreas Ecole Polytechn Federale Lausanne Stn 8 CH-1015 Lausanne Switzerland Tech Univ Berlin Inst Math D-10623 Berlin Germany

We report on the solution of a difficult optimization problem which arises in avionics industry. When constructing the on-board controlling-network of an airplane, the engineers need to solve a computationally highly complex problem. The goal is to assign periodic tasks to the processors on the plane and define a schedule for each processor. Current state-of-the-art approaches to tackle the problem are by far not powerful enough to solve instances of real-world size. With the help of the powerful algorithm engineering paradigm we analyzed the mathematical properties of the scheduling problem and designed sophisticated software based on the structural insights. We were able to design a model that outperformed current state-of-the-art approaches by several orders of magnitude. In particular, we could solve industrial size real-world instances to optimality. Our methods lead, for the first time, to an industrial strength tool to schedule aircraft sized instances.

关键词： F[Theory of Computation] G[Mathematics of Computing] J[Computer Applications] real-time scheduling algorithm engineering avionics on-board computer integer programming IP-model mathematical modelling

来源：评论

学校读者我要写书评

暂无评论

Minimum Partition into Plane Subgraphs: The CG:SHOP Challenge 2022

引用

ACM Journal of Experimental algorithmics 2023年第3期28卷 1-13页

作者： Fekete, Sándor P. Keldenich, Phillip Krupke, Dominik Schirra, Stefan Department of Computer Science TU Braunschweig Mühlenpfordtstr. 23 Braunschweig38106 Germany Department for Simulation and Graphics OVGU Magdeburg Universitätsplatz 2 Magdeburg39106 Germany

We give an overview of the 2022 Computational Geometry Challenge targeting the problem Minimum Partition into Plane Subsets, which consists of partitioning a given set of line segments into a minimum number of non-cro... 详细信息

关键词： Computational geometry geometric optimization algorithm engineering graph coloring plane subgraphs intersection graphs CG:SHOP

来源：评论

学校读者我要写书评

暂无评论

A review of data fusion models and systems

引用

INTERNATIONAL JOURNAL OF IMAGE AND DATA FUSION 2012年第1期3卷 3-21页

作者： Sidek, Othman Quadri, S. A. Univ Sains Malaysia Collaborat Microelect Design Excellence Ctr Engn Campus George Town 14300 Malaysia

Implementation of a data fusion system is a complex task. Several of the most critical issues related to the implementation are requirements analysis, sensor selection, architecture selection, algorithm selection, software implementation and testing and evaluation. A number of data fusion frameworks have been developed to serve the purpose. This article reviews the literature on data fusion models, as well as aspects of systems engineering related to multisensory fusion. A novel generic framework is proposed to link data fusion system engineering with algorithm engineering paradigm. A new term called 'impact factor' is introduced to designate data fusion performance research findings.

关键词： data fusion framework algorithm engineering performance evaluation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：