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

The minimum Manhattan network problem: approximations and exact solutions

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2006年第3期35卷 188-208页

作者： Benkert, Marc Wolff, Alexander Widmann, Florian Shirabe, Takeshi Univ Karlsruhe Dept Comp Sci D-76128 Karlsruhe Germany Vienna Tech Univ Inst Geoinformat A-1040 Vienna Austria

Given a set of points in the plane and a constant t >= 1, a Euclidean t-spanner is a network in which, for any pair of points, the ratio of the network distance and the Euclidean distance of the two points is at most t. Such networks have applications in transportation or communication network design and have been studied extensively. In this paper we study l-spanners under the Manhattan (or L-l-) metric. Such networks are called Manhattan networks. A Manhattan network for a set of points is a set of axis-parallel line segments whose union contains an x- and y-monotone path for each pair of points. It is not known whether it is NP-hard to compute minimum Manhattan networks (MMN), i.e., Manhattan networks of minimum total length. In this paper we present an approximation algorithm for this problem. Given a set P of n points, our algorithm computes in O(n log n) time and linear space a Manhattan network for P whose length is at most 3 times the length of an MMN of P. We also establish a mixed-integer programming formulation for the MMN problem. With its help we extensively investigate the performance of our factor-3 approximation algorithm on random point sets. (c) 2005 Elsevier B.V. All rights reserved.

关键词： spanners minimum Manhattan networks approximation algorithm mixed-integer programming

来源：评论

学校读者我要写书评

暂无评论

On the complexity of computing the capacity of codes that avoid forbidden difference patterns

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2006年第11期52卷 5122-5127页

作者： Blondel, Vincent D. Jungers, Raphael Protasov, Vladimir Univ Catholique Louvain Dept Engn Math B-1348 Louvain Belgium Moscow MV Lomonosov State Univ Dept Mech & Math Moscow 119992 Russia

Some questions related to the computation of the capacity of codes that avoid forbidden difference patterns are analysed. The maximal number of it-bit sequences whose pairwise differences do not contain some given forbidden difference patterns is known to increase exponentially with n;the coefficient of the exponent is the capacity of the forbidden patterns. In this paper, new inequalities for the capacity are given that allow for the approximation of the capacity with arbitrary high accuracy. The computational cost of the algorithm derived from these inequalities is fixed once the desired accuracy is given. Subsequently, a polynomial time algorithm is given for determining if the capacity of a set is positive while the same problem is shown to be NP-hard when the sets of forbidden patterns are defined over an extended set of symbols. Finally, the existence of extremal norms is proved for any set of matrices arising in the capacity computation. Based on this result, a second capacity approximating algorithm is proposed. The usefulness of this algorithm is illustrated by computing exactly the capacity of particular codes that were only known approximately.

关键词： approximation algorithm capacity of codes coding theory complexity of capacity joint spectral radius NP-hardness

来源：评论

学校读者我要写书评

暂无评论

On a minimum linear classification problem

引用

JOURNAL OF GLOBAL OPTIMIZATION 2006年第1期35卷 103-109页

作者： Lu, Bing Du, Hongwei Jia, Xiaohua Xu, Yinfeng Zhu, Binhai Univ Minnesota Dept Comp Sci & Engn Minneapolis MN 55455 USA City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Xian Jiaotong Univ Sch Management Xian 710049 Peoples R China Montana State Univ Dept Comp Sci Bozeman MT 59717 USA

We study the following linear classification problem in signal processing: Given a set Bof n black point and a set W of m white points in the plane (m = O(n)), compute a minimum number of lines L such that in the arrangement of L each face contain points with the same color (i.e., either all black points or all white points). We call this the Minimum Linear Classification (MLC) problem. We prove that MLC is NP-complete by a reduction from the Minimum Line Fitting (MLF) problem;moreover, a C-approximation to MLC implies a C-approximation to the MLF problem. Nevertheless, we obtain an O(log n)-factor algorithm for MLC and we also obtain an O(log Z)-factor algorithm for MLC where Z is the minimum number of disjoint axis-parallel black/white rectangles covering B and W.

关键词： approximation algorithm NP-complete sequence detection signal processing

来源：评论

学校读者我要写书评

暂无评论

Bin packing problems with rejection penalties and their dual problems

引用

INFORMATION AND COMPUTATION 2006年第5期204卷 795-815页

作者： Dosa, Gyorgy He, Yong Univ Veszprem Dept Math H-8201 Veszprem Hungary Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China

