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

approximation algorithms for Minimizing Edge Crossings in Radial Drawings

algorithmICA 2010年第2期58卷 478-497页

作者： Hong, Seok-Hee Nagamochi, Hiroshi Kyoto Univ Dept Appl Math & Phys Kyoto 606 Japan Univ Sydney Sch Informat Technol Sydney NSW 2006 Australia

We study a crossing minimization problem of drawing a bipartite graph with a radial drawing of two orbits. Radial drawings are one of well-known drawing conventions in social network analysis and visualization, in particular, displaying centrality indices of actors (Wasserman and Faust, Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge, 1994). The main problem in this paper is called the one-sided radial crossing minimization, if the positions of vertices in the outer orbit are fixed. The problem is known to be NP-hard (Bachmaier, IEEE Trans. Vis. Comput. Graph. 13, 583-594, 2007), and a number of heuristics are available (Bachmaier, IEEE Trans. Vis. Comput. Graph. 13, 583-594, 2007). However, there is no approximation algorithm for the crossing minimization problem in radial drawings. We present the first polynomial time constant-factor approximation algorithm for the one-sided radial crossing minimization problem.

关键词： Graph drawing Layered drawing Level drawing Hierarchical drawing Radial drawing Crossing minimization approximation algorithm Graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximating Fixation Probabilities in the Generalized Moran Process 12

Approximating Fixation Probabilities in the Generalized Mora...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Josep Diaz Leslie Ann Goldberg George B. Mertzios David Richerby Maria Serna Paul G. Spirakis Departament de Llenguatges i Sistemes Informatics Universitat Politecnica de Catalunya Department of Computer Science University of Liverpool School of Engineering and Computing Sciences Durham University Department of Computer Engineering and Informatics University of Patras

ISBN: (纸本)9781611972108

We consider the Moran process, as generalized by Lieberman, Hauert and Nowak (Nature, 433:312-316, 2005). A population resides on the vertices of a finite, connected, undirected graph and, at each time step, an individual is chosen at random with probability proportional to its assigned "fitness" value. It reproduces, placing a copy of itself on a neighbouring vertex chosen uniformly at random, replacing the individual that was there. The initial population consists of a single mutant of fitness r ＞ 0 placed uniformly at random, with every other vertex occupied by an individual of fitness 1. The main quantities of interest are the probabilities that the descendants of the initial mutant come to occupy the whole graph (fixation) and that they die out (extinction); almost surely, these are the only possibilities. In general, exact computation of these quantities by standard Markov chain techniques requires solving a system of linear equations of size exponential in the order of the graph so is not feasible. We show that, with high probability, the number of steps needed to reach fixation or extinction is bounded by a polynomial in the number of vertices in the graph. This bound allows us to construct fully polynomial randomized approximation schemes (FPRAS) for the probability of fixation (when r ＞ 1) and of extinction (for all r ＞ 0).

关键词： Evolutionary dynamics Markov-chain Monte Carlo approximation algorithm approximation algorithms Probability Fixation fixation Markov chain monte carlo methods vertex head Random Linear system of equations Polynomial Line graph Markov chain

来源：评论

学校读者我要写书评

暂无评论

approximation algorithmS FOR MULTICOMMODITY FACILITY LOCATION PROBLEMS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2010年第2期24卷 538-551页

作者： Ravi, R. Sinha, Amitabh Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA Univ Michigan Ross Sch Business Ann Arbor MI 48109 USA

Multicommodity facility location refers to the extension of facility location to allow for different clients' demands for different goods from among a finite set of goods. This leads to several optimization problems, depending on the cost of opening a facility (now a function of the commodities it serves). In this paper, we introduce and provide approximation algorithms for two fairly general versions of multicommodity facility location. We formulate integer programming models for these problems, and use them to provide approximation algorithms for the problems that are close to the inapproximability thresholds.

关键词： facility location approximation algorithm LP rounding

来源：评论

学校读者我要写书评

暂无评论

A CONSTANT FACTOR approximation FOR MINIMUM λ-EDGE-CONNECTED k-SUBGRAPH WITH METRIC COSTS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2011年第3期25卷 1089-1102页

