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

丛书名： Texts in Theoretical Computer Science. An EATCS Series

1000年

作者： Juraj Hromkovič

ISBN: (数字)9783662046166

Algorithmic design, especially for hard problems, is more essential for success in solving them than any standard improvement of current computer technologies. Because of this, the design of algorithms for solving hard problems is the core of current algorithmic research from the theoretical point of view as weIl as from the practical point of view. There are many general textbooks on algorithmics, and several specialized books devoted to particular approaches such as local search, randomization, approximation algorithms, or heuristics. But there is no textbook that focuses on the design of algorithms for hard computing tasks, and that systematically explains, combines, and compares the main possibilities for attacking hard algorithmic problems. As this topic is fundamental for computer science, this book tries to elose this gap. Another motivation, and probably the main reason for writing this book, is connected to education. The considered area has developed very dynamically in recent years and the research on this topic discovered several profound re sults, new concepts, and new methods. Some of the achieved contributions are so fundamental that one can speak about paradigms which should be ineluded in the education of every computer science student. Unfortunately, this is very far from reality. This is because these paradigms are not sufficiently known in the computer science community, and so they are insufficiently communicated to students and practitioners.

关键词： Discrete Mathematics in Computer Science Algorithm Analysis and Problem complexity Artificial Intelligence Computational Mathematics and Numerical Analysis Combinatorics complexity

来源：评论

学校读者我要写书评

暂无评论

Modular implementation of dense matrix operations in a high-level BSP language

Modular implementation of dense matrix operations in a high-...

引用

2010 International Conference on High Performance Computing and Simulation, HPCS 2010

作者： Tan, Sovanna Gava, Frédéric Laboratory of Algorithms Complexity and Logic University of Paris-East Créteil-Paris France

ISBN: (纸本)9781424468287

BSML is a high-level language for programming parallel algorithms. Built upon the OCaml language, it provides a safe setting for the implementation of BSP algorithms and for avoiding concurrency related problems (deadlocks, indeterminism, etc.). Dense matrices appear in many scientific computations but many libraries are limited to matrices of numeric elements. This paper is our first experiment to design a generic library of BSP implementation in ML of dense matrix operations for scientific computation. © 2010 IEEE.

关键词： High level languages

来源：评论

学校读者我要写书评

暂无评论

Fixed-parameter evolutionary algorithms and the vertex cover problem

Fixed-parameter evolutionary algorithms and the vertex cover...

引用

11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009

作者： Kratsch, Stefan Neumann, Frank Algorithms and Complexity Group Max-Planck-Institut für Informatik Saarbrücken Germany

ISBN: (纸本)9781605583259

In this paper, we consider multi-objective evolutionary algorithms for the Vertex Cover problem in the context of parameterized complexity. We relate the runtime of our algorithms to the input size and the cost of a minimum solution and point out that the search process of evolutionary algorithms creates partial solutions that are similar to the effect of a kernelization (i.e. a special type of preprocessing from parameterized complexity). Based on this, we show that evolutionary algorithms solve the vertex cover problem efficiently if the size of a minimum vertex cover is not too large, i.e. the expected runtime is bounded by O(f(OPT)nc), where c is a constant and f a function that only depends on OPT. This shows that evolutionary algorithms are randomized fixed-parameter tractable algorithms for the vertex cover problem. Copyright 2009 ACM.

关键词： Multiobjective optimization

来源：评论

学校读者我要写书评

暂无评论

The Evolution and Implications of the Inosine tRNA Modification

引用

Journal of Molecular Biology 2025年

作者： Peter T.S. van der Gulik Wouter D. Hoff Algorithms and Complexity Group Centrum Wiskunde & Informatica P.O. Box 94079 1090 GB Amsterdam the Netherlands Department of Microbiology and Molecular Genetics Oklahoma State University Stillwater OK 74078 USA

