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

17th RCRA 2010 Workshop on Experimental Evaluation of algorithms for Solving Problems with Combinatorial Explosion

作者： Sinz, Carsten Iser, Markus Research Group Verification Meets Algorithm Engineering Institute for Theoretical Computer Science University of Karlsruhe Germany

Search restarts have shown great potential in speeding up SAT solvers based on the DPLL procedure. However, most restart policies presented so far do not take the problem structure into account. In this paper we present several new problem-sensitive restart heuristics. They all observe different search parameters like conflict level or backtrack level over time and, based on their development, decide whether to perform a restart or not. We also present a Java tool to visualize these search parameters on a given SAT instance over time in order to analyze existing heuristics and develop new one.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Configuration lifting: Verification meets software configuration 08

Configuration lifting: Verification meets software configura...

引用

ASE 2008 - 23rd IEEE/ACM International Conference on Automated Software engineering

作者： Post, Hendrik Sinz, Carsten Research Group Verification Meets Algorithm Engineering Institute for Theoretical Computer Science University of Karlsruhe Germany

ISBN: (纸本)9781424421886

Configurable software is ubiquitous, and the term Software Product Line (SPL) has been coined for it lately. It remains a challenge, however, how such software can be verified over all variants. Enumerating all variants and analyzing them individually is inefficient, as knowledge cannot be shared between analysis runs. Instead of enumeration we present a new technique called lifting that converts all variants into a meta-program, and thus facilitates the configuration-aware application of verification techniques like static analysis, model checking and deduction-based approaches. As a side-effect, lifting provides a technique for checking software feature models, which describe software variants, for consistency. We demonstrate the feasibility of our approach by checking configuration dependent hazards for the highly configurable Linux kernel which possesses several thousand of configurable features. Using our techniques, two novel bugs in the kernel configuration system were found. © 2008 IEEE.

关键词： Static analysis

来源：评论

学校读者我要写书评

暂无评论

A fast point cloud precision registration method based on spatial grid division

A fast point cloud precision registration method based on sp...

引用

2021 International Conference of Optical Imaging and Measurement, ICOIM 2021

作者： Liu, Faheng Zhang, Chunwei Zhao, Hong Bao, Qingkang Hu, Min Zhang, Tianyu Xi'an Jiaotong University School of Mechanical Engineering Xi'an China Group 3D Algorithm Deptrum China

ISBN: (纸本)9780738112121

Point cloud precision registration is the most time-consuming link in registration, and the main factor that hinders point cloud registration from meeting the real-time requirement. In this paper we propose a fast point cloud precision registration method based on spatial grid division. By virtue of the spatial grid, the scattered point cloud is transformed into the spatial grid sequence. During the applicaton of the Iterative Closest Point (ICP) algorithm, we can get the neighborhood information of any point with the aid of the neighborhood information of the grid sequence to efficiently determine the nearest neighbor points. When calculating the nearest neighbor points, the grids don't interfere with each other. Hence, we can use GPU parallel processing to accelerate the search of the nearest neighbor points. Spatial grid division and parallel processing greatly improve registration efficiency. © 2021 IEEE.

关键词： Iterative methods

来源：评论

学校读者我要写书评

暂无评论

Transmission control design approach using simulation, rapid prototyping, and auto code generation

Transmission control design approach using simulation, rapid...

引用

2008 World Congress

作者： Yan, Kevin Quanzhong Trush, Christopher J. GM Powertrain EI and S Software Engineering Milford MI United States GM Powertrain Algorithm Development Group United States

A math-based approach is now in use to reduce transmission control algorithm development time and prototyping iterations, and to improve transmission control algorithm and software quality. This paper will describe the application of this efficient approach to the development of a transmission control algorithm for production. The processes for algorithm design, closed-loop and rapid prototype testing, auto-code generation of production software, and potential hardware-in-the-loop verification are described with references to supporting development tools. This approach enables upfront, math-based development and performance assessment of transmission control algorithms and their interactions with other powertrain and vehicle control algorithms. Examples will illustrate the efficiency of the control algorithm development approach over a wide range of conditions. Copyright © 2008 SAE International.

