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

Computing and counting longest paths on circular-arc graphs in polynomial time

Electronic Notes in Discrete Mathematics 2011年第C期37卷 219-224页

作者： Mertzios, George B. Bezáková, Ivona Caesarea Rothschild Institute for Computer Science University of Haifa Israel Department of Computer Science Rochester Institute of Technology NY United States

The longest path problem asks for a path with the largest number of vertices in a given graph. The first polynomial time algorithm (with running time O(n4)) has been recently developed for interval graphs. Even though... 详细信息

The longest path problem asks for a path with the largest number of vertices in a given graph. The first polynomial time algorithm (with running time O(n⁴)) has been recently developed for interval graphs. Even though interval and circular-arc graphs look superficially similar, they differ substantially, as circular-arc graphs are not perfect. In this paper, we prove that for every path P of a circular-arc graph G, we can appropriately "cut" the circle, such that the obtained (not induced) interval subgraph G' of G admits a path P' on the same vertices as P. This non-trivial result is of independent interest, as it suggests a generic reduction of a number of path problems on circular-arc graphs to the case of interval graphs with a multiplicative linear time overhead of O(n). As an application of this reduction, we present the first polynomial algorithm for the longest path problem on circular-arc graphs, which turns out to have the same running time O(n⁴) with the one on interval graphs, as we manage to get rid of the linear overhead of the reduction. This algorithm computes in the same time an n-approximation of the number of different vertex sets that provide a longest path;in the case where G is an interval graph, we compute the exact number. Moreover, our algorithm can be directly extended with the same running time to the case where every vertex has an arbitrary positive weight. © 2011 Elsevier B.V.

关键词： approximation algorithm Circular-arc graphs Counting Dynamic programming Interval graphs Longest path problem

来源：评论

学校读者我要写书评

暂无评论

The Routing Open Shop Problem: New approximation algorithms

The Routing Open Shop Problem: New Approximation Algorithms

引用

7th International Workshop on approximation and Online algorithms

作者： Chernykh, Ilya Dryuck, Nikita Kononov, Alexander Sevastyanov, Sergey Sobolev Inst Math Acad Koptyug Pr 4 Novosibirsk 630090 Russia Novosibirsk State Univ Novosibirsk 630090 Russia

ISBN: (纸本)9783642124495

We consider the routing open shop problem being a generalization of the open shop and the metric travelling salesman problems. The jobs are located at nodes of some transportation network, and the machines travel on the network to execute the jobs in the open shop environment. The machines are initially located at the same node (depot) and must return to the depot after completing all the jobs. It is required to find a non-preemptive schedule that minimizes the makespan. The problem is NP-hard even on a. two-node network with two machines. We present new polynomial-time approximation algorithms with worst-case performance guarantees.

关键词： Routing open shop approximation algorithm worst-case analysis

来源：评论

学校读者我要写书评

暂无评论

Experimental Study on approximation algorithms for Guarding Sets of Line Segments

引用

6th International Symposium on Visual Computing

作者： Brimkov, Valentin E. Leach, Andrew Mastroianni, Michael Wu, Jimmy SUNY Coll Buffalo Dept Math Buffalo NY 14222 USA Univ Buffalo Dept Math Buffalo NY 1426 USA

ISBN: (纸本)9783642172885

Consider any real structure that can he modeled by a set of straight line segments. This can be a network of streets in a city, tunnels in a mine, corridors in a building, pipes in a factory, etc. We want to approximate a minimal number of locations where to place "guards" (either men or machines), in a way that any point of the network can be "seen" by at least one guard. A guard can see all points on segments it is on (and nothing more). As the problem is known to be NP-hard, we consider three greedy-type algorithms for finding approximate solutions. We show that for each of these, theoretically the ratio of the approximate to the optimal solution can increase without bound with the increase of the number of segments. Nevertheless, our extensive experiments show that on randomly generated instances, the approximate solutions are always very close to the optimal ones and often are, in fact, optimal.

关键词： guarding set of segments art gallery problem approximation algorithm set cover vertex cover

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for min-max capacitated path covers 10

