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

19th Annual European Symposium on algorithms (ESA)

作者： Joret, Gwenael Paul, Christophe Sau, Ignasi Saurabh, Saket Thomasse, Stephan Univ Libre Bruxelles Dept Informat Brussels Belgium LIRMM CNRS AlGCo project team Montpellier France UCBL INRIA ENS Lyon Laboratoire LIPU LyonCNRS Madras Tamil Nadu India

ISBN: (纸本)9783642237195

The c-pumpkin is the graph with two vertices linked by c >= 1 parallel edges. A c-pumpkin-model in a graph G is a pair {A, B} of disjoint subsets of vertices of G, each inducing a connected subgraph of G, such that there are at least c edges in G between A and B. We focus on hitting and packing c-pumpkin-models in a given graph: On the one hand, we provide an FPT algorithm running in time 2(O(k))n(O(1)) deciding, for any fixed c >= 1, whether all c-pumpkin-models can be hit by at most k vertices. This generalizes the single-exponential FPT algorithms for VERTEX COVER and FEEDBACK VERTEX SET, which correspond to the cases c = 1, 2 respectively. For this, we use a combination of iterative compression and a kernelization-like technique. On the other hand, we present an O(log n)-approximation algorithm for both the problems of hitting all c-pumpkin-models with a smallest number of vertices, and packing a maximum number of vertex-disjoint c-pumpkin-models. Our main ingredient here is a combinatorial lemma saying that any properly reduced n-vertex graph has a c-pumpkin-model of size at most f(c) log n, for a function f depending only on c.

关键词： Hitting and packing parameterized complexity approximation algorithm single-exponential algorithm iterative compression graph minors

来源：评论

学校读者我要写书评

暂无评论

New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs

New approximations for minimum-weighted dominating sets and ...

引用

3rd International Conference on Combinatorial Optimization and Applications (COCOA 2009)

作者： Zou, Feng Wang, Yuexuan Xu, Xiao-Hua Li, Xianyue Du, Hongwei Wan, Pengjun Wu, Weili Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA Tsinghua Univ Inst Theoret Comp Sci Beijing 100084 Peoples R China IIT Dept Comp Sci Chicago IL 60616 USA Lanzhou Univ Sch Math & Stat Lanzhou 730000 Gansu Peoples R China

Given a node-weighted graph, the minimum-weighted dominating set (MWDS) problem is to find a minimum-weighted vertex subset such that, for any vertex, it is contained in this subset or it has a neighbor contained in this set. And the minimum-weighted connected dominating set (MWCDS) problem is to find a MWDS such that the graph induced by this subset is connected. In this paper, we study these two problems on a unit disk graph. A (4 +epsilon)-approximation algorithm for an MWDS based on a dynamic programming algorithm for a Min-Weight Chromatic Disk Cover is presented. Meanwhile, we also propose a (1 +epsilon)-approximation algorithm for the connecting part by showing a polynomial-time approximation scheme for a Node-Weighted Steiner Tree problem when the given terminal set is c-local and thus obtain a (5 +epsilon)-approximation algorithm for an MWCDS. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Minimum-weighted dominating set Minimum-weighted connected dominating set Minimum-weighted chromatic disk cover Node-weighted Steiner tree Polynomial-time approximation scheme approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes 11

Submodular Function Maximization via the Multilinear Relaxat...

引用

43rd ACM Symposium on Theory of Computing

作者： Chekuri, Chandra Vondrak, Jan Zenklusen, Rico Univ Illinois Dept Comp Sci Urbana IL 61801 USA

ISBN: (纸本)9781450306911

We consider the problem of maximizing a non-negative submodular set function f : 2(N) -> R+ over a ground set N subject to a variety of packing type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular when f may be a non-monotone function. Our algorithms are based on (approximately) solving the multilinear extension F of f [5] over a polytope P that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully in some settings [6, 22, 24, 13, 3], it has been limited in some important ways. We overcome these limitations as follows. First, we give constant factor approximation algorithms to maximize F over an arbitrary down-closed polytope P that has an efficient separation oracle. Previously this was known only for monotone functions [36]. For non-monotone functions, a constant factor was known only when the polytope was either the intersection of a fixed number of knapsack constraints [24] or a matroid polytope [37, 30]. Second, we show that contention resolution schemes are an effective way to round a fractional solution, even when f is non-monotone. In particular, contention resolution schemes for different polytopes can be combined to handle the intersection of different constraints. Via LP duality we show that a contention resolution scheme for a constraint is related to the correlation gap [1] of weighted rank functions of the constraint. This leads to an optimal contention resolution scheme for the matroid polytope. Our results provide a broadly applicable framework for maximizing linear and submodular functions subject to independence constraints. We give several illustrative examples. Contention resolution schemes may find other applications.