关键词： Software testing

来源：评论

学校读者我要写书评

暂无评论

Schelling segregation with strategic agents

arXiv

引用

arXiv 2018年

作者： Chauhan, Ankit Lenzner, Pascal Molitor, Louise Algorithm Engineering Group Hasso Plattner Institute Potsdam Germany

Schelling's segregation model is a landmark model in sociology. It shows the counterintuitive phenomenon that residential segregation between individuals of different groups can emerge even when all involved individuals are tolerant. Although the model is widely studied, no pure game-theoretic version where rational agents strategically choose their location exists. We close this gap by introducing and analyzing generalized game-theoretic models of Schelling segregation, where the agents can also have individual location preferences. For our models we investigate the convergence behavior and the efficiency of their equilibria. In particular, we prove guaranteed convergence to an equilibrium in the version which is closest to Schelling's original model. Moreover, we provide tight bounds on the Price of Anarchy. Copyright © 2018, The Authors. All rights reserved.

关键词： Game theory

来源：评论

学校读者我要写书评

暂无评论

Selfish network creation with non-uniform edge cost

arXiv

引用

arXiv 2017年

作者： Chauhan, Ankit Lenzner, Pascal Melnichenko, Anna Molitor, Louise Algorithm Engineering Group Hasso Plattner Institute Potsdam Germany

