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

34th International Workshop on Graph-Theoretic Concepts in Computer Science

作者： Bonsma, Paul Zickfeld, Florian Tech Univ Berlin Inst Math D-10623 Berlin Germany

ISBN: (纸本)9783540922476

We consider the problem of finding a spanning tree that maximizes the number of leaves (MAXLEAF). We provide a 3/2-approximation algorithm for this problem when restricted to cubic graphs, improving on the previous 5/3-approximation for this class. To obtain this approximation we define a graph parameter x(G), and construct a tree with at least (n - x(G) + 4)/3 leaves, and prove that no tree with more than (n - x(G) + 2)/2 leaves exists. In contrast to previous approximation algorithms for MAXLEAF;our algorithm works with connected dominating sets instead of constructing a tree directly. The algorithm also yields a 4/3-approximation for Minimum Connected Dominating Set in cubic graphs.

关键词： approximation algorithm maximum leaf connected dominating set cubic graph

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for the minimum latency set cover problem

An approximation algorithm for the minimum latency set cover...

引用

13th Annual European Symposium on algorithms (ESA 2005)

作者： Hassin, R Levin, A Tel Aviv Univ Dept Stat & Operat Res Tel Aviv Israel Hebrew Univ Jerusalem Dept Stat IL-91905 Jerusalem Israel

ISBN: (纸本)3540291180

The input to the MINIMUM LATENCY SET COVER PROBLEM consists of a set of jobs and a set of tools. Each job j needs a specific subset S-j of the tools in order to be processed. It is possible to install a single tool in every time unit. Once the entire subset S-j has been installed, job j can be processed instantly. The problem is to determine an order of job installations which minimizes the weighted sum of job completion times. We show that this problem is NP-hard in the strong sense and provide an e-approximation algorithm. Our approximation algorithm uses a framework of approximation algorithms which were developed for the minimum latency problem.

关键词： minimum sum set cover minimum latency approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Design of approximation algorithm for Efficient DNA Mapping using Hadoop Technology

A Design of Approximation Algorithm for Efficient DNA Mappin...

引用

International Conference on Advanced Communication Control and Computing Technologies (ICACCCT)

作者： Chaturvedi, Prashant Vel Tech Univ Comp Sci & Engn High Performance Comp Solut Chennai Tamil Nadu India C DAC Pune Maharashtra India

ISBN: (纸本)9781467395458

DNA Sequencing is a process where we determine and identify every single DNA base and element that is in the genome of an individual. There are six billion of those in every normal cell in every person. When we apply DNA sequencing in the Cancer project. We first figure out what those six billion DNA bases are in the normal cells in that person and then we take some of the tumor in that person and figure out what the DNA bases are in the tumor. In this paper, Here we discuss implements and future works in bioinformatics with Hadoop. We study the MapReduce algorithm from algorithm lay by point and demonstrate the appropriates of our approach by tracing and analyzing efficient MapReduce algorithms for sorting and simulation problem of parallel algorithms specified in the help of pigeonhole principle. The big data is a great computational challenge to statistical analysis of DNA big data. We can get general statistical analysis through R language. After studying the survey paper various approaches of using GPU and MapReduce. We adopted the best solution to using R with MapReduce. An R package is created to shift a set of critical R functions on GPU card. It allows users to run R code with GPU spread that enable much faster large data set of computation.

关键词： Big Data approximation algorithm Pigeonhole Principle NVIDIA card

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for the B-prize-collecting Multicut Problem in Trees 17th

An Approximation Algorithm for the B-prize-collecting Multic...

引用

17th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Liu, Xiaofei Li, Weidong Yunnan Univ Sch Informat Sci & Engn Kunming Yunnan Peoples R China Yunnan Univ Sch Math & Stat Kunming Yunnan Peoples R China

ISBN: (纸本)9783031203497;9783031203503