作者： Safari, Mohammadali Salavatipour, Mohammad R. Sharif Univ Technol Dept Comp Engn Tehran Iran Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

In the (k, lambda)-subgraph problem, we are given an undirected graph G = (V, E) with edge costs and two positive integers k and., and the goal is to find a minimum cost simple.-edge-connected subgraph of G with at least k nodes. This generalizes several classical problems, such as the minimum cost k-spanning tree problem, or k-MST (which is a (k, 1)-subgraph), and the minimum cost lambda-edge-connected spanning subgraph (which is a (vertical bar V(G)vertical bar, lambda)-subgraph). The only previously known results on this problem [L. C. Lau, J. S. Naor, M. R. Salavatipour, and M. Singh, SIAM J. Comput., 39 (2009), pp. 1062-1087], [C. Chekuri and N. Korula, in Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Bangalore, India, LIPIcs 2, Schloss Dagstuhl-Leibniz-Zentrum fur Informatik, Dagstuhl, Germany, 2008, pp. 119-130] show that the (k, 2)-subgraph problem has an O(log(2) n)-approximation (even for 2-node-connectivity) and that the (k, lambda)-subgraph problem in general is almost as hard as the densest k-subgraph problem. In this paper we show that if the edge costs are metric (i.e., satisfy the triangle inequality), like in the k-MST problem, then there is an O(1)-approximation algorithm for the (k, lambda)-subgraph problem. This essentially generalizes the k-MST constant factor approximability to higher connectivity.

关键词： approximation algorithm lambda-edge-connectivity k-subgraph metric cost

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for minimum broadcast schedule problem in wireless sensor networks

引用

中国高等学校学术文摘·数学 2010年第1期5卷 75-87页

作者： Weiping SHANG Pengjun WAN Xiaodong HU Department Of Mathematics Zhengzhou University Zhengzhou 450052 China Department of Computer Science Illinois Institute of Technology Chicago IL 60616 USA Institute of Applied Mathematics Chinese Academy of Sciences Beijing 100190 China

A wireless sensor network usually consists of a large number of sensor nodes deployed in a field. One of the major communication operations is to broadcast a message from one node to the rest of the others. In this paper, we adopt the conflict-free communication model and study how to compute a transmission schedule that determines when and where a node should forward the message so that all nodes could receive the message in minimum time. We give two approximation algorithms for this NP-hard problem that have better theoretically guaranteed performances than the existing algorithms. The proposed approach could be applied to some other similar problems.

关键词： broadcast schedule approximation algorithm wireless sensor network unit disk graph

来源：评论

学校读者我要写书评

暂无评论

Tighter approximation Bounds for Minimum CDS in Unit Disk Graphs

引用

algorithmICA 2011年第4期61卷 1000-1021页

作者： Li, Minming Wan, Peng-Jun Yao, Frances City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China IIT Dept Comp Sci Chicago IL 60616 USA

Connected dominating set (CDS) in unit disk graphs has a wide range of applications in wireless ad hoc networks. A number of approximation algorithms for constructing a small CDS in unit disk graphs have been proposed in the literature. The majority of these algorithms follow a general two-phased approach. The first phase constructs a dominating set, and the second phase selects additional nodes to interconnect the nodes in the dominating set. In the performance analyses of these two-phased algorithms, the relation between the independence number alpha and the connected domination number gamma (c) of a unit-disk graph plays the key role. The best-known relation between them is alpha <= 32/3 gamma(c) + 1. In this paper, we prove that alpha <= 3.4306 gamma(c) +4.8185. This relation leads to tighter upper bounds on the approximation ratios of two approximation algorithms proposed in the literature.

关键词： Wireless ad hoc networks Connected dominating set approximation algorithm Geometric analysis

来源：评论

学校读者我要写书评

暂无评论

Game-theoretic Resource Allocation for Malicious Packet Detection in Computer Networks 12

Game-theoretic Resource Allocation for Malicious Packet Dete...

引用

International Conference on Autonomous Agents and Multiagent Systems

作者： Ondrej Vaneky Zhengyu Yin Manish Jain Branislav Bosansky Milind Tambe Michal Pechoucek Faculty of Electrical Engineering Czech Technical University Computer Science Department University of Southern California