关键词： approximation algorithm submodular function maximization matroid contention resolution scheme independence constraint

来源：评论

学校读者我要写书评

暂无评论

Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems 1

引用

22nd International Symposium on algorithms and Computation (ISAAC)

作者： Yamakami, Tomoyuki Univ Fukui Dept Informat Sci Fukui 9108507 Japan

ISBN: (数字)9783642255915

ISBN: (纸本)9783642255908

We give a unified treatment to optimization problems that can be expressed in the form of nonnegative-real-weighted Boolean constraint satisfaction problems. Creignou, Khanna, Sudan, Trevisan, and Williamson studied the complexity of approximating their optimal solutions whose optimality is measured by the sums of outcomes of constraints. To explore a wider range of optimization constraint satisfaction problems, following an early work of Marchetti-Spaccamela and Romano, we study the case where the optimality is measured by products of constraints' outcomes. We completely classify those problems into three categories: PO problems, NPO-hard problems, and intermediate problems that lie between the former two categories. To prove this trichotomy theorem, we analyze characteristics of nonnegative-real-weighted constraints using a variant of the notion of T-constructibility developed earlier for complex-weighted counting constraint satisfaction problems.

关键词： optimization problem approximation algorithm constraint satisfaction problem PO APX approximation-preserving reducibility

来源：评论

学校读者我要写书评

暂无评论

An FPTAS for Flows over Time with Aggregate Arc Capacities

An FPTAS for Flows over Time with Aggregate Arc Capacities

引用

8th Workshop on approximation and Online algorithms

作者： Dressler, Daniel Skutella, Martin TU Berlin Inst Math D-10623 Berlin Germany

ISBN: (纸本)9783642183171

We study flows over time in networks with transit times on the arcs. Transit times describe how long it takes to traverse an arc. A flow over time specifies for each arc a time-dependent flow rate that must always be bounded by the arc's capacity. Only recently, Melkonian introduced an alternative model where so-called bridge capacities bound the total amount of flow traveling along an arc, at any point of time. The contribution of this paper is twofold. Firstly, we introduce a common generalization of both the classical flow over time model and Melkonian's model. Secondly, we present a non-trivial extension of an FPTAS by Fleischer and Skutella to our new flow model. Prior to this, no approximation algorithm was known for Melkonian's model.

关键词： network flow dynamic flow arc capacity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithmS FOR MINIMUM CONNECTED CAPACITATED DOMINATING SET PROBLEM

引用

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2011年第1期3卷 9-15页

作者： Shang, Weiping Wang, Xiumei Zhengzhou Univ Dept Math Zhengzhou 450001 Henan Peoples R China

Connected dominating set (CDS) has been proposed as the virtual backbone to alleviate the broadcasting storm in wireless sensor network. Most recent research has extensively focused on the construction of connected dominating set. However, the nodes in the CDS need to dominate all its neighbors, and then some nodes cover a large number of neighboring nodes. Therefore, it is desirable to construct a capacitated dominating set, each node can dominate only a certain number of neighbors. In this paper, we study capacitated dominating set and connected capacitated dominating set, and propose two approximation algorithms with small approximation ratios.

关键词： Capacitated dominating set approximation algorithm unit disk graph

来源：评论

学校读者我要写书评

暂无评论

DARP: Distance-Aware Relay Placement in WiMAX Mesh Networks

DARP: Distance-Aware Relay Placement in WiMAX Mesh Networks

引用

IEEE INFOCOM Conference

作者： Zhang, Weiyi Bai, Shi Xue, Guoliang Tang, Jian Wang, Chonggang North Dakota State Univ Dept Comp Sci Fargo ND 58105 USA Arizona State Univ Dept Comp Sci & Engn Tempe AZ 85287 USA Syracuse Univ Dept Elect Engn & Comp Sci Syracuse NY 13244 USA NEC Labs Amer Princeton NJ 08540 USA

ISBN: (纸本)9781424499212

The emerging WiMAX technology (IEEE 802.16) is the fourth generation standard for low-cost, high-speed and long-range wireless communications for a large variety of civilian and military applications. IEEE 802.16j has introduced the concept of mesh network model and a special type of node called Relay Station (RS) for traffic relay for Subscriber Stations (SSs). A WiMAX mesh network is able to provide larger wireless coverage, higher network capacity and Non-Line-Of-Sight (NLOS) communications. This paper studies a Distance-Aware Relay Placement (DARP) problem in WiMAX mesh networks, which considers a more realistic model that takes into account physical constraints such as channel capacity, signal strength and network topology, which were largely ignored in previous studies. The goal here is to deploy the minimum number of RSs to meet system requirements such as user data rate requests, signal quality and network topology. We divide the DARP problem into two sub-problems, LOwer-tier Relay Coverage (LORC) Problem and Minimum Upper-tier Steiner Tree (MUST) Problem. For LORC problem, we present two approximation algorithms based on independent set and hitting set, respectively. For MUST problem, an efficient approximation algorithm is provided and proved. Then, an approximation solution for DARP is proposed and proved which combines the solutions of the two sub-problems. We also present numerical results confirming the theoretical analysis of our schemes as the first solution for the DARP problem.

