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

Improved approximation algorithms for Label Cover Problems

algorithmICA 2011年第1期61卷 190-206页

作者： Charikar, Moses Hajiaghayi, MohammadTaghi Karloff, Howard Princeton Univ Dept Comp Sci Princeton NJ 08540 USA Univ Maryland College Pk MD 20742 USA AT&T Labs Res Florham Pk NJ 07932 USA

In this paper we consider both the maximization variant MAX REP and the minimization variantMIN REP of the famous LABEL COVER problem. So far the best approximation ratios known for these two problems were O(root n) and indeed some authors suggested the possibility that this ratio is the best approximation factor for these two problems. We show, in fact, that there are a O(n(1/3))-approximation algorithm for MAX REP and a O(n(1/3)log(2/3) n)-approximation algorithm for MIN REP. In addition, we also exhibit a randomized reduction from DENSEST k-SUBGRAPH to MAX REP, showing that any approximation factor for MAX REP implies the same factor (up to a constant) for DENSEST k-SUBGRAPH.

关键词： LABEL COVER approximation algorithm Hardness of approximation MIN REP MAX REP DENSEST k-SUBGRAPH

来源：评论

学校读者我要写书评

暂无评论

The complexity of minimum convex coloring

The complexity of minimum convex coloring

引用

4th Workshop on Graph Classes, Optimization, and Width Parameters (GROW)

作者： Kammer, Frank Tholey, Torsten Univ Augsburg Inst Informat D-86135 Augsburg Germany

A coloring of the vertices of a graph is called convex if each subgraph induced by all vertices of the same color is connected. We consider three variants of recoloring a colored graph with minimal cost such that the resulting coloring is convex. Two variants of the problem are shown to be N P-hard on trees even if in the initial coloring each color is used to color only a bounded number of vertices. For graphs of bounded treewidth, we present a polynomial-time (2 + epsilon)-approximation algorithm for these two variants and a polynomial-time algorithm for the third variant. Our results also show that, unless NP subset of DTIME(n(0(log logn))) there is no polynomial-time approximation algorithm with a ratio of size (1 - o(1)) In In N for the following problem: given pairs of vertices in an undirected N-vertex graph of bounded treewidth, determine the minimal possible number l for which all except l pairs can be connected by disjoint paths. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Convex coloring approximation algorithm Treewidth Maximum disjoint paths problem Set cover

来源：评论

学校读者我要写书评

暂无评论

Minimizing Data Collection Latency in Wireless Sensor Network with Multiple Mobile Elements

Minimizing Data Collection Latency in Wireless Sensor Networ...

引用

IEEE INFOCOM Conference

作者： Kim, Donghyun Abay, Baraki H. Uma, R. N. Wu, Weili Wang, Wei Tokuta, Alade O. N Carolina Cent Univ Dept Math & Comp Sci Durham NC 27707 USA Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA Xi An Jiao Tong Univ Dept Math Xian 710049 Peoples R China

ISBN: (纸本)9781467307758

This paper considers the problem of computing the optimal trajectories of multiple mobile elements (e. g. robots, vehicles, etc.) to minimize data collection latency in wireless sensor networks (WSNs). By relying on slightly different assumption, we define two interesting problems, the k-traveling salesperson problem with neighborhood (k-TSPN) and the k-rooted path cover problem with neighborhood (k-PCPN). Since both problems are NP-hard, we propose constant factor approximation algorithms for them. Our simulation results indicate our algorithms outperform their alternatives.

关键词： approximation algorithm graph theory wireless sensor network mobile elements traveling salesperson problem with neighborhood k-rooted tree cover problem

来源：评论

学校读者我要写书评

暂无评论

ACCURATE AND FAST HAND-FOREARM SEGMENTATION algorithm BASED ON SILHOUETTE

ACCURATE AND FAST HAND-FOREARM SEGMENTATION ALGORITHM BASED ...

引用

2nd IEEE International Conference on Cloud Computing and Intelligent Systems (CCIS)

作者： Wang, Bosheng Xu, Jiaqi Beijing Univ Posts & Telecommun Multimedia Commun & Pattern Recognit Labs Beijing 100876 Peoples R China

ISBN: (纸本)9781467318556;9781467318570

Segmentation of the hand from an image is a necessary step for many applications e.g. hand tracking, gesture recognition. One of the major problems is the hand-forearm segmentation. We propose mathematic model based on geometrical features of silhouette shape to address this problem. Then an accurate and effective approximation algorithm is proposed to obtain the solution of the model. Finally a complete hand segmentation algorithm is realized by using the Kinect sensor. The experiment result proves that our algorithm is accurate and fast.

关键词： Hand-forearm segmentation Mathematic model Geometrical features approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Distributed algorithm for Set k-Cover Problem and its Worst Case Analysis

Distributed Algorithm for Set <i>k</i>-Cover Problem and its...

引用

3rd International Conference on Networking and Computing (ICNC)

作者： Fujita, Satoshi Hiroshima Univ Dept Informat Engn Higashihiroshima 7398527 Japan

ISBN: (纸本)9780769548937;9781467346245

In this paper, we consider the problem of partitioning a given collection of subsets of nodes into.. collections such that the average size of each collection is the largest, where the size of a collection is defined as the size of the union of the subsets contained in the collection. At first, we give an upper bound on the performance ratio of Abrams et al.'s approximation algorithm which is known to have a performance ratio of at least 1 - 1/e where e is Napier's constant. The result of numerical calculations indicates that an upper bound is 3/4 + epsilon for small epsilon > 0. Next, we design a distributed implementation of Abrams et al.'s algorithm, which is based on the idea of arbitration using a spanning tree. Our algorithm can be used for the periodical switching of active subsets in Wireless Sensor Networks.