Network creation games investigate complex networks from a game-theoretic point of view. Based on the original model by Fabrikant et al. [PODC'03] many variants have been introduced. However, almost all versions have the drawback that edges are treated uniformly, i.e. every edge has the same cost and that this common parameter heavily inuences the outcomes and the analysis of these games. We propose and analyze simple and natural parameter-free network creation games with non-uniform edge cost. Our models are inspired by social networks where the cost of forming a link is proportional to the popularity of the targeted node. Besides results on the complexity of computing a best response and on various properties of the sequential versions, we show that the most general version of our model has constant Price of Anarchy. To the best of our knowledge, this is the first proof of a constant Price of Anarchy for any network creation game. Copyright © 2017, The Authors. All rights reserved.

关键词： Complex networks

来源：评论

学校读者我要写书评

暂无评论

Formation flying for distributed InSAR

Formation flying for distributed InSAR

引用

AIAA/AAS Astrodynamics Specialist Conference, 2006

作者： Scharf, Daniel P. Murray, Emmanuell A. Ploen, Scott R. Gromov, Konstantin G. Chen, Curtis W. Jet Propulsion Laboratory California Institute of Technology Pasadena CA 91109-8099 United States Guidance and Control Analysis Group United States AIAA United States Radar System Engineering and Algorithm Development Group

ISBN: (纸本)1563478226

We consider two spacecraft flying in formation to create an interferometric synthetic aperture radar (InSAR). Several candidate orbits for such an InSAR formation have been previously determined based on radar performance and Keplerian orbital dynamics. However, without active control, disturbance-induced drift can degrade radar performance and (in the worst case) cause a collision. This study evaluates the feasibility of operating the InSAR spacecraft as a formation, that is, with inter-spacecraft sensing and control. We describe the candidate InSAR orbits, design formation guidance and control architectures and algorithms, and report the Δv and control acceleration requirements for the candidate orbits for several tracking performance levels. As part of determining formation requirements, a formation guidance algorithm called Command Virtual Structure is introduced that can reduce Δv requirements compared to standard Leader/Follower formation approaches. In addition, an orbit maintenance and formation reconfiguration guidance algorithm is developed for changing both relative orbits and the overall formation orbit. Copyright © 2006 by the American Institute of Aeronautics, and Aeronautics, Inc.

关键词： Synthetic aperture radar

来源：评论

学校读者我要写书评

暂无评论

Transitions in Dynamic Point Labeling

arXiv

引用

arXiv 2022年

作者： Depian, Thomas Li, Guangping Nöllenburg, Martin Wulms, Jules Algorithms and Complexity Group TU Wien Vienna Austria Algorithm Engineering Group TU Dortmund Dortmund Germany

The labeling of point features on a map is a well-studied topic. In a static setting, the goal is to find a non-overlapping label placement for (a subset of) point features. In a dynamic setting, the set of point features and their corresponding labels change, and the labeling has to adapt to such changes. To aid the user in tracking these changes, we can use morphs, here called transitions, to indicate how a labeling changes. Such transitions have not gained much attention yet, and we investigate different types of transitions for labelings of points, most notably consecutive transitions and simultaneous transitions. We give (tight) bounds on the number of overlaps that can occur during these transitions. When each label has a (non-negative) weight associated to it, and each overlap imposes a penalty proportional to the weight of the overlapping labels, we show that it is NP-complete to decide whether the penalty during a simultaneous transition has weight at most k. Finally, in a case study, we consider geotagged Twitter data on a map, by labeling points with rectangular labels showing tweets. We developed a prototype implementation to evaluate different transition styles in practice, measuring both number of overlaps and transition duration. Copyright © 2022, The Authors. All rights reserved.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Generating All Invertible Matrices by Row Operations 35

Generating All Invertible Matrices by Row Operations

引用

35th International Symposium on algorithms and Computation, ISAAC 2024

作者： Gregor, Petr Hoang, Hung P. Merino, Arturo Mička, Ondřej Department of Theoretical Computer Science and Mathematical Logic Charles University Prague Czech Republic Algorithm and Complexity Group Faculty of Informatics TU Wien Austria Institute of Engineering Sciences Universidad de O’Higgins Rancagua Chile

ISBN: (纸本)9783959773546

We show that all invertible n × n matrices over any finite field Fq can be generated in a Gray code fashion. More specifically, there exists a listing such that (1) each matrix appears exactly once, and (2) two consecutive matrices differ by adding or subtracting one row from a previous or subsequent row, or by multiplying or dividing a row by the generator of the multiplicative group of Fq. This even holds in the more general setting where the pairs of rows that can be added or subtracted are specified by an arbitrary transition tree that has to satisfy some mild constraints. Moreover, we can prescribe the first and the last matrix if n ≥ 3, or n = 2 and q > 2. In other words, the corresponding flip graph on all invertible n × n matrices over Fq is Hamilton connected if it is not a cycle. This solves yet another special case of Lovász conjecture on Hamiltonicity of vertex-transitive graphs. © Petr Gregor, Hung P. Hoang, Arturo Merino, and Ondřej Mička.

关键词： Matrix algebra

来源：评论

学校读者我要写书评

暂无评论

Exact ILP solutions for phylogenetic Minimum Flip problems 10

Exact ILP solutions for phylogenetic Minimum Flip problems

引用

Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology

作者： Chimani, Markus Rahmann, Sven Böcker, Sebastian Algorithm Engineering Group Friedrich-Schiller-Universität 07743 Jena Germany Bioinformatics Computer Science XI TU Dortmund 44221 Dortmund Germany Department for Bioinformatics Friedrich-Schiller-Universität 07743 Jena Germany

ISBN: (纸本)9781450304382

In computational phylogenetics, the problem of constructing a consensus tree or supertree of a given set of rooted input trees can be formalized in different ways. We consider the Minimum Flip Consensus Tree and Minimum Flip Su-pertree problem, where input trees are transformed into a 0/1/?-matrix, such that each row represents a taxon, and each column represents a subtree membership. For the consensus tree problem, all input trees contain the same set of taxa, and no ?-entries occur. For the supertree problem, the input trees may contain different subsets of the taxa, and unrepresented taxa are coded with ?-entries. In both cases, the goal is to find a perfect phylogeny for the input matrix requiring a minimum number of 0/1-ips, i.e., matrix entry corrections. Both optimization problems are NP-hard. We present the first efficient Integer Linear Programming (ILP) formulations for both problems, using three distinct characterizations of a perfect phylogeny. Although these three formulations seem to differ considerably at first glance, we show that they are in fact polytope-wise equivalent. Introducing a novel column generation scheme, it turns out that the simplest, purely combinatorial formulation is the most efficient one in practice. Using our framework, it is possible to find exact solutions for instances with ∼100 taxa. Copyright © 2010 ACM.

关键词： Phylogenetic

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：