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

Variable Sized Online Interval Coloring with Bandwidth

algorithmICA 2009年第3期53卷 385-401页

作者： Epstein, Leah Erlebach, Thomas Levin, Asaf Univ Leicester Dept Comp Sci Leicester LE1 7RH Leics England Univ Haifa Dept Math IL-31905 Haifa Israel Hebrew Univ Jerusalem Dept Stat IL-91905 Jerusalem Israel

We consider online coloring of intervals with bandwidth in a setting where colors have variable capacities. Whenever the algorithm opens a new color, it must choose the capacity for that color and cannot change it later. A set of intervals can be assigned the same color a of capacity C (a) if the sum of bandwidths of intervals at each point does not exceed C (a) . The goal is to minimize the total capacity of all the colors used. We consider the bounded model, where all capacities must be chosen in the range (0,1], and the unbounded model, where the algorithm may use colors of any positive capacity. For the absolute competitive ratio, we give an upper bound of 14 and a lower bound of 4.59 for the bounded model, and an upper bound of 4 and a matching lower bound of 4 for the unbounded model. We also consider the offline version of these problems and show that whereas the unbounded model is polynomially solvable, the bounded model is NP-hard in the strong sense and admits a 3.6-approximation algorithm.

关键词： Competitive analysis Interval coloring Lower bound approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

APPROXIMATE NONLINEAR OPTIMIZATION OVER WEIGHTED INDEPENDENCE SYSTEMS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2009年第4期23卷 1667-1681页

作者： Lee, Jon Onn, Shmuel Weismantel, Robert IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA Technion Israel Inst Technol IL-32000 Haifa Israel Otto VonGuericke Univ Magdegurg D-39106 Magdeburg Germany

We consider optimizing a nonlinear objective function over a weighted independence system presented by a linear-optimization oracle. We provide an efficient algorithm that determines an r-best solution for nonlinear functions of the total weight of an independent set, where r depends only on certain Frobenius numbers of the individual weights and is independent of the size of the ground set. In contrast, we show that finding an optimal (0-best) solution requires exponential time.

关键词： nonlinear combinatorial optimization independence system approximation algorithm Frobenius numbers

来源：评论

学校读者我要写书评

暂无评论

Degree-bounded minimum spanning trees

引用

DISCRETE APPLIED MATHEMATICS 2009年第5期157卷 960-970页

作者： Jothi, Raja Raghavachari, Balaji NHLBI Lab Mol Immunol NIH Bethesda MD 20892 USA Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

Given n points in the Euclidean plane, the degree-A minimum spanning tree (MST) problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most delta. The problem is NP-hard for 2 <= delta <= 3, while the NP-hardness of the problem is open for delta = 4. The problem is polynomial-time solvable when delta = 5. By presenting an improved approximation analysis for Chan's degree-4 MST algorithm [T. Chan, Euclidean bounded-degree spanning tree ratios, Discrete & Computational Geometry 32 (2004) 177-194], we show that, for any arbitrary collection of points in the Euclidean plane, there always exists a degree-4 spanning tree of weight at most (root 2 + 2)/3 < 1.1381 times the weight of an MST. Published by Elsevier B.V.

关键词： Spanning trees Minimum spanning trees approximation algorithm Geometric optimization Network design

来源：评论

学校读者我要写书评

暂无评论

Cost-Effective Designs of Fault-Tolerant Access Networks in Communication Systems

引用

NETWORKS 2009年第4期53卷 382-391页

作者： Chen, Xujin Chen, Bo Univ Warwick Warwick Business Sch Coventry CV4 7AL W Midlands England Chinese Acad Sci Inst Appl Math Beijing 100190 Peoples R China

This article is concerned with the design of fault-tolerant access networks for cost-effective communications-deploying network links and service providers (SPs) at a minimum cost, while ensuring error tolerance ability via the ring architecture. Given a set of service subscribers (SSs) in an access network, we are required to determine the locations and capacities of service providers, and to establish network links in terms of rings connecting SSs to SPs. We pay link costs for ring constructions and pay management costs for selecting SPs with capacities sufficient to manage the SSs in their rings. The network design aims to minimize the sum of the link costs and the management costs. Two APX-hard problems in the general network design are studied in this article to address the scalable and modular features of SP capacities. Despite the logarithmic inapproximability that we show for one problem, constant-factor approximation algorithms are proposed to solve the other problem and its variant in quartic time. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 53(4),382-391 2009

