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

Selected multicriteria shortest path problems: An analysis of complexity, models and adaptation of standard algorithms

引用

INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS AND COMPUTER SCIENCE 2007年第2期17卷 269-287页

作者： Tarapata, Zbigniew Mil Univ Technol Fac Cybernet Div Operat Res & Decis Support PL-00908 Warsaw Poland

The paper presents selected multicriteria (multiobjective) approaches to shortest path problems. A classification of multiobjective shortest path (MOSP) problems is given. Different models of MOSP problems are discussed in detail. Methods of solving the formulated optimization problems are presented. An analysis of the complexity of the presented methods and ways of adapting of classical algorithms for solving multiobjective shortest path problems are described. A comparison of the effectiveness of solving selected MOSP problems defined as mathematical programming problems (using the CPLEX 7.0 solver) and multi-weighted graph problems (Using modified Dijkstra's algorithm) is given. Experimental results of using the presented methods for multicriteria path selection in a terrain-based grid network are given.

关键词： multiobjective shortest path stochastic shortest path algorithm complexity routing problem terrain-based modeling approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Generalizing the induced matching by edge capacity constraints

引用

DISCRETE OPTIMIZATION 2007年第2期4卷 198-205页

作者： Fukunaga, Takuro Nagamochi, Hiroshi Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto Japan

Given an edge-weighted graph, the induced matching problem is an edge packing problem, which asks to find a maximum weight edge set such that every edge in the graph is adjacent to at most one edge in the set. In this paper, we generalize this problem by introducing edge capacities and propose an approximation algorithm to the problem. The analysis of this algorithm is based on a relationship between two polytopes for an LP relaxation of the above problem and the capacitated b-matching problem. (c) 2006 Elsevier B.V. All rights reserved.

关键词： approximation algorithm induced matching edge capacity polytopes

来源：评论

学校读者我要写书评

暂无评论

The demand-matching problem

引用

MATHEMATICS OF OPERATIONS RESEARCH 2007年第3期32卷 563-578页

作者： Shepherd, F. B. Vella, A. Bell Labs Murray Hill NJ 07974 USA McGill Univ Dept Math & Stat Montreal PQ Canada

We examine formulations for the well-known b-matching problem in the presence of integer demands on the edges. A subset M of edges is feasible if for each node v the total demand of edges in M incident to v is at most b(v). We examine the system of star inequalities for this problem. This system yields an exact linear description for b-matchings in bipartite graphs. For the demand version, we show that the integrality gap for this system is at least 2.5 and at most 2.764. For general graphs, the gap lies between 3 and 3.264. We also describe a 3-approximation algorithm (2.5 for bipartite graphs) for the cardinality version of the problem. A full), polynomial approximation scheme is also presented for the problem on a tree, thus generalising a well-known result for the knapsack problem. Recently, the notion of demand matching has arisen in the design of Clos network switches.

关键词： b-matching linear programming integrality gap approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A reliable and efficient MAC layer broadcast protocol for mobile ad hoc networks

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2007年第4期56卷 2296-2305页

作者： Chiu, Chun-Yuan Wu, Eric Hsiao-Kuang Chen, Gen-Huey Natl Taiwan Univ Dept Comp Sci & Informat Engn Taipei 106 Taiwan Natl Cent Univ Dept Comp Sci & Informat Engn Chungli 320 Taiwan

Flexible multimedia broadcast/multicast services such as mobile auction and advertisements are vital services for future mobile ad hoc networks. A great number of applications rely on a reliable and efficient medium access control (MAC) layer broadcast. The current IEEE 802.11 broadcast protocol based on carrier sense multiple access with collision avoidance does not offer any MAC layer recovery on broadcast frames. Consequently, unexpected lost frames may deteriorate the quality of broadcast/multicast services. Previous protocols extended request-to-send, clear-to-send, and acknowledgement to enhance the broadcast reliability. However, they still suffered from the hidden terminal problem and the excessive retransmission problem at the same time. In this paper, we first formulate the excessive retransmission problem as an optimization problem and show that it is NP-hard even if the upper layer service is periodical beacon exchange. An approximation algorithm with a guaranteed approximation ratio is also suggested. Then, a reliable and efficient MAC layer broadcast protocol, which is named broadcast protocol with busy tone (BPBT), is proposed. BPBT applies a busy tone to solve the hidden terminal problem and applies the proposed approximation algorithm to solve the excessive retransmission problem. Finally, BPBT is compared with previous protocols for performance evaluation by simulation.

