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

2014全国理论计算机科学学术年会

作者： Xingfu Li Daming Zhu School of Computer Science and Technology Shandong UniversityJinanShandong 250100China

We consider the path cover problem which is to find a set of vertex-disjoint paths for a simple undirectedgraph with maximum number of edges to cover all vertices of this *** path cover problem isNP-hard because the well known Hamilton path problem is NP complete and the Hamilton path problemis a special case of the path cover *** this paper we present a new upper bound for the size of asolution of the path cover problem We believe that the upper bound is useful for our future *** application,we devise a 7-10approximation algorithm whose time complexity is O(|V‖E|1.5log(|V|))where |V| is the number of vertices and |E| is the number of edges of a *** that the bestapproximation ratio is 6-7 which is achieved by Berman et al[20].However,their algorithm has timecomplexity O(|V|9) which is much slower than ours.

关键词： approximation algorithm upper bound path cover

来源：评论

学校读者我要写书评

暂无评论

Lazy and eager approaches for the set cover problem 14

Lazy and eager approaches for the set cover problem

引用

Proceedings of the Thirty-Seventh Australasian Computer Science Conference - Volume 147

作者： Ching Lih Lim Alistair Moffat Anthony Wirth The University of Melbourne Victoria Australia

ISBN: (纸本)9781921770302

The Set Cover problem is tantalizingly simple to describe: given a collection F of sets, each containing a subset of a universe U of objects, find a smallest sub-collection A of F such that every object in U is included in at least one of the sets in A. However, like many such combinatorial problems, Set Cover is NP-hard, meaning that it is unlikely that an efficient algorithm will be found, and that approximation algorithms must be preferred for non-trivial problem instances. One well-known approximation approach for Set Cover is to repeatedly add the set with the most uncovered items to the solution, continuing until every element in the universe is covered; this Greedy approach has a provable logarithmic approximation ratio, essentially the best feasible ratio. Here we study the implementation of the Greedy approach to Set Cover, evaluating eager and lazy versions and other implementation options. Experiments with several large datasets demonstrate that lazy "as required" priority queue updates should be preferred, rather than eager "as soon as possible" ones; and that when implemented in this way, the Greedy mechanism can solve some large instances of the Set Cover problem very quickly. This practical superiority contrasts with the lazy version's having a demonstrably higher worst-case operation cost.

关键词： priority queue set cover lazy update approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Constant-Factor approximation for Multi-Covering with Disks 13

A Constant-Factor Approximation for Multi-Covering with Disk...

引用

29th Annual Symposium on Computational Geometry (SoCG)

作者： Bhowmick, Santanu Varadarajan, Kasturi Xue, Shi-Ke Univ Iowa Dept Comp Sci Iowa City IA 52242 USA MIT Dept Comp Sci Cambridge MA 02139 USA

ISBN: (纸本)9781450320313

We consider variants of the following multi-covering problem with disks. We are given two point sets Y (servers) and X (clients) in the plane, and a coverage function kappa : X -> N. Centered at each server is a single disk whose radius we are free to set. The requirement is that each client x is an element of X be covered by at least kappa(x) of the server disks. The objective function we wish to minimize is the sum of the areas of the disks. We present a polynomial time algorithm for this problem achieving an O(1) approximation.

关键词： approximation algorithm Geometric Set Cover

来源：评论

学校读者我要写书评

暂无评论

Efficient 2-approximation algorithms for Computing 2-Connected Steiner Minimal Networks

引用

IEEE TRANSACTIONS ON COMPUTERS 2012年第7期61卷 954-968页

作者： Shen, Hong Guo, Longkun Beijing Jiaotong Univ Sch Comp & Informat Technol Beijing Peoples R China Univ Adelaide Sch Comp Sci Adelaide SA 5005 Australia Fuzhou Univ Sch Math & Comp Sci Fuzhou 350108 Fujian Peoples R China

For an undirected and weighted graph G = (V, E) and a terminal set S subset of V, the 2-connected Steiner minimal network (SMN) problem requires to compute a minimum-weight subgraph of G in which all terminals are 2-connected to each other. This problem has important applications in design of survivable networks and fault-tolerant communication, and is known MAXSNP-hard [7], a harder subclass of NP-hard problems for which no polynomial-time approximation scheme (PTAS) is known. This paper presents an efficient algorithm of O(|V|(2)|S|(3)) time for computing a 2-vertex connected Steiner network (2V SN) whose weight is bounded by two times of the optimal solution 2-vertex connected SMN (2V SMN). It compares favorably with the currently known 2-approximation solution to the 2V SMN problem based on that to the survivable network design problem [10], [16], with a time complexity reduction of O(|V|(5)|E|(7)) for strongly polynomial time and O(|V|(5)gamma) for weakly polynomial time where gamma is determined by the sizes of input. Our algorithm applies a novel greedy approach to generate a 2V SN through progressive improvement on a set of vertex-disjoint shortest path pairs incident with each terminal of S. The algorithm can be directly deployed to solve the 2-edge connected SMN problem at the same approximation ratio within time O(|V|(2)|S|(2)). To the best of our knowledge, this result presents currently the most efficient 2-approximation algorithm for the 2-connected Steiner minimal network problem.