关键词： Set k-cover problem approximation algorithm performance ratio distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Constrained surface-level gateway placement for underwater acoustic wireless sensor networks

Constrained surface-level gateway placement for underwater a...

引用

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

作者： Li, Deying Li, Zheng Ma, Wenkai Chen, Hong Chen, Wenping Renmin Univ China MOE Key Lab Data Engn & Knowledge Engn Beijing Peoples R China Renmin Univ China Sch Informat Beijing 100872 Peoples R China

One approach to guarantee the performance of underwater acoustic sensor networks is to deploy multiple Surface-level Gateways (SGs) at the surface. This paper addresses the connected (or survivable) Constrained Surface-level Gateway Placement (C-SGP) problem for 3-D underwater acoustic sensor networks. Given a set of underwater sensor nodes (USNs) which are floated at different depths to perform collaborative monitoring tasks over a given region, and a set of candidate locations where SGs may be placed, our objective is to place minimum number of SGs at a subset of candidate locations such that it is connected (or k-connected) from any USN to the base station. We first propose a general algorithm for the connected C-SGP problem and prove its approximation ratio. We also give a constant ratio approximation algorithm for the problem. Second, for the survivable C-SGP problem we also propose a general algorithm and prove its approximation ratio. Finally, we give a constant ratio approximation algorithm for the 2-connected C-SGP problem. (c) 2011 Elsevier B.V. All rights reserved.

关键词： Underwater sensor networks Surface-level gateway placement Connectivity Survivability approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximate algorithms for Survivable Network Design

Approximate Algorithms for Survivable Network Design

引用

3rd International Conference on Networking and Computing (ICNC)

作者： Shen, Hong Univ Adelaide Sch Comp Sci Adelaide SA 5005 Australia

ISBN: (纸本)9780769548937;9781467346245

Along with the rapid development of network communication technology and the explosive growth of the internet applications, network reliability appears increasingly important to both traditional areas such as defense, finance and power industry, and emerging areas such as trusted computing, cloud computing and next-generation Internet. An interesting subject that has attracted great effort is how to design network topologies with a minimum network resource usage in terms of cost that provides a relibility guarantee. As problems on this subject, like most other network optimization problems, are well-known NP-hard even in their simplest form, design of effective solutions with a guaranteed approximation ratio from the optimal solution has been a major research focus of great significance for both theory and applications. This survery summarizes major existing techniques and results for solving some central problems in designing survivable networks including the minimal connected subgraph problem, the survivable network design problem and the Steiner minimal network problem.

关键词： approximation algorithm survivable network design Steiner minimal network connected spanning subgraph terminal spanning-tree disjoint path pair Euler walk

来源：评论

学校读者我要写书评

暂无评论

Energy Aware Scheduling for Unrelated Parallel Machines

Energy Aware Scheduling for Unrelated Parallel Machines

引用

IEEE/ACM International Conference on Green Computing and Communications (GreenCom) / IEEE International Conference on Internet of Things (iThings) / 5th IEEE International Conference on Cyber, Physical and Social Computing (CPSCom)

作者： Angel, Eric Bampis, Evripidis Kacem, Fadi Univ Evry Val dEssonne IBISC F-91025 Evry France UPMC CNRS LIP6 F-75005 Paris France

ISBN: (纸本)9780769548654;9781467351461

We consider the problem of energy aware scheduling of a set of jobs on a set of unrelated parallel machines with the average weighted completion time plus energy objective. The processing time and the energy consumption of the jobs are machine and speed dependent. Also, every job is subject to a machine-dependent release date. Firstly, we aim to find a non-preemptive schedule of the jobs minimizing the average weighted completion time plus energy, and we propose a randomized approximation algorithm that we derandomize obtaining a deterministic approximation algorithm. We then consider the budget variant of the problem where the objective is to minimize the average completion time while the total energy consumption does not exceed a given budget.

关键词： scheduling unrelated machines weighted completion time energy consumption randomization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Two Connected Dominating Set algorithms for Wireless Sensor Networks

Two Connected Dominating Set Algorithms for Wireless Sensor ...

引用

7th International Conference on Wireless algorithms, Systems, and Applications (WASA)

作者： Al-Nabhan, Najla Zhang, Bowu Al-Rodhaan, Mznah Al-Dhelaan, Abdullah King Saud Univ Dept Comp Sci Riyadh Saudi Arabia George Washington Univ Dept Comp Sci Washington DC 20052 USA

ISBN: (纸本)9783642318696

In this work, we present the design of two novel algorithms for constructing connected dominating set (CDS) in wireless sensor networks (WSNs). Both algorithms are intended to minimize CDS size. The first algorithm has a performance factor of 5 from the optimal solution, which outperforms the best-published results (5.8+ ln 4) in [1]. The second algorithm is an improved version of the first one. We included the theoretical analysis and simulation results showing the effectiveness of both algorithms.

关键词： Connected Dominating Set Wireless Sensor Networks Maximal Independent Set Unit Disk Graph approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Scheduling Problem for Parallel Machines with Limited Processing Capacities

Scheduling Problem for Parallel Machines with Limited Proces...

引用

International Conference on Advanced Research on Advanced Structure, Materials and Engineering (ASME 2011)

作者： Fan, Jing Shanghai Second Polytech Univ Sch Sci Shanghai 201209 Peoples R China

ISBN: (纸本)9783037852996

In the actual industrial engineering, machines used for processing need to be checked periodically to ensure that they can work efficiently. Thus, the novel scheduling problem for parallel machines with limited capacities is worth to study. The objective function is to maximize the last completion time of jobs. We show the problem is NP-hard at least. Furthermore, two approximation algorithms are presented, and algorithms' performances are considered through the experiments with large amounts of data.

关键词： industrial engineering scheduling problem parallel machine NP-hard approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：