关键词： WiMAX mesh network relay station placement approximation algorithm hitting set independent set

来源：评论

学校读者我要写书评

暂无评论

Multiflows in Multi-Channel Multi-Radio Multihop Wireless Networks

Multiflows in Multi-Channel Multi-Radio Multihop Wireless Ne...

引用

IEEE INFOCOM Conference

作者： Wan, Peng-Jun Cheng, Yu Wang, Zhu Yao, Frances IIT Dept Comp Sci Chicago IL 60616 USA IIT Dept Elect & Comp Engn Chicago IL USA City Univ Hong Kong Dept Comp Sci Kowloon Peoples R China

ISBN: (纸本)9781424499212

This paper studies maximum multiflow (MMF) and maximum concurrent multiflow (MCMF) in muliti-channel multi-radio multihop wireless networks under the 802.11 interference model or the protocol interference model. We introduce a fine-grained network representation of multi-channel multi-radio multihop wireless networks and present some essential topological properties of its associated conflict graph. By exploiting these properties, we develop practical polynomial approximation algorithms for MMF and MCMF with constant approximation bounds regardless of the number of channels and radios. Under the 802.11 interference model, their approximation bounds are at most 20 in general and at most 8 with uniform interference radii;under the protocol interference model, if the interference radius of each node is at least.. times its communication radius, their approximation bounds are at most 2 (inverted right perpendicular pi/arcsin c-1/2c inverted left perpendicular + 1). In addition, we also prove that if the number of channels is bounded by a constant (which is typical in practical networks), both MMF and MCMF admit a polynomial-time approximation scheme under the 802.11 interference model or under the protocol interference model with some additional mild conditions.

关键词： Link scheduling multi-channel multi-radio maximum (concurrent) multiflow approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On Approximating the d-Girth of a Graph

On Approximating the <i>d</i>-Girth of a Graph

引用

37th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011

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

ISBN: (纸本)9783642183805

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 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. [13, 14] and Bollobas and Brightwell [7] over 20 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 [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.

关键词： generalized girth minimum degree approximation algorithm hardness of approximation randomized algorithm planar graph

来源：评论

学校读者我要写书评

暂无评论

Energy Efficient Monitoring in Sensor Networks

Energy Efficient Monitoring in Sensor Networks

引用

8th Latin American Theoretical Informatics International Conference

作者： Deshpande, Amol Khuller, Samir Malekian, Azarakhsh Toossi, Mohammed Univ Maryland Dept Comp Sci College Pk MD 20742 USA Google Mountain View CA USA

We study a set of problems related to efficient battery energy utilization for monitoring applications in a wireless sensor network with the goal to increase the sensor network lifetime. We study several generalizations of a basic problem called Set k-Cover. The problem can be described as follows: we are given a set of sensors, and a set of targets to be monitored. Each target can be monitored by a subset of the sensors. To increase the lifetime of the sensor network, we would like to partition the sensors into k sets (or time-slots), and activate each set of sensors in a different time-slot, thus extending the battery life of the sensors by a factor of k. The goal is to find a partitioning that maximizes the total coverage of the targets for a given k. This problem is known to be NP-hard. We develop an improved approximation algorithm for this problem using a reduction to Max k-Cut. Moreover, we are able to demonstrate that this algorithm is efficient, and yields almost optimal solutions in practice. We also consider generalizations of this problem in several different directions. First, we allow each sensor to be active in alpha different sets (time-slots). This means that the battery life is extended by a factor of k/alpha, and allows for a richer space of solutions. We also consider different coverage requirements, such as requiring that all targets, or at least a certain number of targets, be covered in each time slot. In the Set k-Cover formulation, there is no requirement that a target be monitored at all, or in any number of time slots. We develop a randomized rounding algorithm for this problem. We also consider extensions where each sensor can monitor only a bounded number of targets in any time-slot, and not all the targets adjacent to it. This kind of problem may arise when a sensor has a directional camera, or some other physical constraint might prevent it from monitoring all adjacent targets even when it is active. We develop the first approximation

关键词： algorithms Complexity approximation algorithm Sensor networks Energy efficiency Target monitoring

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：