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

Energy-Optimal Routes for Battery Electric Vehicles

algorithmICA 2020年第5期82卷 1490-1546页

作者： Baum, Moritz Dibbelt, Julian Pajor, Thomas Sauer, Jonas Wagner, Dorothea Zundorf, Tobias Karlsruhe Inst Technol Karlsruhe Germany

We study the problem of computing paths that minimize energy consumption of a battery electric vehicle. For that, we must cope with specific properties, such as regenerative braking and constraints imposed by the battery capacity. These restrictions can be captured by profiles, which are a functional representation of optimal energy consumption between two locations, subject to initial state of charge. Efficient computation of profiles is a relevant problem on its own, but also a fundamental ingredient to many route planning approaches for battery electric vehicles. In this work, we prove that profiles have linear complexity. We examine different variants of Dijkstra's algorithm to compute energy-optimal paths or profiles. Further, we derive a polynomial-time algorithm for the problem of finding an energy-optimal path between two locations that allows stops at charging stations. We also discuss a heuristic variant that is easy to implement, and carefully integrate it with the well-known Contraction Hierarchies algorithm and A* search. Finally, we propose a practical approach that enables computation of energy-optimal routes within milliseconds after fast (metric-dependent) preprocessing of the whole network. This enables flexible updates due to, e. g., weather forecasts or refinements of the consumption model. Practicality of our approaches is demonstrated in a comprehensive experimental study on realistic, large-scale road networks.

关键词： algorithm engineering Shortest paths Speedup techniques Electric vehicles Profile search

来源：评论

学校读者我要写书评

暂无评论

Parallel computation of combinatorial symmetries 29

Parallel computation of combinatorial symmetries

引用

29th Annual European Symposium on algorithms, ESA 2021

作者： Anders, Markus Schweitzer, Pascal TU Darmstadt Germany

ISBN: (纸本)9783959772044

In practice symmetries of combinatorial structures are computed by transforming the structure into an annotated graph whose automorphisms correspond exactly to the desired symmetries. An automorphism solver is then employed to compute the automorphism group of the constructed graph. Such solvers have been developed for over 50 years, and highly efficient sequential, single core tools are available. However no competitive parallel tools are available for the task. We introduce a new parallel randomized algorithm that is based on a modification of the individualization-refinement paradigm used by sequential solvers. The use of randomization crucially enables parallelization. We report extensive benchmark results that show that our solver is competitive to state-of-the-art solvers on a single thread, while scaling remarkably well with the use of more threads. This results in order-of-magnitude improvements on many graph classes over state-of-the-art solvers. In fact, our tool is the first parallel graph automorphism tool that outperforms current sequential tools. © Markus Anders and Pascal Schweitzer;licensed under Creative Commons License CC-BY 4.0

关键词： algorithm engineering Automorphism groups Graph isomorphism Parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On the effectiveness of the genetic paradigm for polygonization

引用

INFORMATION PROCESSING LETTERS 2021年 171卷 106134-106134页

作者： Cicerone, Serafino D'Emidio, Mattia Di Stefano, Gabriele Navarra, Alfredo Univ Aquila Dipartimento Ingn & Sci Informaz & Matemat Laquila Italy Univ Perugia Dipartimento Matemat & Informat Perugia Italy

A polygon is simple if it is a closed chain of straight line segments that do not self-intersect. Given a finite set P of input points in the Euclidean plane, the search for a simple polygon with vertex set P is a very well-known and studied computational problem, referred to as the simple polygonization. Its optimization version, that requires to find a simple polygon having either minimum or maximum area, is known to be NP-hard. Moreover, no bounded approximation algorithm is known for the minimization flavor, while the maximization one admits an algorithm guaranteeing 1/2 worst-case approximation ratio. In this work, we design a new algorithm to practically attack both the optimization problems, based on the genetic paradigm. We demonstrate its effectiveness through an extensive experimental evaluation that employs a reference test-bed set of input instances. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Polygonization Approximation algorithms Genetic optimization Computational geometry algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

algorithmic Aspects of Temporal Betweenness 20

Algorithmic Aspects of Temporal Betweenness

引用

26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)

作者： Buss, Sebastian Molter, Hendrik Niedermeier, Rolf Rymar, Maciej TU Berlin Algorithm & Computat Complex Berlin Germany

ISBN: (纸本)9781450379984