关键词： ad hoc network approximation algorithm broadcast busy tone medium access control (MAC)

来源：评论

学校读者我要写书评

暂无评论

Approximating the fixed linear crossing number

引用

DISCRETE APPLIED MATHEMATICS 2007年第17期155卷 2202-2210页

作者： Cimikowski, Robert Mumey, Brendan Warren Natl Univ Dept Comp Sci Prescott AZ 86305 USA Montana State Univ Dept Comp Sci Bozeman MT 59717 USA

We present a randomized polynomial-time approximation algorithm for the fixed linear crossing number problem (FLCNP). In this problem, the vertices of a graph are placed in a fixed order along a horizontal "node line" in the plane, each edge is drawn as an arc in one of the two half-planes (pages), and the objective is to minimize the number of edge crossings. FLCNP is NP-hard, and no previous polynomial-time approximation algorithms are known. We show that the problem can be generalized to k pages and transformed to the maximum k-cut problem which admits a randomized polynomial-time approximation. For the 2-page case, our approach leads to a randomized polynomial time 0.878 + 0.122 rho approximation algorithm for FLCNP, where rho is the ratio of the number of conflicting pairs (pairs of edges that cross if drawn in the same page) to the crossing number. We further investigate this performance ratio on the random graph family G(n), 1/2, where each edge of the complete graph K,1 occurs with probability 1/2. We show that a longstanding conjecture for the crossing number of K-n implies that with probability at least 1 - 4e(-lambda 2) the expected performance bound of the algorithm on a random graph from G(n). 1/2 is 1.366 + O(lambda/n). A series of experiments is performed to compare the algorithm against two other leading heuristics on a set of test graphs. The results indicate that the randomized algorithm yields near-optimal solutions and outperforms the other heuristics overall. (C) 2007 Elsevier B.V. All rights reserved.

关键词： crossing number approximation algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithms for the minimum partitioning problems in graphs

引用

ELECTRONICS AND COMMUNICATIONS IN JAPAN PART III-FUNDAMENTAL ELECTRONIC SCIENCE 2007年第10期90卷 63-78页

作者： Nagamochi, Hiroshi Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan

In this paper, the author explains the recent evolution of algorithms for minimum partitioning problems in graphs. When the set of vertices of a graph having non-negative weights for edges is divided into k subsets, the set of edges for which both endpoints are contained in different subsets is called a k-way cut or k-cut. The problem of obtaining the k-way cut that minimized the sum of the weights is an important research topic that appears in many practical applications such as VLSI design. In this paper, the author introduces recent results including cases in which sets of terminals or sets of terminal pairs that are to be separated are further specified in this problem and cases in which the objects to be partitioned are extended from graphs to hypergraphs or submodular set functions. (C) 2007 Wiley Periodicals, Inc.

关键词： graph partitioning hypergraph cut submodular function approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Linear time algorithms for approximating the facility terminal cover problem

引用

NETWORKS 2007年第1期50卷 118-126页

作者： Xu, Guang Yang, Yang Xu, Jinhui SUNY Buffalo Dept Comp Sci & Engn Buffalo NY 14260 USA

In this paper, we consider an interesting generalization of the weighted vertex cover problem, called the Facility Terminal Cover (FTC) problem. In the FTC problem, each vertex is associated with a positive weight, each edge is associated with a positive demand, and the objective is to determine a subset of vertices and a capacity for each selected vertex so that the demand of each edge is covered by the capacity of one of its two endpoints and the total weighted capacity of all selected vertices is minimized. The FTC problem is motivated by several key network optimization problems, such as the power assignment problem in ad hoc networks, and could be used as a subroutine to solve such problems. No quality-guaranteed solution is previously known for the FTC problem. In this paper, we present two linear time approximation algorithms for this problem. Our first algorithm achieves deterministically an approximation ratio of 8 by using an interesting rounding technique and a lower-bounding technique. Based on interesting randomization techniques, our second algorithm further improves the approximation ratio to 2e, where e is the natural logarithmic base. The second algorithm can be easily derandomized in quadratic time. Our algorithms are relatively simple and can be easily implemented for networking applications. Experiments show that the two algorithms behave rather similarly, especially in largesize graphs, indicating that the solutions yielded by one or both algorithms are much closer to the optimum. (C) 2007 Wiley Periodicals, Inc.

