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

Greedy splitting algorithms for approximating multiway partition problems

MATHEMATICAL PROGRAMMING 2005年第1期102卷 167-183页

作者： Zhao, L Nagamochi, H Ibaraki, T Utsunomiya Univ Fac Engn Dept Informat Sci Utsunomiya Tochigi 3218585 Japan Toyohashi Univ Technol Dept Informat & Comp Sci Aichi 4418580 Japan Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto Japan

Given a system (V, T, f, k), where V is a finite set, T subset of or equal to V, f : 2(V) --> R is a submodular function and k greater than or equal to 2 is an integer, the general multiway partition problem (MPP) asks to find a k-partition P = {V-1, V-2,..., V-k} of V that satisfies V-i boolean AND T not equal empty set for all i and minimizes f (V-1) + f (V-2)+...+ f (V-k), where P is a k-partition of V if ( i) V-i not equal empty set, (ii) V-i boolean AND V-j = empty set, i not equal j, and (iii) V-1 boolean OR V-2 boolean OR ... V-k = V hold. MPP formulation captures a generalization in submodular systems of many NP-hard problems such as k-way cut, multiterminal cut, target split and their generalizations in hypergraphs. This paper presents a simple and unified framework for developing and analyzing approximation algorithms for various MPPs.

关键词： approximation algorithm hypergraph partition k-way cut multiterminal cut multiway partition problem submodular function

来源：评论

学校读者我要写书评

暂无评论

On a bidirected relaxation for the MULTIWAY CUT problem

引用

DISCRETE APPLIED MATHEMATICS 2005年第1-3期150卷 67-79页

作者： Chekuri, C Gupta, A Kumar, A Lucent Bell Labs Murray Hill NJ 07974 USA Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA Indian Inst Technol Dept Comp Sci New Delhi 110016 India

