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

MAXIMUM WEIGHT CYCLE PACKING IN DIRECTED GRAPHS, WITH APPLICATION TO KIDNEY EXCHANGE PROGRAMS

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2009年第4期1卷 499-517页

作者： Biro, Peter Manlove, David F. Rizzi, Romeo Univ Glasgow Dept Comp Sci Glasgow G12 8QQ Lanark Scotland Univ Udine Dipartimento Matemat & Informat DIMI Udine Italy

Centralized matching programs have been established in several countries to organize kidney exchanges between incompatible patient-donor pairs. At the heart of these programs are algorithms to solve kidney exchange problems, which can be modelled as cycle packing problems in a directed graph, involving cycles of length 2, 3, or even longer. Usually, the goal is to maximize the number of transplants, but sometimes the total benefit is maximized by considering the differences between suitable kidneys. These problems correspond to computing cycle packings of maximum size or maximum weight in directed graphs. Here we prove the APX-completeness of the problem of finding a maximum size exchange involving only 2-cycles and 3-cycles. We also present an approximation algorithm and an exact algorithm for the problem of finding a maximum weight exchange involving cycles of bounded length. The exact algorithm has been used to provide optimal solutions to real kidney exchange problems arising from the National Matching Scheme for Paired Donation run by NHS Blood and Transplant, and we describe practical experience based on this collaboration.

关键词： Directed graph triangle packing APX-completeness approximation algorithm exact algorithm kidney paired donation

来源：评论

学校读者我要写书评

暂无评论

APPROXIMATED WINNER DETERMINATION FOR A SERIES OF COMBINATORIAL AUCTIONS

APPROXIMATED WINNER DETERMINATION FOR A SERIES OF COMBINATOR...

引用

1st International Conference on Agents and Artificial Intelligence

作者： Fukuta, Naoki Ito, Takayuki Shizuoka Univ Fac Informat 3 5 1 Johoku Shizuoka Japan Nagoya Inst Technol Grad Sch Engn Showa Ku Nagoya Aichi Japan MIT Sloan Sch Management Cambridge MA 02139 USA

ISBN: (纸本)9789898111661

In this paper, we propose approximated winner determination algorithms for iteratively conducted combinatorial auctions. Our algorithms are designed to effectively reuse last-cycle solutions to speed up the initial approximation performance on the next cycle. Experimental results show that our proposed algorithms outperform existing algorithms when a large number of similar bids are contained through iterations. Also, we propose an enhanced algorithm that effectively avoids the undesirable reuse of the last solutions in the algorithm without serious computational overheads.

关键词： Combinatorial auctions Winner determination approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Bicriteria Scheduling on Single-Machine with Inventory Operations

Bicriteria Scheduling on Single-Machine with Inventory Opera...

引用

3rd International Conference on Combinatorial Optimization and Applications (COCOA 2009)

作者： Fan, Baoqiang Chen, Rongjun Tang, Guochun Ludong Univ Dept Math & Informat Yantai 264025 Peoples R China Changzhou Inst Technol Dept Math Changzhou 213002 Peoples R China Shanghai Second Polytech Univ Inst Management Engn Shanghai 201209 Peoples R China

ISBN: (纸本)9783642020254

In this paper, we consider the single machine scheduling problem with inventory operations. The objective is to minimize makespan subject. to the constraint that the total number of tardy jobs is minimum. We show the problem is strongly NP-hard. A polynomial (1 + 1/(m - 1))-approximation scheme for the problem is presented, where m. is defined as the total job's processing times Sigma p(j) divided by the capacity c of the storage, and an optimal algorithm for a special case of the problem, in which each job is one unit in size, is provided.

关键词： scheduling bicriteria NP-hardness approximation algorithm performance ratio

来源：评论

学校读者我要写书评

暂无评论

Squarepants in a Tree: Sum of Subtree Clustering and Hyperbolic Pants Decomposition 18

Squarepants in a Tree: Sum of Subtree Clustering and Hyperbo...

引用

18th ACM-SIAM Symposium on Discrete algorithms

作者： Eppstein, David Univ Calif Irvine Dept Comp Sci Irvine CA 92697 USA

ISBN: (纸本)9780898716245

We provide efficient constant-factor approximation algorithms for the problems of finding a hierarchical clustering of a point set in any metric space, minimizing the sum of minimimum spanning tree lengths within each cluster, and in the hyperbolic or Euclidean planes, minimizing the sum of cluster perimeters. Our algorithms for the hyperbolic and Euclidean planes can also be used to provide a pants decomposition, that is, a set of disjoint simple closed curves partitioning the plane minus the input points into subsets with exactly three boundary components, with approximately minimum total length. In the Euclidean case, these curves are squares;in the hyperbolic case, they combine our Euclidean square pants decomposition with our tree clustering method for general metric spaces.