In this paper, we consider the B-prize-collecting multicut problem in trees. In this problem, we are given a tree T = (V, E), a set of k source-sink pairs P = {(s(1), t(1)), (s(2), t(2)),..., (s(k), t(k))} and a profit bound B. Every edge e is an element of E has a cost c(e), and every source-sink pair (s(j), t(j)). P has a profit p(j) and a penalty pi(j). This problem is to find a multicut M subset of E such that the total cost, which consists of the total cost of the edges in M and the total penalty of the pairs still connected after removing M, is minimized and the total profit of the disconnected pairs by removing M is at least B. Based on the primal-dual scheme, we present an (8/3 + epsilon)-approximation algorithm by carefully increasing the penalty, where epsilon is any fixed positive number.

关键词： Multicut problem in trees B-prize-collecting approximation algorithm Primal-dual scheme

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for the Two-Node-Connected Star Problem with Steiner Nodes

引用

Electronic Notes in Discrete Mathematics 2018年 69卷 173-180页

作者： Ferreira, Graciela Robledo, Franco Romero, Pablo Instituto de Matemática y Estadística Facultad de Ingeniería Universidad de la República Montevideo Uruguay

The goal in topological network design is to build a minimum-cost topology meeting specific real-life constraints. There is a cost-robustness trade-off under single and multiple failures. Previous works in the field suggest that a backbone composed by a two-node-connected toplogy provides savings with respect to elementary cycles. Consequently, we introduce the Two-Node Connected Star Problem with Steiner Nodes (2NCSP-SN). The goal is to design a minimum-cost topology, where the backbone is two-node connected, the access network is connected in a star topology or by direct links to the backbone, and optional nodes (called Steiner nodes) could be included in the solution. The 2NCSP-SN belongs to the class of NP-Hard problems. This promotes the development of heuristics and approximation algorithms. An approximation algorithm of factor 4α for the 2NCSP-SN is introduced, being α≥1/2 the cost-ratio between backbone and access links. This is a generalization of the well-known factor 2 for the design of minimum-cost two-connected spanning networks (if we fix α=1/2). Finally, an exact Integer Linear Programming (ILP) formulation is proposed in order to highlight the effectiveness of the approximation algorithm. The results confirm a small gap between the globally optimum solution and the topology offered by our approximation algorithm when the ratio α is close to 1/2. © 2018 Elsevier B.V.

关键词： approximation algorithm Integer Linear Programming Network Optimization

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for Computing the Visibility Region of a Point on a Terrain and Visibility Testing

An Approximation Algorithm for Computing the Visibility Regi...

引用

9th International Conference on Computer Vision Theory and Applications (VISAPP)

作者： Alipour, Sharareh Ghodsi, Mohammad Gudukbay, Ugur Golkari, Morteza Sharif Univ Technol Dept Comp Engn Tehran Iran Sharif Univ Technol Dept Comp Engn Tehran Iran Sharif Univ Technol Inst Res Fundamental Sci IPM Tehran Iran Bilkent Univ Dept Comp Engn Ankara Turkey

ISBN: (纸本)9789897581335

Given a terrain and a query point p on or above it, we want to count the number of triangles of terrain that are visible from p. We present an approximation algorithm to solve this problem. We implement the algorithm and then we run it on the real data sets. The experimental results show that our approximation solution is very close to the real solution and compare to the other similar works, the running time of our algorithm is better than their algorithm. The analysis of time complexity of algorithm is also presented. Also, we consider visibility testing problem, where the goal is to test whether p and a given triangle of train are visible or not. We propose an algorithm for this problem and show that the average running time of this algorithm will be the same as running time of the case where we want to test the visibility between two query point p and q.

关键词： Computational Geometry Visibility approximation algorithm Terrain

来源：评论

学校读者我要写书评

暂无评论

A 3.5-approximation algorithm for Sorting by Intergenic Transpositions 7th

A 3.5-Approximation Algorithm for Sorting by Intergenic Tran...

引用

7th International Conference on algorithms for Computational Biology (AlCoB) / 8th International Conference on algorithms for Computational Biology (AlCoB)

作者： Oliveira, Andre Rodrigues Jean, Geraldine Fertin, Guillaume Brito, Klairton Lima Dias, Ulisses Dias, Zanoni Univ Estadual Campinas Inst Comp Campinas Brazil Univ Nantes LS2N UMR CNRS 6004 Nantes France Univ Estadual Campinas Sch Technol Limeira Brazil