The betweenness centrality of a graph vertex measures how often this vertex is visited on shortest paths between other vertices of the graph. In the analysis of many real-world graphs or networks, betweenness centrality of a vertex is used as an indicator for its relative importance in the network. In recent years, a growing number of real-world networks is modeled as temporal graphs instead of conventional (static) graphs. In a temporal graph, we have a fixed set of vertices and there is a finite discrete set of time steps and every edge might be present only at some time steps. While shortest paths are straightforward to define in static graphs, temporal paths can be considered "optimal" with respect to many different criteria, including length, arrival time, and overall travel time (shortest, foremost, and fastest paths). This leads to different concepts of temporal betweenness centrality, posing new challenges on the algorithmic side. We provide a systematic study of temporal betweenness variants based on various concepts of optimal temporal paths both on a theoretical and empirical level.

关键词： Network Science Network Centrality Temporal Graphs Temporal Paths Counting Complexity algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Enumeration of 2-level polytopes

引用

MATHEMATICAL PROGRAMMING COMPUTATION 2019年第1期11卷 173-210页

作者： Bohn, Adam Faenza, Yuri Fiorini, Samuel Fisikopoulos, Vissarion Macchia, Marco Pashkovich, Kanstantsin Univ Libre Bruxelles Brussels Belgium Columbia Univ LEOR Dept New York NY USA Univ Waterloo C&O Dept Waterloo ON Canada

A (convex) polytope P is said to be 2-level if for each hyperplane H that supports a facet of P, the vertices of P can be covered with H and exactly one other translate of H. The study of these polytopes is motivated by questions in combinatorial optimization and communication complexity, among others. In this paper, we present the first algorithm for enumerating all combinatorial types of 2-level polytopes of a given dimension d, and provide complete experimental results for d <= 7. Our approach is inductive: for each fixed (d - 1)-dimensional 2-level polytope P-0, we enumerate all d-dimensional 2-level polytopes P that have P-0 as a facet. This relies on the enumeration of the closed sets of a closure operator over a finite ground set. By varying the prescribed facet P-0, we obtain all 2-level polytopes in dimension d.

关键词： Polyhedral computation Polyhedral combinatorics Optimization Formal concept analysis algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Shortest Feasible Paths with Charging Stops or Battery Electric Vehicles

引用

TRANSPORTATION SCIENCE 2019年第6期53卷 1627-1655页

作者： Baum, Moritz Dibbelt, Julian Gemsa, Andreas Wagner, Dorothea Zuendorf, Tobias KIT D-76131 Karlsruhe Germany

We study the problem of minimizing overall trip time for battery electric vehicles in road networks. As battery capacity is limited, stops at charging stations may be inevitable. Careful route planning is crucial because charging stations are scarce and recharging is timeconsuming. We extend the constrained shortest-path problem for electric vehicles with realistic models of charging stops, including varying charging power and battery-swapping stations. Although the resulting problem is theoretically hard, we propose a combination of algorithmic techniques to achieve good performance in practice. Extensive experimental evaluation shows that our approach (CHArge) enables computation of optimal solutions on realistic inputs even of continental scale. Finally, we investigate heuristic variants of CHArge that derive high-quality routes in well below a second on sensible instances.

关键词： route planning road networks speedup techniques algorithm engineering shortest paths electric vehicles energy consumption charging stations

来源：评论

学校读者我要写书评

暂无评论

High-Multiplicity Fair Allocation Made More Practical 21

High-Multiplicity Fair Allocation Made More Practical

引用

International Conference on Autonomous Agents and Multiagent Systems

作者： Robert Bredereck Aleksander Figiel Andrzej Kaczmarczyk Dusan Knop Rolf Niedermeier Humboldt-Universitat zu Berlin TU Berlin Czech Technical University in Prague

ISBN: (纸本)9781713832621

The envy-free, Pareto-efficient allocation of indivisible goods leads to computationally hard problems. There is a big variety of modeling issues, such as agent-specific utility functions or (high numbers of) different types of goods. In recent work, Bredereck et al. [ACM EC 2019] addressed this topic by showing (theoretical) fixed-parameter tractability results for "high-multiplicity fair allocation", exploiting parameters such as number of agents or maximum absolute utility values. To this end, they used a number of tools from (theoretical) integer linear programming. We "engineer" their work towards practical usefulness, thereby being able to solve all real-world instances from the state-of-art online platform "*** for provably fair solutions". Besides providing the foundations for a fast tool for fair allocations, we also offer a flexible framework with the possibility to relax fairness or efficiency demands so to, e.g., allow tradeoffs between fairness and social welfare. Moreover, our framework provides ways to interpret and explain "solution paths" which makes it possible to perform further explorations in cases when no envy-free and efficient allocations exist.

关键词： Indivisible goods Flexible fairness Integer linear programming algorithm engineering Interpretable and explainable allocations Integer linear programming cargo allocation elastic frame Utility functions tradeoffs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：