Ever since the legendary publication by Francis Crick in JMB introducing the wobble hypothesis in 1966, inosine has been a permanent part of molecular biology. This review aims to integrate the rich array of novel insights emerging from subsequent research on the adenine-to-inosine modification of tRNA, with an emphasis on the results obtained during the last 5 years. Both the grand panorama of 4 billion years of evolution of life and the medical implications of defects in inosine modification will be reviewed. The most salient insights are that: (1) inosine at position 34 (the first position in the anticodon) is not universally present in the tree of life; (2) in many bacteria just a single homodimeric enzyme (TadA) is responsible for both tRNA inosine modification and mRNA inosine modification; (3) rapid progress is currently being made both in the molecular understanding of the heterodimeric ADAT2/ADAT3 enzyme responsible for inosine modifications in eukaryotes and in experimental capabilities for monitoring both the cytoplasmic tRNA pool and their modifications; (4) for selected tRNAs, inosine modification at position 37 has been demonstrated but this modification remains under-studied; (5) modification of tRNAs known to contain inosine can be incomplete; (6) the GC content of the T-stem is of great importance for wobble behavior, including wobbling behavior of inosine; and (7) the tRNA inosine modification is of direct relevance to human disease. In summary, research on inosine continues to yield important novel insights.

关键词： Inosine Wobble Modopathies Eukaryogenesis Nanopore ADAT Adenosine deaminase acting on tRNA CDAT Cytosine deaminase acting on tRNA FECA First eukaryote common ancestor I Inosine LACA Last archaeal common ancestor LBCA Last bacterial common ancestor LECA Last eukaryote common ancestor LUCA Last universal common ancestor Ψ Pseudourine TAD tRNA-specific Adenosine Deaminase

来源：评论

学校读者我要写书评

暂无评论

Parameterized complexity of feature selection for categorical data clustering

arXiv

引用

arXiv 2021年

作者： Bandyapadhyay, Sayan Fomin, Fedor V. Golovach, Petr A. Simonov, Kirill Department of Informatics University of Bergen Norway Algorithms and Complexity Group TU Wien Austria

We develop new algorithmic methods with provable guarantees for feature selection in regard to categorical data clustering. While feature selection is one of the most common approaches to reduce dimensionality in practice, most of the known feature selection methods are heuristics. We study the following mathematical model. We assume that there are some inadvertent (or undesirable) features of the input data that unnecessarily increase the cost of clustering. Consequently, we want to select a subset of the original features from the data such that there is a small-cost clustering on the selected features. More precisely, for given integers (the number of irrelevant features) and k (the number of clusters), budget B, and a set of n categorical data points (represented by m-dimensional vectors whose elements belong to a finite set of values Σ), we want to select m − relevant features such that the cost of any optimal k-clustering on these features does not exceed B. Here the cost of a cluster is the sum of Hamming distances (0-distances) between the selected features of the elements of the cluster and its center. The clustering cost is the total sum of the costs of the clusters. We use the framework of parameterized complexity to identify how the complexity of the problem depends on parameters k, B, and |Σ|. Our main result is an algorithm that solves the Feature Selection problem in time f(k, B, |Σ|) · mg(k,|Σ|) · n2 for some functions f and g. In other words, the problem is fixed-parameter tractable parameterized by B when |Σ| and k are constants. Our algorithm for Feature Selection is based on a solution to a more general problem, Constrained Clustering with Outliers. In this problem, we want to delete a certain number of outliers such that the remaining points could be clustered around centers satisfying specific constraints. One interesting fact about Constrained Clustering with Outliers is that besides Feature Selection, it encompasses many other fundamental pro

关键词： Clustering algorithms

来源：评论

学校读者我要写书评

暂无评论

Transitions in Dynamic Point Labeling 12

Transitions in Dynamic Point Labeling

引用

12th International Conference on Geographic Information Science, GIScience 2023

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

ISBN: (纸本)9783959772884

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. © Thomas Depian, Guangping Li, Martin Nöllenburg, and Jules Wulms.

关键词： Information retrieval

来源：评论

学校读者我要写书评

暂无评论

Boundary Labeling in a Circular Orbit 32

Boundary Labeling in a Circular Orbit

引用

32nd International Symposium on Graph Drawing and Network Visualization, GD 2024

作者： Bonerath, Annika Nöllenburg, Martin Terziadis, Soeren Wallinger, Markus Wulms, Jules University of Bonn Germany Algorithms and Complexity Group TU Wien Austria TU Eindhoven Netherlands Chair for Efficient Algorithms TU Munich Germany

ISBN: (纸本)9783959773430