关键词： Survivable network design 2-vertex (edge) connected Steiner minimal network terminal spanning-tree approximation algorithm shortest disjoint path pair Euler walk

来源：评论

学校读者我要写书评

暂无评论

Near optimal solutions for maximum quasi-bicliques

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2013年第3期25卷 481-497页

作者： Wang, Lusheng City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China

The maximum quasi-biclique problem has been proposed for finding interacting protein group pairs from large protein-protein interaction (PPI) networks. The problem is defined as follows: The Maximum Quasi-biclique Problem: Given a bipartite graph G=(Xa(a)Y,E) and a number 0 approximation scheme to give a quasi-biclique X'aS dagger X and Y'aS dagger Y with |X'|+|Y'|a parts per thousand yen(1-epsilon)(|X (opt) |+|Y (opt) |) such that any vertex xaX' is incident to at least (1-delta-epsilon)|Y'| vertices in Y' and any vertex yaY' is incident to at least (1-delta-epsilon)|X'| vertices in X' for any epsilon > 0, where X (opt) and Y (opt) form the optimal solution.

关键词： Protein-protein interaction networks Interacting protein group pairs Protein interaction sites Quasi-bicliques approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Exact and approximation algorithms for the complementary maximal strip recovery problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2012年第4期23卷 493-506页

作者： Jiang, Haitao Li, Zhong Lin, Guohui Wang, Lusheng Zhu, Binhai Montana State Univ Dept Comp Sci Bozeman MT 59717 USA Shandong Univ Sch Comp Sci & Technol Jinan 250100 Shandong Peoples R China Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China

Given two genomic maps G(1) and G(2) each represented as a sequence of n gene markers, the maximal strip recovery (MSR) problem is to retain the maximum number of markers in both G(1) and G(2) such that the resultant subsequences, denoted as G(1)* and G(2)*, can be partitioned into the same set of maximal substrings of length greater than or equal to two. Such substrings can occur in the reversal and negated form. The complementary maximal strip recovery (CMSR) problem is to delete the minimum number of markers from both G(1) and G(2) for the same purpose, with its optimization goal exactly complementary to maximizing the total number of gene markers retained in the final maximal substrings. Both MSR and CMSR have been shown NP-hard and APX-hard. A 4-approximation algorithm is known for the MSR problem, but no constant ratio approximation algorithm for CMSR. In this paper, we present an O(3(k)n(2))-time fixed-parameter tractable (FPT) algorithm, where k is the size of the optimal solution, and a 3-approximation algorithm for the CMSR problem.

关键词： Fixed-parameter tractable approximation algorithm Amortized analysis

来源：评论

学校读者我要写书评

暂无评论

On approximating the d-girth of a graph

引用

DISCRETE APPLIED MATHEMATICS 2013年第16-17期161卷 2587-2596页

作者： Peleg, David Sau, Ignasi Shalom, Mordechai Weizmann Inst Sci IL-76100 Rehovot Israel CNRS LIRMM Montpellier France TelHai Acad Coll IL-12210 Upper Galilee Israel

For a finite, simple, undirected graph G and an integer d >= 1, a mindeg-d subgraph is a subgraph of G of minimum degree at least d. The d-girth of G, denoted by g(d)(G), is the minimum size of a mindeg-d subgraph of G. It is a natural generalization of the usual girth, which coincides with the 2-girth. The notion of d-girth was proposed by Erdos et al. (1988, 1990) [14,15] and Bollobas and Brightwell (1989) [8] over 25 years ago, and studied from a purely combinatorial point of view. Since then, no new insights have appeared in the literature. Recently, first algorithmic studies of the problem have been carried out by Amini et al. (2012a,b) [2,4]. The current article further explores the complexity of finding a small mindeg-d subgraph of a given graph (that is, approximating its d-girth), by providing new hardness results and the first approximation algorithms in general graphs, as well as analyzing the case where G is planar. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Generalized girth Minimum degree approximation algorithm Hardness of approximation Randomized algorithm Planar graph

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for the robust fault-tolerant facility location problem