关键词： Hierarchical clustering minimum spanning tree hyperbolic geometry approximation algorithm sum of cluster sizes pants decomposition

来源：评论

学校读者我要写书评

暂无评论

Approximating Some Network Design Problems with Node Costs

Approximating Some Network Design Problems with Node Costs

引用

12th International Workshop on approximation algorithms for Combinatorial Optimization Problems/13th International Workshop on Randomization and Computation

作者： Kortsarz, Guy Nutov, Zeev Rutgers State Univ Camden NJ 08102 USA Open Univ Israel Raanana Israel

ISBN: (纸本)9783642036842

We study several multi-criteria undirected network design problems with node costs and lengths with all problems related to the node cost's Multicommodity Buy at Bulk (MBB) problem in which we are given a graph G = (V, E), demands {d(st) : s,t is an element of V} and a family {c(nu) : nu is an element of V} of subadditive cost functions. For every s,t is an element of V we seek to send d(st) flow units from s to t on a single path, so that Sigma(nu) c(nu)(f(nu)) is minimized, Where f(nu) the Lotal alliolint, of flow through nu. lit the Multicommodity Cost-Distance (MCD) problem we are also given lengths, {l(nu) : nu is an element of V}, and seek a subgraph H of G that minimizes c(H) + Sigma(s,t is an element of V) d(st) . l(H)(s,t), where l(H)(s,t) is the minimum l-length of an st-path in H. The approximation for these two problems is equivalent, up to a factor arbitrarily close to 2. We give an O(log(3) n)-approximation algorithm for both problems for the case of demands, polynomial in n. The previously best. known approximation ratio for these problems was O(log(4) n) [Chekuri et;al, FOCS 2006] and [Chekuri et al., SODA 2007]. This technique seems quite robust, and was already used in order to improve, the ratio of Buy-at-bulk with protection (Antonakopoulos et, al FOCS 2007) from log(3) h to log(2) h. See [3]. We also consider the Maximum Covering Tree (MaxCT) problem which is closely related to MBB: given a, graph G = (V,E), costs {c(nu) : nu is an element of V}, profits {p(nu) : nu is an element of V}, and a bound C, find a subtree T of G with c(T) <= C and p(T) maximum. The best, known approximation algorithm for MaxCT [Moss and Rabani, STOC 2001] computes a tree T with c(T) <= 2C and p(T) = Omega(opt/log n). We provide the first non-trivial lower bound and in fact. provide a bicriteria lower bound on approximating this problem (which is stronger than the usual lower bound) by showing that, the problem admits no better than Omega(1/(log log n)) approximation a

关键词： Network design Node costs Multicommodity Buy at Bulk Covering tree approximation algorithm Hardness of approximation

来源：评论

学校读者我要写书评

暂无评论

BICRITERIA SCHEDULING ON SINGLE-MACHINE WITH INVENTORY OPERATIONS

引用

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2009年第2期1卷 227-234页

In this paper, we consider the single machine scheduling problem with inventory operations. The objective is to minimize makespan subject to the constraint that the total number of tardy jobs is minimum. We show the problem is strongly NP-hard. A polynomial 1+1/m-1-approximation scheme for the problem is presented, where m is defined as the total job's processing times Sigma p(j) divided by the capacity c of the storage, and an optimal algorithm for a special case of the problem, in which each job is one unit in size.

关键词： Scheduling bicriteria NP-hardness approximation algorithm performance ratio

来源：评论

学校读者我要写书评

暂无评论

ON THE PERFORMANCE OF SEMIDEFINITE RELAXATION MIMO DETECTORS FOR QAM CONSTELLATIONS

ON THE PERFORMANCE OF SEMIDEFINITE RELAXATION MIMO DETECTORS...

引用

IEEE International Conference on Acoustics, Speech and Signal Processing

作者： So, Anthony Man-Cho Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China

ISBN: (纸本)9781424423538

Due to their computational efficiency and strong empirical performance, semidefinite relaxation (SDR)-based algorithms have gained much attention in multiple-input multiple-output (MIMO) detection. In the case of a binary phase-shift keying (BPSK) constellation, the theoretical performance of the SDR approach is relatively well-understood. However, little is known about the case of quadrature amplitude modulation (QAM) constellations, although simulation results suggest that the SDR approach should work well in the low signal-to-noise ratio (SNR) region. In this paper we make a first step towards explaining such phenomenon by showing that in the case of QAM constellations, several commonly used SDR-based algorithms will provide a constant factor approximation to the optimal log-likelihood value in the low SNR region with exponentially high probability. Our result gives some theoretical justification for using SDR-based algorithms for the MIMO detection of QAM signals, at least in the low SNR region.