Boundary labeling is a well-known method for displaying short textual labels for a set of point features in a figure alongside the boundary of that figure. Labels and their corresponding points are connected via crossing-free leaders. We propose orbital boundary labeling as a new variant of the problem, in which (i) the figure is enclosed by a circular contour and (ii) the labels are placed as disjoint circular arcs in an annulus-shaped orbit around the contour. The algorithmic objective is to compute an orbital boundary labeling with the minimum total leader length. We identify several parameters that define the corresponding problem space: two leader types (straight or orbital-radial), label size and order, presence of candidate label positions, and constraints on where a leader attaches to its label. Our results provide polynomial-time algorithms for many variants and NP-hardness for others, using a variety of geometric and combinatorial insights. © Annika Bonerath, Martin Nöllenburg, Soeren Terziadis, Markus Wallinger, and Jules Wulms.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Data signature-based multiyear analysis of BLK-NB 6-minute interval datasets of 2006 to 2009

Data signature-based multiyear analysis of BLK-NB 6-minute i...

引用

2012 IEEE/ACIS 11th International Conference on Computer and Information Science, ICIS 2012

作者： Villena, Junnel C. Malinao, Jasmine A. Adorna, Henry N. Department of Computer Science Algorithms and Complexity Laboratory University of Philippines Diliman Quezon City 1101 Philippines

ISBN: (纸本)9780769546940

In this paper, we present a multiyear analysis of the North Luzon Expressway Balintawak-NorthBound (NLEX BLKNB) Datasets of 2006 to 2009 using the 6-minute Interval traffic volume obtained from the National Center of Transportation Studies (NCTS). Previous works have only explored the behavior and characteristics of hourly interval datasets where in, however descriptive, we think is still limited. The analysis includes extracting valuable information like common problems faced by motorist and traffic enforcers based from the trends and behaviors of the traffic flow given the traffic volume of the Balintawak corridor in NLEX for each 6-minute interval in every week of the years 2006 to 2009. By getting the data signature and applying X-Means clustering algorithm, Vector Fusion and nMDS algorithms to obtain visualizations needed for analysis, we are able to detect 12 outliers, some of which are previously known and unknown. We are also able to extract 90 different types of potential outliers from the datasets and analyze their behavior and commonality. Moreover, we are able to realize recurring patterns and relate gathered results to different factors such as holidays and weather disturbances. In addition, we are able to gather data about what may be the role of the SBPy component in characterizing the dataset. Finally, we conclude that the 6-minute Interval dataset has provided us with an effective visualization model used for traffic data analysis and a more in-depth level of characterization of the traffic behavior in NLEX, BLK-NB. © 2012 IEEE.

关键词： Visualization

来源：评论

学校读者我要写书评

暂无评论

Parameterized complexity of Caching in Networks*

arXiv

引用

arXiv 2024年

作者： Ganian, Robert Inerney, Fionn Mc Tsigkari, Dimitra Algorithms and Complexity Group TU Wien Vienna Austria Telefónica Scientific Research Barcelona Spain

The fundamental caching problem in networks asks to find an allocation of contents to a network of caches with the aim of maximizing the cache hit rate. Despite the problem's importance to a variety of research areas-including not only content delivery, but also edge intelligence and inference-and the extensive body of work on empirical aspects of caching, very little is known about the exact boundaries of tractability for the problem beyond its general NPhardness. We close this gap by performing a comprehensive complexity-theoretic analysis of the problem through the lens of the parameterized complexity paradigm, which is designed to provide more precise statements regarding algorithmic tractability than classical complexity. Our results include algorithmic lower and upper bounds which together establish the conditions under which the caching problem becomes tractable. Copyright © 2024, The Authors. All rights reserved.

关键词： Complex networks

来源：评论

学校读者我要写书评

暂无评论

Lossy Kernelization of Same-Size Clustering 1

引用

17th International Computer Science Symposium in Russia, CSR 2022

作者： Bandyapadhyay, Sayan Fomin, Fedor V. Golovach, Petr A. Purohit, Nidhi Siminov, Kirill Department of Informatics University of Bergen Bergen Norway Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (数字)9783031095740

ISBN: (纸本)9783031095733

In this work, we study the k-median clustering problem with an additional equal-size constraint on the clusters, from the perspective of parameterized preprocessing. Our main result is the first lossy (2-approximate) polynomial kernel for this problem, parameterized by the cost of clustering. We complement this result by establishing lower bounds for the problem that eliminate the existences of an (exact) kernel of polynomial size and a PTAS. © 2022, Springer Nature Switzerland AG.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：