ISBN: (纸本)9783030422660;9783030422653

Genome Rearrangements affect large stretches of genomes during evolution. One of the most studied genome rearrangement is the transposition, which occurs when a sequence of genes is moved to another position inside the genome. Mathematical models have been used to estimate the evolutionary distance between two different genomes based on genome rearrangements. However, many of these models have focused only on the (order of the) genes of a genome, disregarding other important elements in it. Recently, researchers have shown that considering existing regions between each pair of genes, called intergenic regions, can enhance the distance estimation in realistic data. In this work, we study the transposition distance between two genomes, but we also consider intergenic regions, a problem we name Sorting Permutations by Intergenic Transpositions (SbIT). We show that this problem is NP-hard and propose a 3.5-approximation algorithm for it.

关键词： Genome rearrangements Intergenic regions Transpositions approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for Shortest Path in Large Social Networks

引用

algorithmS 2020年第2期13卷 36页

作者： Mensah, Dennis Nii Ayeh Gao, Hui Yang, Liang Wei Univ Elect Sci & Technol China Big Data Res Ctr Chengdu 610051 Peoples R China

Proposed algorithms for calculating the shortest paths such as Dijikstra and Flowd-Warshall's algorithms are limited to small networks due to computational complexity and cost. We propose an efficient and a more accurate approximation algorithm that is applicable to large scale networks. Our algorithm iteratively constructs levels of hierarchical networks by a node condensing procedure to construct hierarchical graphs until threshold. The shortest paths between nodes in the original network are approximated by considering their corresponding shortest paths in the highest hierarchy. Experiments on real life data show that our algorithm records high efficiency and accuracy compared with other algorithms.

关键词： parallel programing complex networks hierarchical networks approximation algorithm shortest path

来源：评论

学校读者我要写书评

暂无评论

A Local Search approximation algorithm for a Squared Metric k-Facility Location Problem 11th

A Local Search Approximation Algorithm for a Squared Metric ...

引用

11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Zhang, Dongmei Xu, Dachuan Wang, Yishui Zhang, Peng Zhang, Zhenning Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China Beijing Univ Technol Coll Appl Sci Dept Informat & Operat Res Beijing 100124 Peoples R China Shandong Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China

ISBN: (纸本)9783319711508;9783319711492

In this paper, we introduce a squared metric k-facility location problem (SM-k-FLP) which is a generalization of the squared metric facility location problem (SMFLP) and k-facility location problem (k-FLP). In the SM-k-FLP, we are given a client set C and a facility set F from a metric space, a facility opening cost f(i) >= 0 for each i is an element of F, and an integer k. The goal is to open a facility subset F subset of F with vertical bar F vertical bar <= k and to connect each client to the nearest open facility such that the total cost (including facility opening cost and the sum of squares of distances) is minimized. Using local search and scaling techniques, we offer a constant approximation algorithm for the SM-k-FLP.

关键词： approximation algorithm Facility location Local search

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for the Two-Stage Distributionally Robust Facility Location Problem 3

An Approximation Algorithm for the Two-Stage Distributionall...

引用

3rd World Congress of Global Optimization (WCGO)

作者： Wu, Chenchen Du, Donglei Xu, Dachuan Tianjin Univ Technol Coll Sci Tianjin 300384 Peoples R China Beijing Univ Technol Dept Appl Math Beijing 100124 Peoples R China Univ New Brunswick Fac Business Adm Fredericton NB E3B 9Y2 Canada

ISBN: (纸本)9783319083773;9783319083766

In this paper, we introduce a model of distributionally robust facility location problem (DRFLP) under moment constraints up to the second order. We show, via duality theory of moment problems, that the linear relaxation of the DRFLP is equivalent to that of the standard uncapacitated facility location problem (UFLP). Consequently, any LP-based approximation algorithm for the UFLP implies an approximation algorithm for the DRFLP with the same approximation ratio.

关键词： Facility location problem approximation algorithm Distributionally robust optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：