关键词： communication network design approximation algorithm primal-dual schema

来源：评论

学校读者我要写书评

暂无评论

Truthful mechanisms for two-range-values variant of unrelated scheduling

引用

THEORETICAL COMPUTER SCIENCE 2009年第21-23期410卷 2196-2206页

作者： Yu, Changyuan Tsinghua Univ Inst Theoret Comp Sci Beijing 100084 Peoples R China

In this paper, we consider a restricted variant of the scheduling problem, where the machines are the strategic players. For this multi-parameter mechanism design problem, the only known truthful mechanisms use task independent allocation algorithms and only have approximation ratio O(m) [N. Nisan, & Ronen. algorithmic mechanism design (extended abstract), in: STOC'99: Proceedings of the thirty-first annual ACM symposium on Theory of computing, ACM, New York, NY, USA, 1999. pp. 129-140;A. Mu'alem, M. Schapira, Setting lower bounds on truthfulness: Extended abstract, in: SODA'07: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, Philadelphia. PA, USA, 2007, pp. 1143-1152;P. Lu, C. Yu, An improved randomized truthful mechanism for scheduling unrelated machines, in: 25th International Symposium on Theoretical Aspects of Computer Science, STACS, 2008, pp. 527-538;P. Lu, C. Yu, Randomized truthful mechanisms for scheduling unrelated machines, in: C.H. Papadimitriou, S. Zhang (Eds.), Proceedings of WINE, in: Lecture Notes in Computer Science, vol. 5385, Springer, 2008, pp. 402-413]. Lavi and Swamy first use the cycle monotone condition and design a 3-approximation truthful mechanism for a two value variant in [R. Lavi, C. Swamy, Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity, in: EC'07: Proceedings of the 8th ACM conference on Electronic commerce, ACM, New York, NY, USA, 2007, pp. 252-261], where the processing time of task j on machine i, say t(ij), can only be either a lower value L-j or a higher value H-j. We consider a generalized variant. where t(ij) lies in [L-j, L-j(1+epsilon)] boolean OR [H-j, H-j(1+epsilon)] and epsilon is a parameter satisfying some condition. We consider two special cases, case A when H-j/L-j > 2,for all(j) and case B when H-j/L-j <= 2, for all j, and give randomized truthful mechanisms with approximation ratio 4(1+epsilon) for both

关键词： Truthful mechanism approximation algorithm Scheduling

来源：评论

学校读者我要写书评

暂无评论

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

引用

ACM TRANSACTIONS ON algorithmS 2009年第3期5卷 1–24页

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

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

来源：评论

学校读者我要写书评

暂无评论

Enhancing Downlink Performance in Wireless Networks by Simultaneous Multiple Packet Transmission

引用

IEEE TRANSACTIONS ON COMPUTERS 2009年第5期58卷 706-718页

作者： Zhang, Zhenghao Yang, Yuanyuan Zhao, Miao Florida State Univ Dept Comp Sci Tallahassee FL 32306 USA SUNY Stony Brook Dept Elect & Comp Engn Stony Brook NY 11794 USA

In this paper, we consider using simultaneous Multiple Packet Transmission ( MPT) to improve the downlink performance of wireless networks. With MPT, the sender can send two compatible packets simultaneously to two distinct receivers and can double the throughput in the ideal case. We formalize the problem of finding a schedule to send out buffered packets in minimum time as finding a maximum matching problem in a graph. Since maximum matching algorithms are relatively complex and may not meet the timing requirements of real-time applications, we give a fast approximation algorithm that is capable of finding a matching at least 3/4 of the size of a maximum matching in O(vertical bar E vertical bar) time, where vertical bar E vertical bar is the number of edges in the graph. We also give analytical bounds for maximum allowable arrival rate, which measures the speedup of the downlink after enhanced with MPT, and our results show that the maximum arrival rate increases significantly even with a very small compatibility probability. We also use an approximate analytical model and simulations to study the average packet delay, and our results show that packet delay can be greatly reduced even with a very small compatibility probability.

关键词： Multiple packet transmission multiple-input multiple-output (MIMO) wireless LAN matching approximation algorithm maximum allowable arrival rate packet delay

来源：评论

学校读者我要写书评

暂无评论

Perfectness and imperfectness of unit disk graphs on triangular lattice points

引用

DISCRETE MATHEMATICS 2009年第9期309卷 2733-2744页