ISBN: (纸本)9781627481564

We study the problem of optimal resource allocation for packet selection and inspection to detect potential threats in large computer networks with multiple computers of differing importance. An attacker tries to harm these targets by sending malicious packets from multiple entry points of the network; the defender thus needs to optimally allocate her resources to maximize the probability of malicious packet detection under network latency constraints. We formulate the problem as a graph-based security game with multiple resources of heterogeneous capabilities and propose a mathematical program for finding optimal solutions. We also propose Grande, a novel polynomial time algorithm that uses an approximated utility function to circumvent the limited scalability caused by the attacker's large strategy space and the non-linearity of the aforementioned mathematical program. Grande computes solutions with bounded error and scales up to problems of realistic sizes.

关键词： Computer networks Security Game-theory approximation algorithm Submodularity Resource utilization computer network Packet multicomputer management of resources optimal solution nonlinearity network delay

来源：评论

学校读者我要写书评

暂无评论

THE TRAVELING SALESMAN PROBLEM FOR LINES AND RAYS IN THE PLANE

引用

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2012年第4期4卷

作者： Dumitrescu, Adrian Univ Wisconsin Dept Comp Sci Milwaukee WI 53201 USA

In the Euclidean TSP with neighborhoods (TSPN), we are given a collection of n regions (neighborhoods) and we seek a shortest tour that visits each region. In the path variant, we seek a shortest path that visits each region. We present several linear-time approximation algorithms with improved ratios for these problems for two cases of neighborhoods that are (infinite) lines, and respectively, (half-infinite) rays. Along the way we derive a tight bound on the minimum perimeter of a rectangle enclosing an open curve of length L.

关键词： Traveling salesman problem with neighborhoods linear programming minimum-perimeter rectangle approximation algorithm lines rays

来源：评论

学校读者我要写书评

暂无评论

Improved approximation for Guarding Simple Galleries from the Perimeter

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2011年第2期46卷 252-269页

作者： King, James Kirkpatrick, David McGill Univ Sch Comp Sci Montreal PQ Canada Univ British Columbia Dept Comp Sci Vancouver BC V6T 1W5 Canada

We provide an O(log log OPT)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for building epsilon-nets of size O(1/epsilon log log 1/epsilon) for the instances of HITTING SET associated with our guarding problem. We then apply the technique of Bronnimann and Goodrich to build an approximation algorithm from this e-net finder. Along with a simple polygon P, our algorithm takes as input a finite set of potential guard locations that must include the polygon's vertices. If a finite set of potential guard locations is not specified, e. g., when guards may be placed anywhere on the perimeter, we use a known discretization technique at the cost of making the algorithm's running time potentially linear in the ratio between the longest and shortest distances between vertices. Our algorithm is the first to improve upon O(log OPT)-approximation algorithms that use generic net finders for set systems of finite VC-dimension.

关键词： Art gallery problem Polygon guarding approximation algorithm Epsilon-nets Perimeter guards Vertex guards

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for the minimum rainbow subgraph problem

引用

DISCRETE MATHEMATICS 2010年第20期310卷 2666-2670页

作者： Camacho, Stephan Matos Schiermeyer, Ingo Tuza, Zsolt Tech Univ Bergakad Freiberg Inst Diskrete Math & Algebra D-09596 Freiberg Germany Hungarian Acad Sci Comp & Automat Res Inst Budapest Hungary Univ Pannonia Dept Comp Sci Veszprem Hungary

We consider the minimum rainbow subgraph problem (MRS): given a graph G, whose edges are coloured with p colours. Find a subgraph F subset of G of G of minimum order and with p edges such that each colour occurs exactly once. For graphs with maximum degree Delta(G) there is a greedy polynomial-time approximation algorithm for the MRS problem with an approximation ratio of Delta(G). In this paper we present a polynomial-time approximation algorithm with an approximation ratio of 5/6 Delta for Delta >= 2. (c) 2010 Elsevier B.V. All rights reserved.

关键词： Edge colouring Minimum rainbow subgraph approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：