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

20th International Symposium on algorithms and Computations (ISAAC 2009)

作者： Xu, Zhou Xu, Liang Hong Kong Polytech Univ Dept Logist & Maritime Studies Fac Business Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9783642106309

This paper presents improved approximation algorithms and inapproximability results for min-max path cover problems with service handling time, which have wide applications in practice when the latest service completion time for customers is critical. We study three variants of this problem, where paths must start (i) from a given depot, (ii) from any depot of a given set, and (iii) from any vertex of the given graph, respectively. For these three variants, we are able to achieve approximation ratios of 3, (4 + epsilon), and (5 + epsilon), respectively, for any epsilon > 0. We have further shown that;approximation ratios less than 4/3, 3/2, and 3/2 are impossible for them, respectively, unless NP = P.

关键词： approximation algorithm inapproximability min-max vehicle routing path covers

来源：评论

学校读者我要写书评

暂无评论

THE VPN PROBLEM WITH CONCAVE COSTS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2010年第3期24卷 1080-1090页

作者： Fiorini, Samuel Oriolo, Gianpaolo Sanita, Laura Theis, Dirk Oliver Univ Libre Bruxelles Dept Math Brussels Belgium Univ Roma Tor Vergata Dipartimento Ing Impresa Rome Italy

Only recently Goyal, Olver, and Shepherd [Proc. STOC, ACM, New York, 2008] proved that the symmetric virtual private network design (sVPN) problem has the tree routing property, namely, that there always exists an optimal solution to the problem whose support is a tree. Combining this with previous results by Fingerhut, Suri, and Turner [J. algorithms, 24 (1997), pp. 287-309] and Gupta et al. [Proc. STOC, ACM, New York, 2001], sVPN can be solved in polynomial time. In this paper we investigate an APX-hard generalization of sVPN, where the contribution of each edge to the total cost is proportional to some non-negative, concave, and nondecreasing function of the capacity reservation. We show that the tree routing property extends to the new problem and give a constant-factor approximation algorithm for it. We also show that the undirected uncapacitated single-source minimum concave-cost flow problem has the tree routing property when the cost function has some property of symmetry.

关键词： network design routing problem approximation algorithm concave cost

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms on Multiprocessor Task Scheduling

Approximation Algorithms on Multiprocessor Task Scheduling

引用

International Conference on Computer Engineering and Technology

作者： Huang Jingui Li Rongheng Hunan Normal Univ Dept Comp Educ Changsha Hunan Peoples R China Hunan Normal Univ Coll Math & Comp Sci Changsha Peoples R China

ISBN: (纸本)9780769535210

Multiprocessor task scheduling problem has become increasingly interesting, for both theoretical study and practical applications. Theoretical study of the problem has made significant progress recently. However, it seems not to imply practical algorithms for the problem yet. In this paper, the offline version of the Multiprocessor scheduling problem on m-processor system is discussed for the case of not only the unit process time tasks but also the arbitrary processing time tasks. Some approximation algorithms are proposed by using the Split Scheduling, the First Fit and the Large Width First techniques. The approximation ratios here are better than the best results existed in the current literature.

关键词： Multiprocessor task scheduling approximation algorithm NP-hard problem

来源：评论

学校读者我要写书评

暂无评论

Parallel machine scheduling with nested processing set restrictions

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第2期204卷 229-236页

作者： Huo, Yumei Leung, Joseph Y-T New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA CUNY Dept Comp Sci Staten Isl NY 10314 USA

We consider the problem of scheduling a set of n independent jobs on in parallel machines, where each job can only be scheduled on a subset of machines called its processing set. The machines are linearly ordered, and the processing set of job j is given by two machine indexes a(j) and b(j);i.e., job j can only be scheduled on machines a(j), a(j) + 1, ... , b(j). Two distinct processing sets are either nested or disjoint. Preemption is not allowed. Our goal is to minimize the makespan. It is known that the problem is strongly NP-hard and that there is a list-type algorithm with a worst-case bound of 2 - 1/m. In this paper we give an improved algorithm with a worst-case bound of 7/4. For two and three machines, the algorithm gives a better worst-case bound of 5/4 and 3/2, respectively. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Nested processing set restrictions Nonpreemptive scheduling Makespan NP-hard approximation algorithm Worst-case bound