关键词： Multiple-Input Multiple-Output (MIMO) Detection Quadrature Amplitude Modulation (QAM) Semidefinite Relaxation Performance Analysis approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Better approximation Ratio for the Vertex Cover Problem

引用

ACM TRANSACTIONS ON algorithmS 2009年第4期5卷 1–8页

作者： Karakostas, George McMaster Univ Dept Comp & Software Hamilton ON L8S 4K1 Canada

We reduce the approximation factor for the vertex cover to 2 - Theta(1/root log n) (instead of the previous 2 - Theta lnlnn/2lnn obtained by Bar-Yehuda and Even [1985] and Monien and Speckenmeyer [1985]). The improvement of the vanishing factor comes as an application of the recent results of Arora et al. [2004] that improved the approximation factor of the sparsest cut and balanced cut problems. In particular, we use the existence of two big and well-separated sets of nodes in the solution of the semidefinite relaxation for balanced cut, proven by Arora et al. [2004]. We observe that a solution of the semidefinite relaxation for vertex cover, when strengthened with the triangle inequalities, can be transformed into a solution of a balanced cut problem, and therefore the existence of big well-separated sets in the sense of Arora et al. [2004] translates into the existence of a big independent set.

关键词： approximation algorithm vertex cover semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for item pricing with bounded degree and valuation

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2008年第2期E91D卷 187-199页

作者： Hamane, Ryoso Itoh, Toshiya Tokyo Inst Technol Dept Informat Proc Tokyo 1528552 Japan Tokyo Inst Technol Global Sci Informat & Comp Ctr Tokyo 1528552 Japan

When a store sells items to customers, the store wishes to decide the prices of the items to maximize its profit. If the store sells the items with low (resp. high) prices, the customers buy more (resp. less) items, which provides less profit to the store. It would be hard for the store to decide the prices of items. Assume that a store has a set V of n items and there is a set C of m customers who wish to buy those items. The goal of the store is to decide the price of each item to maximize its profit. We refer to this maximization problem as an item pricing problem. We classify the item pricing problems according to how many items the store can sell or how the customers valuate the items. If the store can sell every item i with unlimited (resp. limited) amount, we refer to this as unlimited supply (resp. limited supply). We say that the item pricing problem is single-minded if each customer j is an element of C wishes to buy a set e(j) subset of V of items and assigns valuation w(e(j)) >= 0. For the single-minded item pricing problems (in unlimited supply), Bal-can and Blum regarded them as weighted k-hypergraphs and gave several approximation algorithms. In this paper, we focus on the (pseudo) degree of k-hypergraphs and the valuation ratio, i.e., the ratio between the smallest and the largest valuations. Then for the single-minded item pricing problems (in unlimited supply), we show improved approximation algorithms (for k-hypergraphs, general graphs, bipartite graphs, etc.) with respect to the maximum (pseudo) degree and the valuation ratio.

关键词： item pricing approximation algorithm pseudodegree valuation ratio

来源：评论

学校读者我要写书评

暂无评论

MINIMUM ENERGY BROADCAST ROUTING IN AD HOC AND SENSOR NETWORKS WITH DIRECTIONAL ANTENNAS

引用

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2009年第2期1卷 205-218页

作者： Li, Zheng Li, Deying Renmin Univ China MOE Key Lab Data Engn & Knowledge Engn Beijing Peoples R China Renmin Univ China Sch Informat Beijing Peoples R China

In this paper we discuss minimum energy broadcast routing with directional antennas in ad hoc and sensor networks. We assume that the network consists of sensor nodes whose antennas are switched beam directional antennas. The problem of our concern is: a given set V with n nodes and each node v(i) has l(i) transmission directions (i.e. the antenna sectors) and a broadcast request sourced at s, how to find a broadcast tree rooted at s and spanning all nodes in V such that the total energy is minimized. This problem involves with the choice of transmitting nodes and their transmission directions, which is NP-hard. We firstly propose a directed Steiner tree-based approximation algorithm for this problem and discuss its distributed implementation. Then we also propose a |V|-approximation algorithm and one heuristic with lower time complexities. Extensive simulations have demonstrated the efficiency of our algorithms.

关键词： Wireless ad hoc and sensor networks energy efficient broadcast directional antenna approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：