In this paper we consider the following problems: we are given a set or n items {u(1),., u(n)} and a number of unit-capacity bins. Each item u(i) has a size w(i) is an element of (0,1] and a penalty p(i)>= 0. An item can be either rejected, in which case we pay its penalty, or put into one bin under the constraint that the total size of the items in the bin is no greater than 1. No item can be spread into more than one bin. The objective is to minimize the total number of used bins plus the total penalty paid for the rejected items. We call the problem bin packing with rejection penalties, and denote it as BPR. For the on-line BPR problem, we present an algorithm with an absolute competitive ratio of 2.618 while the lower bound is 2.343, and an algorithm with an asymptotic competitive ratio arbitrarily close to 1.75 while the lower bound is 1.540. For the off-line BPR problem, we present an algorithm with an absolute worst-case ratio of 2 while the lower bound is 1.5, and an algorithm with an asymptotic worst-case ratio of 1.5. We also study a closely related bin covering version of the problem. In this case pi means some amount of profit. If an item is rejected, we get its profit, or it can be put into a bin in such a way that the total size of the items in the bin is no smaller than 1. The objective is to maximize the number of covered bins plus the total profit of all rejected items. We call this problem bin covering with rejection (BCR). For the on-line BCR problem, we show that no algorithm can have absolute competitive ratio greater than 0, and present an algorithm with asymptotic competitive ratio 1/2, which is the best possible. For the off-line BCR problem, we also present an algorithm with an absolute worst-case ratio of 1/2 which matches the lower bound. (C) 2006 Elsevier Inc. All rights reserved.

关键词： bin packing bin covering approximation algorithm on-line off-line

来源：评论

学校读者我要写书评

暂无评论

Augmenting forests to meet odd diameter requirements

引用

DISCRETE OPTIMIZATION 2006年第2期3卷 154-164页

作者： Ishii, Toshimasa Yamamoto, Shigeyuki Nagamochi, Hiroshi Toyohashi Univ Technol Dept Informat & Comp Sci Aichi 4418580 Japan I FOR COM Co Ltd Kanagawa 2200207 Japan Kyoto Univ Dept Appl Math & Phys Grad Sch Informat Kyoto 6068501 Japan

Given a graph G = (V, E) and an integer D >= 1, we consider the problem of augmenting G by the smallest number of new edges so that the diameter becomes at most D. It is known that no constant approximation algorithms to this problem with an arbitrary graph G can be obtained unless P = NP. For a forest G and an odd D >= 3, it was open whether the problem is approximable within a constant factor. In this paper, we give the first constant factor approximation algorithm to the problem with a forest G and an odd D;our algorithm delivers an 8-approximate solution in O(vertical bar V vertical bar(3)) time. We also show that a 4-approximate solution to the problem with a forest G and an odd D can be obtained in linear time if the augmented graph is additionally required to be biconnected. (c) 2006 Elsevier B.V. All rights reserved.

关键词： undirected graph graph augmentation problem diameter forest approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximate minimum-energy multicasting in wireless ad hoc networks

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2006年第4期5卷 377-387页

作者： Liang, WF Australian Natl Univ Dept Comp Sci Canberra ACT 0200 Australia

A wireless ad hoc network consists of mobile nodes that are equipped with energy-limited batteries. As mobile nodes are battery-operated, an important issue in such a network is to minimize the total power consumption for each operation. Multicast is one of fundamental operations in any modern telecommunication network including wireless ad hoc networks. Given a multicast request consisting of a source node and a set of destination nodes, the problem is to build a minimum-energy multicast tree for the request such that the total transmission power consumption in the tree is minimized. Since the problem in a symmetric wireless ad hoc network is NP-complete, we instead devise an approximation algorithm with provable approximation guarantee. The approximation of the solution delivered by the proposed algorithm is within a constant factor of the best-possible approximation achievable unless P = NP.

关键词： wireless communication network approximation algorithm power awareness ad hoc networks energy consumption optimization multicasting broadcasting minimum node-weighted Steiner tree problem

来源：评论

学校读者我要写书评

暂无评论

Minmax subtree cover problem on cacti

引用

DISCRETE APPLIED MATHEMATICS 2006年第8期154卷 1254-1263页

作者： Nagamochi, H Kawada, T Kyoto Univ Kyoto 6068501 Japan Toyohashi Univ Technol Dept Informat & Comp Sci Aichi 4418580 Japan