来源：评论

学校读者我要写书评

暂无评论

GENERALIZED WATCHMAN ROUTE PROBLEM WITH DISCRETE VIEW COST

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2010年第2期20卷 119-146页

作者： Wang, Pengpeng Krishnamurti, Ramesh Gupta, Kamal Simon Fraser Univ Sch Engn Sci Robot Algorithms & Mot Planning Lab Burnaby BC V5A 1S6 Canada Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada

In this paper, we introduce a generalized version of the Watchman Route Problem (WRP) where the objective is to plan a continuous closed route in a polygon (possibly with holes) and a set of discrete viewpoints on the planned route such that every point on the polygon boundary is visible from at least one viewpoint. Each planned viewpoint has some associated cost. The total cost to minimize is a weighted sum of the view cost, proportional to the number of viewpoints, and the travel cost, the total length of the route. We call this problem the Generalized Watchman Route Problem or the GWRP. We tackle a restricted nontrivial (it remains NP-hard and log-inapproximable) version of GWRP where each polygon edge is entirely visible from at least one planned viewpoint. We call it Whole Edge Covering GWRP. The algorithm we propose first constructs a graph that connects O(n(12)) number of sample viewpoints in the polygon, where n is the number of polygon vertices;and then solves the corresponding View Planning Problem with Combined View and Traveling Cost, using an LP-relaxation based algorithm we introduced in [27, 29]. We show that our algorithm has an approximation ratio in the order of either the view frequency, defined as the maximum number of sample viewpoints that cover a polygon edge, or a polynomial of log n, whichever is smaller.

关键词： Watchman route problem art gallery problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Interference and power constrained broadcast and multicast routing in wireless ad hoc networks using directional antennas

引用

COMPUTER COMMUNICATIONS 2010年第12期33卷 1428-1439页

作者： Li, Zheng Li, Deying Liu, Ming Renmin Univ China Sch Informat Beijing 100872 Peoples R China Renmin Univ China Key Lab Data Engn & Knowledge Engn MOE Beijing 100872 Peoples R China Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Peoples R China

In this paper, we address the interference and power constrained broadcast/multicast routing problem (D-IPCB/M) in wireless ad hoc networks using directional antenna as a starting point, which jointly considers low-interference and energy-efficiency issues. Then we study the delay-bounded interference and power constrained broadcast/multicast routing problem (DB-D-IPCB/M). An approximation algorithm and a heuristic algorithm with low time complexity are proposed for the D-IPCB/M and DB-D-IPCB/M problem, respectively. Finally, we explore and investigate the multi-constrained subgraph optimization (MCSO) problem. We prove its NP-hard and propose an approximation scheme with theoretical performance guarantee for this class of optimization problems. This is a general result originated from the study of D-IPCB/M and DB-D-IPCB/M problems, which can be applicable to solve different optimization problems such as the multi-constrained broadcast/multicast routing problems. Broadcast/multicast message by using the routing trees found by our algorithms tends to not only have less channel collisions but also save energy to extend network lifetime. The theoretical results are evaluated by simulation studies. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Wireless ad hoc network Energy-efficient Interference Broadcast/multicast approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Shortest Average Routing Path-Based d-hop Clustering in Wireless Sensor Networks

Shortest Average Routing Path-Based d-hop Clustering in Wire...

引用

3rd IEEE International Conference on Computer Science and Information Technology (ICCSIT)

作者： Jiang, Ailian Wu, Weili Xie, Keming Kim, Donghyun Wang, Wei Taiyuan Univ Technol Dept Comp Sci & Technol Taiyuan Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75083 USA Xi An Jiao Tong Univ Dept Math Xian Peoples R China

ISBN: (纸本)9781424455379

In the paper, we propose a new d-hop Clustering method for a clustering-based multi-hop routing scheme in large-scale wireless sensor network. d-hop clustering means that each cluster contains all nodes that are at distance at most d-hops from the clusterhead, so that the number of clusters can be getting smaller to make it possible to guarantee the combined system performances including end-to-end delay and throughput. To determine the clusterheads, we give the constraint of minimizing the expected average hop distance from a node to its neatest sink in order to minimize the energy consumption for data forwarding in the clustering-based routing scheme. To deal with the high complexity of the problem, we relax it to a special form of Minimum Weighte d-hop Dominating Set Problem(MW dDSP), Then we present two approximation algorithms and corresponding analyses for it. One is a greedy algorithm with approximation ratio), another achieves a constant factor performance ratio.