作者： Miyamoto, Y. Matsui, T. Sophia Univ Fac Sci & Technol Chiyoda Ku Tokyo 1028554 Japan Chuo Univ Fac Sci & Engn Bunkyo Ku Tokyo 1128551 Japan

Given a finite set of 2-dimensional points P c R 2 and a positive real d, a unit disk graph, denoted by (P. d), is an undirected graph with vertex set P such that two vertices are adjacent if and only if the Euclidean distance between the pair is less than or equal to d. Given a pair of non-negative integers m and n, P(m, n) denotes a subset of 2-dimensional triangular lattice points defined by P(m, n) (def) double under bar {(xe(1) + ye(2)) vertical bar x is an element of {0, 1, . . . , m - 1}, y is an element of {0, 1, . . . , n - 1}} where e(1) (def) double under bar (1, 0), e(2) (def) under bar (1/2, root-3/2). Let T-m,T-n(d) be a unit disk graph defined on a vertex set P(m, n) and a positive real d. Let T-m,n(k) be the kth power of T-m,T-n(1). In this paper, we show necessary and sufficient conditions that [for all m, T-m,T-n(d) is perfect] and/or [for all m, T-m,n(k) is perfect], respectively. These conditions imply polynomial time approximation algorithms for multicoloring (T-m,T-n(d), w) and (T-m,n(k), w). (C) 2008 Elsevier B.V. All rights reserved.

关键词： Perfect graph Unit disk graph Multicoloring Stable set Lattice graph approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A note on the minimum bounded edge-partition of a tree

引用

DISCRETE APPLIED MATHEMATICS 2009年第13期157卷 2958-2963页

作者： Dye, Shane Univ Canterbury Dept Management Christchurch 1 New Zealand

Minimum bounded edge-partition divides the edge set of a tree into the minimum number of disjoint connected components given a maximum weight for any component. It is an adaptation of the uniform edge-partition of a tree. An optimization algorithm is developed for this NP-hard problem, based on repeated bin packing of inter-related instances. The algorithm has linear running time for the class of 'balanced trees' common for the stochastic programming application which motivated investigation of this problem. Fast 2-approximation algorithms are formed for general instances by replacing the optimal bin packing with almost any bin packing heuristic. The asymptotic worst-case ratio of these approximation algorithms is never better than the absolute worst-case ratio of the bin packing heuristic used. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Tree Partition Optimization problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Deterministic Pivoting algorithms for Constrained Ranking and Clustering Problems

引用

MATHEMATICS OF OPERATIONS RESEARCH 2009年第3期34卷 594-620页

作者： van Zuylen, Anke Williamson, David P. Tsinghua Univ Inst Theoret Comp Sci Beijing 100084 Peoples R China Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14853 USA

We consider ranking and clustering problems related to the aggregation of inconsistent information, in particular, rank aggregation, (weighted) feedback arc set in tournaments, consensus and correlation clustering, and hierarchical clustering. Ailon et al. [Ailon, N., M. Charikar, A. Newman. 2005. Aggregating inconsistent information: Ranking and clustering. Proc. 37th Annual ACM Sympos. Theory Comput. (STOC '05), 684-693], Ailon and Charikar [Ailon, N., M. Charikar. 2005. Fitting tree metrics: Hierarchical clustering and phylogeny. Proc. 46th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS '05), 73-82], and Ailon [Ailon, N. 2007. Aggregation of partial rankings, p-ratings and top-m lists. Proc. 18th Annual ACM-SIAM Sympos. Discrete algorithms (SODA '07), 415-424] proposed randomized constant factor approximation algorithms for these problems, which recursively generate a solution by choosing a random vertex as "pivot" and dividing the remaining vertices into two groups based on the pivot vertex. In this paper, we answer an open question in these works by giving deterministic approximation algorithms for these problems. The analysis of our algorithms is simpler than the analysis of the randomized algorithms. In addition, we consider the problem of finding minimum-cost rankings and clusterings that must obey certain constraints (e. g., an input partial order in the case of ranking problems), which were introduced by Hegde and Jain [Hegde, R., K. Jain. 2006. Personal communication]. We show that the first type of algorithms we propose can also handle these constrained problems. In addition, we show that in the case of a rank aggregation or consensus clustering problem, if the input rankings or clusterings obey the constraints, then we can always ensure that the output of any algorithm obeys the constraints without increasing the objective value of the solution.

关键词： rank aggregation minimum feedback arc set in tournaments consensus clustering correlation clustering hierarchical clustering approximation algorithm derandomization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：