Let G = (V. E) be a connected graph such that edges and vertices are weighted by nonnegative reals. Let p be a positive integer. The minimax subtree cover problem (MSC) asks to find a pair (X, F) of a partition X = {X-1, X-2,....X-p} of V and a set F of p subtrees T-1, T-2,..., T-p, each T-i containing X-i so as to minimize the maximum Cost of the subtrees, where the cost of T-i is defined to be the sum of the weights of edges in T-i and the weights of vertices in Xi. In this paper. we propose an O(p(2)n) time (4 - 4/(p + 1))-approximation algorithm for the MSC when G is a cactus. (c) 2006 Elsevier B.V. All rights reserved.

关键词： approximation algorithm cactus graph partitions NP-hard tree vehicle routing

来源：评论

学校读者我要写书评

暂无评论

A network flow approach to the minimum common integer partition problem

引用

THEORETICAL COMPUTER SCIENCE 2006年第1-3期369卷 456-462页

作者： Zhao, Wenbo Zhang, Peng Jiang, Tao Chinese Acad Sci Inst Software Beijing 100080 Peoples R China Graad Univ Chinese Acad Sci Beijing Peoples R China Univ Calif Riverside Dept Comp Sci & Engn Riverside CA 92521 USA

In the k-Minimum Common Integer Partition Problem, abbreviated as k-MCIP, we are given k multisets X-1,..., X-k of positive integers, the goal is to find an integer multiset T of the minimum size such that for every i, we can partition each of the integers in Xi so that the disjoint (multiset) union of their partitions equals T. This problem has applications in computational molecular biology, in particular, ortholog assignment and DNA hybridization fingerprint assembly. The problem is known to be NP-hard for any k >= 2. In this article, we improve the approximation ratio for k-MCIP by viewing this problem as a flow decomposition problem in some flow network. We show an efficient 0.5625k-approximation algorithm, improving upon the previously best known 0.6139k-approximation algorithm for this problem. (c) 2006 Elsevier B.V. All rights reserved.

关键词： Minimum Common Integer Partition approximation algorithm network flow

来源：评论

学校读者我要写书评

暂无评论

Finding minimum hidden guard sets in polygons - tight approximability results

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2006年第2期34卷 49-57页

作者： Eidenbenz, S Los Alamos Natl Lab Discrete Simulat Sci Los Alamos NM 87545 USA

We study the problem MINIMUM HIDDEN GUARD SET, which consists of positioning a minimum number of guards in a given polygon (or other structure such as a terrain) such that no two guards see each other and such that every point in the polygon is visible from at least one guard. By constructing a gap-creating reduction from 5-OCCURENCE-3-SATISFIABILITY, we show that this problem cannot be approximated by any polynomial-time algorithm with an approximation ration of vertical bar I vertical bar(1-is an element of) for any is an element of > 0, unless NP = P, where vertical bar I vertical bar is the size of the input polygon. The result even holds for input polygons without holes, which separates the problem from other visibilty problems such as guarding and hiding, where strong inapproximability results hold only for polygons with holes. We also show that a straight-forward approximation algorithm achieves an approximation ratio of vertical bar I vertical bar. These two results characterize the approximability threshold of MINIMUM HIDDEN GUARD SET exactly up to low-order terms. (c) 2006 Elsevier B.V. All rights reserved.

关键词： hidden guard set inapproximability approximation algorithm visibility art gallery problems terrains polygons

来源：评论

学校读者我要写书评

暂无评论

An average-case analysis of online non-clairvoyant scheduling of independent parallel tasks

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2006年第5期66卷 617-625页

作者： Li, KQ SUNY Albany Dept Comp Sci New Paltz NY 12561 USA

We analyze the average-case performance of an online non-clairvoyant scheduling algorithm for independent parallel tasks. The algorithm schedules tasks without prior knowledge of the future tasks and the execution times of the tasks that are not yet completed. By using reasonable assumptions, we find an asymptotic average-case performance bound and develop a method to calculate the bound for arbitrary probability distribution of task sizes. In particular, we show that when task sizes are uniformly distributed in the range [1..C], an asymptotic average-case performance bound of [GRAPHICS] can be achieved, where M is the number of processors. The above asymptotic average-case performance bound achieves its maximum value when C = M, which is approximately 1/(e - 2) = 1.3922112 for large M. We also present extensive numerical and simulation data to demonstrate the accuracy of our analytical bound. (c) 2005 Elsevier Inc. All rights reserved.

关键词： approximation algorithm average-case performance ratio online non-clairvoyant scheduling parallel task probabilistic analysis simulation worst-case performance ratio

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：