In the MULTIWAY CUT problem, we are given an undirected edge-weighted graph G = (V, E) with C-e denoting the cost (weight) of edge e. We are also given a subset S of V, of size k, called the terminals. The objective is to find a minimum cost set of edges whose removal ensures that the terminals are disconnected. In this paper, we study a bidirected linear programming relaxation of MULTIWAY CUT. We resolve an open problem posed by Vazirani [approximation algorithms, first ed., Springer, Berlin, Heidelberg, 20011, and show that the integrality gap of this relaxation is not better than that for a geometric linear programming relaxation given by Calinescu et al. [J. Comput. System Sci. 60(3) (2000) 564-574], and may be strictly worse on some instances. (c) 2005 Elsevier B.V. All rights reserved.

关键词： MULTIWAY CUT problem bidirected relaxation approximation algorithm integrality gap

来源：评论

学校读者我要写书评

暂无评论

Flows over time with load-dependent transit times

引用

SIAM JOURNAL ON OPTIMIZATION 2005年第4期15卷 1185-1202页

作者： Köhler, E Skutella, M Tech Univ Berlin Fak Math & Nat Wissensch 2 Inst Math D-10623 Berlin Germany Univ Dortmund Inst Angew Math D-44221 Dortmund Germany

More than forty years ago, Ford and Fulkerson studied maximum s-t-flows over time (also called "dynamic" flows) in networks with fixed transit times on the arcs and a fixed time horizon. Here, flow on arcs may change over time and transit times specify the amount of time it takes for flow to travel through a particular arc. Ford and Fulkerson proved that there always exists an optimal solution which sends flow on certain s-t-paths at a constant rate as long as there is enough time left for the flow along a path to arrive at the sink;a flow over time featuring this simple structure is called "temporally repeated." Although this result does not hold for the more general and also more realistic setting where transit times depend on the current flow situation, we show that there always exists a provably good temporally repeated solution. Moreover, such a solution can be determined very efficiently by only one minimum convex cost flow computation. Our results rest upon a new model of flow-dependent transit times. It is based on two assumption on the pace of flow on a particular arc. First, the pace of flow on an arc is assumed to be uniform for all flow units on an arc for each point in time. Second, this uniform pace is for each moment determined by the actual amount of flow on this arc. Finally, we show that the resulting flow-over-time problem is strongly NP-hard and cannot be approximated with arbitrary precision in polynomial time, unless P=NP.

关键词： network flow dynamic flow congestion approximation algorithm traffic routing

来源：评论

学校读者我要写书评

暂无评论

k-Center problems with minimum coverage

引用

THEORETICAL COMPUTER SCIENCE 2005年第1-3期332卷 1-17页

作者： Lim, A Rodrigues, B Wang, F Xu, Z Hong Kong Univ Sci & Technol Dept Ind Engn & Engn Management Kowloon Hong Kong Peoples R China Singapore Management Univ Sch Business Singapore Singapore

In this work, we study an extension of the k-center facility location problem, where centers are required to service a minimum of clients. This problem is motivated by requirements to balance the workload of centers while allowing each center to cater to a spread of clients. We study three variants of this problem, all of which are shown to be N P-hard. In-approximation hardness and approximation algorithms with factors equal or close to the best lower bounds are provided. Generalizations, including vertex costs and vertex weights, are also studied. (c) 2004 Elsevier B.V. All rights reserved.

关键词： approximation algorithm k-center problem minimum coverage

来源：评论

学校读者我要写书评

暂无评论

The approximability of the weighted Hamiltonian path completion problem on a tree

引用

THEORETICAL COMPUTER SCIENCE 2005年第1-3期341卷 385-397页

作者： Wu, Q Lu, CL Lee, RCT Natl Chiao Tung Univ Dept Biol Sci & Technol Hsinchu 300 Taiwan Natl Chi Nan Univ Grad Inst Commun Engn Puli 545 Nantou Hsien Taiwan Natl Chi Nan Univ Dept Comp Sci & Informat Engn Puli 545 Nantou Hsien Taiwan

Given a graph, the Hamiltonian path completion problem is to find an augmenting edge set such that the augmented graph has a Hamiltonian path. In this paper, we show that the Hamiltonian path completion problem will unlikely have any constant ratio approximation algorithm unless NP = P. This problem remains hard to approximate even when the given subgraph is a tree. Moreover, if the edge weights are restricted to be either 1 or 2, the Hamiltonian path completion problem on a tree is still NP-hard. Then it is observed that this problem is strongly NP-hard, so it does not have any fully polynomial-time approximation scheme (FPTAS) unless NP = P. When the given tree is a k-tree, we give an approximation algorithm with performance ratio 1.5. (c) 2005 Elsevier B.V. All rights reserved.

关键词： Hamiltonian path completion problem trees strongly NP-hard approximation algorithm fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Building edge-failure resilient networks

引用

algorithmICA 2005年第1-2期43卷 17-41页

作者： Chekuri, C Gupta, A Kumar, A Naor, J Raz, D Lucent Technol Bell Labs Murray Hill NJ 07974 USA Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA Indian Inst Technol Dept Comp Sci New Delhi 110016 India Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Cornell Univ Ithaca NY 14853 USA

We consider the design of resilient networks that are fault tolerant against link failures. Resilience against link failures can be built into the network by providing backup paths, which are used in the eventuality of an edge failure occurring on a primary path in the network. We consider several network design problems in this context;these problems are motivated by the requirements of current high-speed optical networks. In all the following problems the objective is to provide resilience in networks while minimizing the cost incurred. The main problem under consideration in this paper is that of backup allocation: this problem takes as its input an already provisioned primary network and a parameter k, and allocates backup capacity on the edges of the underlying network so that all the demand can be routed even in the presence of k edge failures. We also consider a variant of this problem where the primary network has a tree topology, and it is required that the restored network retains a tree topology. We then address the problem of simultaneous primary and backup allocation: we are given specifications of the traffic to be handled, and the goal is to provision both the primary as well as the backup network. Finally, we investigate a single-commodity problem motivated by a pragmatic scenario in which the primary network is not known in advance and demands between source--sink pairs arrive online.

关键词： network design link failure backup path restoration approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Average-case performance analysis of a 2D strip packing algorithm - NFDH

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2005年第1期9卷 14-34页

作者： Gu, XD Chen, GL Xu, YL Univ Sci & Technol China Dept Comp Sci & Technol Natl High Performance Comp Ctr Hefei Hefei 230027 Peoples R China

The two-dimensional strip packing problem is a generalization of the classic one-dimensional bin packing problem. It has many important applications such as costume clipping, material cutting, real-world planning, packing, scheduling etc. Average-case performance analysis of approximation algorithms attracts a lot of attention because it plays a crucial role in selecting an appropriate algorithm for a given application. While approximation algorithms for two-dimensional packing are frequently presented, the results of their average-case performance analyses have seldom been reported due to intractability. In this paper, we analyze the average-case performance of Next Fit Decreasing Height (NFDH) algorithm, one of the first strip packing algorithms proposed by Coffman, Jr. in 1980. We prove that the expected height of packing with NFDH algorithm, when the heights and widths of the rectangle items are independent and both obey (0, 1] uniform distribution, is about n/3, where n is the number of rectangle items. We also validate the theoretical result with experiments.

关键词： bin packing approximation algorithm average-case performance ratio worst-case performance ratio NP-hard

来源：评论

学校读者我要写书评

暂无评论

A PTAS for semiconductor burn-in scheduling

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2005年第1期9卷 1-13页

作者： Deng, XT Feng, HD Li, GJ Shi, BY Shandong Univ Sch Math & Syst Sci Jinan 250100 Peoples R China Chinese Acad Sci Inst Software Beijing 100080 Peoples R China Shandong Univ Sch Comp Sci & Technol Jinan 250100 Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

In this paper a polynomial time approximation scheme, PTAS for short, is presented for the problem of scheduling jobs in a batch processing system. Each job has a pre-defined release date, which indicates when the job is available, and a pre-defined burn-in time, which is the least time needed for processing the job. At one time, at most B jobs can be processed together, where B is a pre-given number. No preemption is permitted.

关键词： approximation algorithm batch processing release date geometric rounding time stretching

来源：评论

学校读者我要写书评

暂无评论

On the one-sided crossing minimization in a bipartite graph with large degrees

引用

THEORETICAL COMPUTER SCIENCE 2005年第1-3期332卷 417-446页

作者： Nagamochi, H Kyoto Univ Dept Appl Math & Phys Kyoto 6068501 Japan

Given a bipartite graph G = (V, W, E), a 2-layered drawing consists of placing nodes in the first node set V on a straight line L-1 and placing nodes in the second node set Won a parallel line L-2. For a given ordering of nodes in Won L2, the one-sided crossing minimization problem asks to find an ordering of nodes in V on L-1 so that the number of arc crossings is minimized. A well-known lower bound LB on the minimum number of crossings is obtained by summing up min{c(uv), c(vu)} over all node pairs u, v is an element of V, where c(uv) denotes the number of crossings generated by arcs incident to u and v when u precedes v in an ordering. In this paper, we prove that there always exists a solution whose crossing number is at most (1.2964 + 12/(delta - 4))LB if the minimum degree delta of a node in V is at least 5. (c) 2004 Elsevier B.V. All rights reserved.

关键词： approximation algorithm bipartite graph edge crossing graph drawing 2-layered drawing randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Single-machine scheduling with precedence constraints

引用

MATHEMATICS OF OPERATIONS RESEARCH 2005年第4期30卷 1005-1021页

作者： Correa, JR Schulz, AS Univ Adolfo Ibanez Sch Business Santiago Chile MIT Alfred P Sloan Sch Management Cambridge MA 02139 USA

We discuss the problem of sequencing precedence-constrained jobs on a single machine to minimize the average weighted completion time. This problem has attracted much attention in the mathematical programming community since Sidney's pioneering work in 1975 (Sidney, J. B. 1975. Decomposition algorithms for single machine scheduling with precedence relations and deferral costs. Operations Research 23 283-298). We look at the problem from a polyhedral perspective and uncover a relation between Sidney's decomposition theorem and different linear programming relaxations. More specifically, we present a generalization of Sidney's result, which particularly allows us to reason that virtually all known 2-approximation algorithms are consistent with his decomposition. Moreover, we establish a connection between the single-machine scheduling problem and the vertex cover problem. Indeed, in the special case of series-parallel precedence constraints, we prove that the sequencing problem can be seen 'as a special case of the vertex cover problem. We also. argue that this result is true for general precedence constraints if one can show that a certain integer program represents a valid formulation of the sequencing problem. Finally, we give a 3/2-approximation algorithm for two-dimensional partial orders, and we also provide a characterization of the active inequalities of a linear programming relaxation in completion time variables.

关键词： linear ordering scheduling vertex cover linear programming relaxation integer programming formulation approximation algorithm partial order

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：