Approximation algorithms for min-max capacitated path covers

引用

Proceedings of the Sixteenth Symposium on Computing: the Australasian Theory - Volume 109

作者： Zhou Xu Liang Xu The Hong Kong Polytechnic University

ISBN: (纸本)9781920682903

This paper presents the first approximation algorithms and the first inapproximability results for min-max path cover problems where a capacity constraint restricts the number of customers that can be serviced by every trip of the paths in the cover. Depending on different applications, every path in the cover may either be restricted to contain only one trip, or be allowed to contain multiple trips but with a return to the depot between every two consecutive trips. We develop a 5-approximation algorithm for the problem with multiple trips allowed, and a (7+ε)-approximation algorithm for any ε > 0 for the problem with single trips only. For both problems, we show that unless NP = P, it is impossible to achieve any performance ratios less than 3/2.

关键词： min-max path cover capacity constraint single/multiple depots approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Hardness of approximation and integer programming frameworks for searching for caterpillar trees 11

Hardness of approximation and integer programming frameworks...

引用

Proceedings of the Seventeenth Computing: The Australasian Theory Symposium - Volume 119

作者： Micheal J. Dinneen Masoud Khosravani University of Auckland Auckland New Zealand

ISBN: (纸本)9781920682989

We consider the problems of finding a caterpillar tree in a graph. We first prove that, unless P=NP, there is no approximation algorithms for finding a minimum spanning caterpillar in a graph within a factor of f(n); where f(n) is any polynomial time computable function of n, the order of the graph. Then we present a quadratic integer programming formulation for the problem that can be a base for a branch and cut algorithm. We also show that by using Gomory cuts iteratively, one can obtain a solution for the problem that is close to the optimal value by a factor of 1/ε, for 0 < ε < 1. Finally, we show that our formulation is equivalent to a semidefinite programming formulation, which introduces another approach for solving the problem.

关键词： integer programming optimization caterpillar trees approximation algorithm semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth

引用

JOURNAL OF THE ACM 2011年第5期58卷 21-21页

作者： Bateni, Mohammadhossein Hajiaghayi, Mohammadtaghi Marx, Daniel Princeton Univ Dept Comp Sci Princeton NJ 08540 USA Univ Maryland Dept Comp Sci College Pk MD 20742 USA Humboldt Univ Inst Informat D-10099 Berlin Germany Ctr Computat Intractabil Princeton NJ USA

We give the first polynomial-time approximation scheme (PTAS) for the Steiner forest problem on planar graphs and, more generally, on graphs of bounded genus. As a first step, we show how to build a Steiner forest spanner for such graphs. The crux of the process is a clustering procedure called prize-collecting clustering that breaks down the input instance into separate subinstances which are easier to handle;moreover, the terminals in different subinstances are far from each other. Each subinstance has a relatively inexpensive Steiner tree connecting all its terminals, and the subinstances can be solved (almost) separately. Another building block is a PTAS for Steiner forest on graphs of bounded treewidth. Surprisingly, Steiner forest is NP-hard even on graphs of treewidth 3. Therefore, our PTAS for bounded-treewidth graphs needs a nontrivial combination of approximation arguments and dynamic programming on the tree decomposition. We further show that Steiner forest can be solved in polynomial time for series-parallel graphs (graphs of treewidth at most two) by a novel combination of dynamic programming and minimum cut computations, completing our thorough complexity study of Steiner forest in the range of bounded-treewidth graphs, planar graphs, and bounded-genus graphs.

关键词： algorithms Design Performance Theory approximation algorithm bounded-treewidth dynamic programming network design planar graph PTAS series-parallel graph Steiner forest

来源：评论

学校读者我要写书评

暂无评论

Path Planning of Data Mules in Sensor Networks

引用

ACM TRANSACTIONS ON SENSOR NETWORKS 2011年第1期8卷 1-1页

作者： Sugihara, Ryo Gupta, Rajesh K. Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA

We study the problem of planning the motion of "data mules" for collecting the data from stationary sensor nodes in wireless sensor networks. Use of data mules significantly reduces energy consumption at sensor nodes compared to commonly used multihop forwarding approaches, but has a drawback in that it increases the latency of data delivery. Optimizing the motion of data mules, including path and speed, is critical for improving the data delivery latency and making the data mule approach more useful in practice. In this article, we focus on the path selection problem: finding the optimal path of data mules so that the data delivery latency can be minimized. We formulate the path selection problem as a graph problem that is capable of expressing the benefit from larger communication range. The problem is NP-hard and we present approximation algorithms for both single-data mule case and multiple-data mules case. We further consider the case in which we have only partial knowledge of communication range, where we design semionline algorithms that improve the offline plan using online knowledge at runtime. Simulation experiments on Matlab and ns2 demonstrate that our offline and semionline algorithms produce significantly shorter path lengths and data delivery latency compared to previously proposed methods, suggesting that controlled mobility can be exploited much more effectively.

关键词： algorithms Design Performance Controlled mobility approximation algorithm integer programming semionline algorithm simulation

来源：评论

学校读者我要写书评

暂无评论

A Polynomial Time OPT+1 algorithm for the Cutting Stock Problem with a Constant Number of Object Lengths

引用

MATHEMATICS OF OPERATIONS RESEARCH 2011年第4期36卷 743-753页

作者： Jansen, Klaus Solis-Oba, Roberto Univ Kiel Inst Informat D-24118 Kiel Germany Univ Western Ontario Dept Comp Sci London ON N6A 5B7 Canada

In the cutting stock problem, we are given a set of objects of different types, and the goal is to pack them all in the minimum possible number of identical bins. All objects have integer lengths, and objects of different types have different sizes. The total length of the objects packed in a bin cannot exceed the capacity of the bin. In this paper, we consider the version of the problem in which the number of different object types is constant, and we present a polynomial-time algorithm that computes a solution using at most one more bin than an optimum solution.

关键词： cutting stock problem bin packing approximation algorithm mixed-integer programming

来源：评论

学校读者我要写书评

暂无评论

Minimum Latency Data Aggregation In The Physical Interference Model 11

Minimum Latency Data Aggregation In The Physical Interferenc...

引用

14th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM)

作者： Lam, Nhat X. An, Min Kyung Huynh, Dung T. Nguyen, Trac N. Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

ISBN: (纸本)9781450308984

Data aggregation has been the focus of many researchers as one of the most important applications in Wireless Sensor Networks. A main issue of data aggregation is how to construct efficient schedules by which data can be aggregated without any interference. The problem of constructing minimum latency data aggregation schedules (MLAS) has been extensively studied in the literature although most of existing works use the graph-based interference model. In this paper, we study the MLAS problem in the more realistic physical model known as Signal-to-Interference-Noise-Ratio (SINR) where few works exist and algorithms that guarantee theoretical performances are scarce [17, 16]. We first derive an Omega (log n) approximation lower bound for the MLAS problem in the metric SINR model. We also prove the NP-completeness of the decision version of MLAS in the geometric SINR model. This is a significant contribution as these results have not been obtained before for the SINR model. In addition, we propose a constant factor approximation algorithm whose latency is bounded by O(Delta + R) for the dual power model, where Delta is the maximum node degree of a network and R is the network radius. Finally we study the performance of the algorithms through simulation.

关键词： Data aggregation Inapproximability NP-Completeness Geometric graph Signal-to-Interference-Noise-Ratio approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An Pproximation algorithm for the Soft-Capacitated Dynamicfacility Location Problem with Penalties

An Pproximation Algorithm for the Soft-Capacitated Dynamicfa...

引用

The 2011 International Conference on Education Science and Management Engineering(ESME2011)(2011年教育科学与管理工程国际学术会议)

作者： Chunyan JIANG Basic Course Teaching Department the Armed Police AcademyLangfangChina

In this paper, we consider the Soft-Capacitated dynamic facility location problem with penalties (SCDFLPWP).We present a 3.7052-approximation primal-dual combinatorial algorithm for DFLPSP.

关键词： Dynamic facility location problem approximation algorithm submodular function

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：