关键词： algorithm graph theory vertex cover approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximability of the capacitated b-edge dominating set problem

引用

THEORETICAL COMPUTER SCIENCE 2007年第1-3期385卷 202-213页

作者： Berger, Andre Fukunaga, Takuro Nagamochi, Hiroshi Parekh, Ojas Kyoto Univ Dept Appl Math & Phys Grad Sch Informat Kyoto 606 Japan Tech Univ Berlin Dept Math D-10623 Berlin Germany Emory Univ Dept Math & Comp Sci Atlanta GA 30322 USA

In this paper, we discuss the approximability of the capacitated b-edge dominating set problem, which generalizes the edge dominating set problem by introducing capacities and demands on the edges. We present an approximation algorithm for this problem and show that it achieves a factor of 8/3 for general graphs and a factor of 2 for bipartite graphs. Moreover, we discuss the relationships of the edge dominating set problem and the vertex cover problem. The results show that improving the approximation factor beyond 8/3 using our approach of adding valid inequalities to a natural linear programming relaxation is as hard as improving the approximation factor for vertex cover beyond 2. (c) 2007 Elsevier B.V. All rights reserved.

关键词： edge dominating set approximation algorithm integrality gap

来源：评论

学校读者我要写书评

暂无评论

Finding well-balanced pairs of edge-disjoint trees in edge-weighted graphs

引用

DISCRETE OPTIMIZATION 2007年第3-4期4卷 334-348页

作者： Bang-Jensena, Jorgen Goncalves, Daniel Gortz, Inge Li Univ So Denmark Dept Math & Comp Sci DK-5230 Odense Denmark LIRMM F-34392 Montpellier France Tech Univ Denmark Dept Informat & Math Modeling DK-2800 Lyngby Denmark

The well-known number partition problem is NP-hard even in the following version: Given a set S of n non-negative integers;partition S into two sets X and Y such that vertical bar X vertical bar = vertical bar Y vertical bar and the sum of the elements in X is as close as possible to the sum of the elements in Y (or equivalently, minimize the maximum of the two sums). In this paper we study the following generalization of the partition problem: given an edge-weighted graph G containing two edge-disjoint spanning trees. Find a pair of edge-disjoint spanning trees such that the maximum weight of these two trees is as small as possible. In the case when G is precisely the union of two trees this problem may be seen as a generalization of the partition problem in which we have added a graph structure to the numbers (through the edges) and the extra restriction that only the sets X and Y which correspond to trees in G are valid partitions. We first show how to obtain a 2-approximation via an algorithm for weighted matroid partition. Then we describe a simple heuristic which when applied to the 2-approximation above will result in a solution whose value is no more than 3/2 times the value of an optimal solution. We also show that the approach above may sometimes exclude all the optimal solutions. Both the partition problem and its generalization to the problem above on edge-disjoint spanning trees are special cases of the problem of finding, in a weighted matroid with two disjoint bases, a pair of disjoint bases which minimize the maximum of their weights. In the last part of the paper we give some results on this problem for transversal matroids which turn out to be analogous to those for graphs. (c) 2007 Elsevier B.V. All rights reserved.

关键词： edge-disjoint spanning trees approximation algorithm graphic matroid transversal matroid matroid partition algorithm approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A simple linear time algorithm for scheduling with step-improving processing times

引用

COMPUTERS & OPERATIONS RESEARCH 2007年第8期34卷 2396-2402页

作者： Ji, Min He, Yong Cheng, T. C. E. Hong Kong Polytech Univ Dept Logist Kowloon Hong Kong Peoples R China Zhejiang Univ State Key Lab CAD & CG Dept Math Hangzhou 310027 Peoples R China

We consider the problem of scheduling jobs with step-improving processing times around a common critical date on a single machine to minimize the makespan. For this problem, we present a simple linear time off-line ap... 详细信息

关键词： scheduling approximation algorithm worst-case ratio

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：