引用

INFORMATION PROCESSING LETTERS 2012年第10期112卷 361-364页

作者： Li, Yu Xu, Dachuan Du, Donglei Xiu, Naihua Beijing Univ Technol Dept Appl Math Beijing 100124 Peoples R China Beijing Jiaotong Univ Sch Sci Dept Math Beijing 100044 Peoples R China Univ New Brunswick Fac Business Adm Fredericton NB E3B 5A3 Canada

We consider the robust alpha fault-tolerant facility location problem (alpha-RFLP), recently introduced by Chechik and Peleg (2010) [6]. We present an improved approximation algorithm with ratio 5.236 for the 1-RFLP comparing to 6.5 by Chechik and Peleg's. For the general alpha-RFLP (fixed alpha >= 2), the same algorithm with a different subroutine tailored for alpha >= 2 provides an improved approximation ratio 1.005 + 6.015 alpha comparing to 1.5 + 7.5 alpha by Chechik and Peleg's. The key component of our algorithm is the resolution of an auxiliary facility location problem (FLP) by a variant of the LP-rounding technique of Byrka and Aardal (2010) [2] to estimate the total weighted facility open cost and shipping cost. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Facility location approximation algorithm Fault tolerance

来源：评论

学校读者我要写书评

暂无评论

Route-Enabling Graph Orientation Problems

引用

algorithmICA 2013年第2期65卷 317-338页

作者： Ito, Takehiro Miyamoto, Yuichiro Ono, Hirotaka Tamaki, Hisao Uehara, Ryuhei Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan Sophia Univ Fac Sci & Technol Chiyoda Ku Tokyo 1028554 Japan Kyushu Univ Fac Econ Higashi Ku Fukuoka 8128581 Japan Meiji Univ Sch Sci & Technol Tama Ku Kawasaki Kanagawa 2148571 Japan JAIST Sch Informat Sci Nomi Ishikawa 9231292 Japan

Given an undirected and edge-weighted graph G together with a set of ordered vertex-pairs, called st-pairs, we consider two problems of finding an orientation of all edges in G: min-sum orientation is to minimize the sum of the shortest directed distances between all st-pairs;and min-max orientation is to minimize the maximum shortest directed distance among all st-pairs. Note that these shortest directed paths for st-pairs are not necessarily edge-disjoint. In this paper, we first show that both problems are strongly NP-hard for planar graphs even if all edge-weights are identical, and that both problems can be solved in polynomial time for cycles. We then consider the problems restricted to cacti, which form a graph class that contains trees and cycles but is a subclass of planar graphs. Then, min-sum orientation is solvable in polynomial time, whereas min-max orientation remains NP-hard even for two st-pairs. However, based on LP-relaxation, we present a polynomial-time 2-approximation algorithm for min-max orientation. Finally, we give a fully polynomial-time approximation scheme (FPTAS) for min-max orientation on cacti if the number of st-pairs is a fixed constant.

关键词： approximation algorithm Cactus Dynamic programming Fully polynomial-time approximation scheme Graph orientation Planar graph Reachability

来源：评论

学校读者我要写书评

暂无评论

On the k-edge-incident subgraph problem and its variants

引用

DISCRETE APPLIED MATHEMATICS 2013年第18期161卷 2985-2991页

作者： Liang, Hongyu Tsinghua Univ Inst Interdisciplinary Informat Sci Beijing 100084 Peoples R China

Given a node-weighted graph G = (V, E) and an integer k, the k-edge-incident subgraph problem requires one to find a vertex set S subset of V of maximum weight that covers at most k edges, and the minimum partial vertex cover problem requires one to find a set of k vertices that covers the minimum number of edges. These two problems are closely related to the well-studied densest k-subgraph problem, and are interesting on their own. In this paper, we study these two problems from an approximation point of view. We obtain the following results. 1. For the k-edge-incident subgraph problem, we present a (2 + epsilon) approximation algorithm for any fixed epsilon > 0, which improves the previous best approximation ratio of 3 and matches that of its unweighted version [O. Goldschmidt and D.S. Hochbaum, k-edge subgraph problems, Discrete Appl. Math. 74 (2) (1997) 159-169]. 2. For the minimum partial vertex cover problem, we give a 2-approximation algorithm. We then propose a polynomial-time approximation scheme (PTAS) for it on the class of everywhere-c-dense graphs on which many well-studied combinatorial problems have been investigated. (C) 2013 Elsevier B.V. All rights reserved.

关键词： k-edge-incident subgraph problem Minimum partial vertex cover problem approximation algorithm Dense graph Polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：