关键词： d-hop clustering clustring-based routing approximation algorithm wireless sensor network

来源：评论

学校读者我要写书评

暂无评论

Structural Identifiability in Low-Rank Matrix Factorization

引用

algorithmICA 2010年第3期56卷 313-332页

作者： Fritzilas, Epameinondas Milanic, Martin Rahmann, Sven Rios-Solis, Yasmin A. Univ Bielefeld Fac Technol Bielefeld Germany Univ Primorska Fac Math Nat Sci & Informat Technol Koper Slovenia Tech Univ Dortmund Dortmund Germany UANL Grad Program Syst Engn Monterrey Mexico

In many signal processing and data mining applications, we need to approximate a given matrix Y with a low-rank product Ya parts per thousand AX. Both matrices A and X are to be determined, but we assume that from the specifics of the application we have an important piece of a-priori knowledge: A must have zeros at certain positions. In general, different AX factorizations approximate a given Y equally well, so a fundamental question is whether the known zero pattern of A contributes to the uniqueness of the factorization. Using the notion of structural rank, we present a combinatorial characterization of uniqueness up to diagonal scaling (subject to a mild non-degeneracy condition on the factors), called structural identifiability of the model. Next, we define an optimization problem that arises in the need for efficient experimental design. In this context, Y contains sensor measurements over several time samples, X contains source signals over time samples and A contains the source-sensor mixing coefficients. Our task is to monitor the signal sources with the cheapest subset of sensors, while maintaining structural identifiability. Firstly, we show that this problem is NP-hard. Secondly, we present a mixed integer linear program for its exact solution together with two practical incremental approaches. We also propose a greedy approximation algorithm. Finally, we perform computational experiments on simulated problem instances of various sizes.

关键词： Low-rank matrix factorization Structural rank Bipartite matching Computational complexity Integer programming approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Lower-Bounded Facility Location

引用

ACM TRANSACTIONS ON algorithmS 2010年第4期6卷 1–16页

作者： Svitkina, Zoya Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

We study the lower-bounded facility location problem which generalizes the classical uncapacitated facility location problem in that it comes with lower bound constraints for the number of clients assigned to a facility in the case that this facility is opened. This problem was introduced independently in the papers by Karger and Minkoff [2000] and by Guha et al. [2000], both of which give bicriteria approximation algorithms for it. These bicriteria algorithms come within a constant factor of the optimal solution cost, but they also violate the lower bound constraints by a constant factor. Our result in this article is the first true approximation algorithm for the lower-bounded facility location problem which respects the lower bound constraints and achieves a constant approximation ratio for the objective function. The main technical idea for the design of the algorithm is a reduction to the capacitated facility location problem, which has known constant-factor approximation algorithms.

关键词： approximation algorithm facility location

来源：评论

学校读者我要写书评

暂无评论

Efficient approximation algorithms for shortest cycles in undirected graphs

引用

INFORMATION PROCESSING LETTERS 2009年第10期109卷 493-498页

作者： Lingas, Andrzej Lundell, Eva-Marta Lund Univ Dept Comp Sci S-22100 Lund Sweden

We describe a simple combinatorial approximation algorithm for finding a shortest (simple) cycle in an undirected graph. Given an adjacency-list representation of an undirected graph G with n vertices and unknown girth k, our algorithm returns with high probability a cycle of length at most 2k for even k and 2k + 2 for odd k, in time O(n(3/2) root log n). Thus, in general, it yields a 2 2/3 approximation. For a weighted, undirected graph, with non-negative edge weights in the range {1,2,...,M}, we present a simple combinatorial 2-approximation algorithm for a minimum weight (simple) cycle that runs in time O(n(2) log n(log n + log M)). (C) 2009 Elsevier B.V. All rights reserved.

关键词： Graph algorithm approximation algorithm Shortest cycle Undirected graph Time complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：