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

Online Allocation of Communication and Computation Resources for Real-Time Multimedia Services

IEEE TRANSACTIONS ON MULTIMEDIA 2013年第3期15卷 670-683页

作者： Liao, Jun Chou, Philip A. Yuan, Chun Hu, Yusuo Zhu, Wenwu China Mobile Commun Corp Informat Secur Ctr Beijing 100053 Peoples R China Microsoft Res Redmond WA 98052 USA Tsinghua Univ Dept Comp Sci & Technol Beijing 100084 Peoples R China Google Mountain View CA 94043 USA

In a network, the location of the node on which a service is computed is inextricably linked to the locations of the paths through which the service communicates. Hence, service location can have a profound effect on quality of service, especially for communication-centric applications such as real-time multimedia. In this paper, we propose an online algorithm that uses pricing to consider server load, route congestion, and propagation delay jointly when locating servers and routes for real-time multimedia services in a network with fixed computing and communication capacities. The algorithm is online in the sense that it is able to sequentially allocate resources for services with long and unknown duration as demands arrive, without the benefit of looking ahead to later demands. By formulating the problem as one of lowest cost subgraph packing, we prove that our algorithm is nevertheless C-competitive with the optimal algorithm that looks ahead, meaning that our performance is within a constant factor C of optimal, as measured by the total number of service demands satisfied, or total user utility. Using mixing services as an example, we show through experimental results that our algorithm can adapt to cross traffic and automatically route around congestion and failure of nodes and edges, can reduce latency by 40% or more, and can pack 20% more sessions or alternatively can double the number of sessions before significant call rejection, compared with conventional approaches.

关键词： approximation algorithm congestion pricing mixing multimedia services online algorithm primal-dual algorithm resource allocation subgraph packing

来源：评论

学校读者我要写书评

暂无评论

Bin covering with a general profit function: approximability results

引用

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2013年第4期21卷 805-816页

作者： Benko, Attila Dosa, Gyoergy Tuza, Zsolt Univ Pannonia Dept Math Veszprem Hungary Hungarian Acad Sci Alfred Renyi Inst Math Budapest Hungary Univ Pannonia Dept Comp Sci & Syst Technol Veszprem Hungary

In the recent paper (BenkA et al. 2010) we introduced a new problem that we call Bin Packing/Covering with Delivery, or BP/CD for short. Mainly we mean under this expression that we look for not only a good, but a "good and fast" packing or covering. In the present paper we investigate the offline case. For the analysis, a novel view on "offline optimum" is introduced, which appears to be relevant concerning all problems where a final solution is ordering-dependent. We prove that if the item sizes are not allowed to be arbitrarily close to zero, then an optimal offline solution can be found in polynomial time. On the other hand, for unrestricted problem instances, no polynomial-time algorithm can achieve an asymptotic approximation ratio better than 6/7 if P not equal NP.

关键词： Bin covering Polynomial-time exact algorithm approximation algorithm Non-approximability

来源：评论

学校读者我要写书评

暂无评论

Modeling and algorithms for QoS-Aware Service Composition in Virtualization-Based Cloud Computing

引用

IEICE TRANSACTIONS ON COMMUNICATIONS 2013年第1期E96B卷 10-19页

作者： Huang, Jun Liu, Yanbing Yu, Ruozhou Duan, Qiang Tanaka, Yoshiaki Chongqing Univ Posts & Telecom Sch Commun & Informat Engn Chongqing 400065 Peoples R China Chongqing Univ Posts & Telecom Sch Comp Sci Chongqing 400065 Peoples R China Beijing Univ Posts & Telecom Sch Comp Sci Beijing 100876 Peoples R China Penn State Univ Abington Coll Informat Sci & Technol Dept Abington PA 19001 USA Waseda Univ Global Informat & Telecommun Inst Tokyo 1690051 Japan

Cloud computing is an emerging computing paradigm that may have a significant impact on various aspects of the development of information infrastructure. In a Cloud environment, different types of network resources need to be virtualized as a series of service components by network virtualization, and these service components should be further composed into Cloud services provided to end users. Therefore Quality of Service (QoS) aware service composition plays a crucial role in Cloud service provisioning. This paper addresses the problem on how to compose a sequence of service components for QoS guaranteed service provisioning in a virtualization-based Cloud computing environment. The contributions of this paper include a system model for Cloud service provisioning and two approximation algorithms for QoS-aware service composition. Specifically, a system model is first developed to characterize service provisioning behavior in virtualization-based Cloud computing, then a novel approximation algorithm and a variant of a well-known QoS routing procedure are presented to resolve QoS-aware service composition. Theoretical analysis shows that these two algorithms have the same level of time complexity. Comparison study conducted based on simulation experiments indicates that the proposed novel algorithm achieves better performance in time efficiency and scalability without compromising quality of solution. The modeling technique and algorithms developed in this paper are general and effective;thus are applicable to practical Cloud computing systems.

关键词： cloud service provisioning network virtualization quality of service service composition approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A PTAS for the disk cover problem of geometric objects

引用

OPERATIONS RESEARCH LETTERS 2013年第5期41卷 552-555页

作者： de Rezende, Pedro J. Miyazawa, Flavio K. Sasaki, Anderson T. Univ Estadual Campinas Inst Comp Campinas SP Brazil

We present PTASs for the disk cover problem: given geometric objects and a finite set of disk centers, minimize the total cost for covering those objects with disks under a polynomial cost function on the disks' radii. We describe the first FPTAS for covering a line segment when the disk centers form a discrete set, and a PTAS for when a set of geometric objects, described by polynomial algebraic inequalities, must be covered. The latter result holds for any dimension. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Disk cover approximation algorithm Computational geometry Wireless networks Sensor coverage

来源：评论

学校读者我要写书评

暂无评论

Approximability issues of guarding a set of segments

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2013年第8期90卷 1653-1667页

作者： Brimkov, Valentin E. SUNY Coll Buffalo Dept Math Buffalo NY 14222 USA

In this paper we consider the following problem: given a finite set of straight-line segments S in R-2, find minimum in size set V of points on the segments, such that each segment of S contains at least one point in V. We call this problem guarding a set of segments (GSS). GSS is a special case of the set cover problem where the given family of subsets can be taken as a set of intersections of the straight-line segments in S. Requiring that the given subsets can be interpreted geometrically this way is a major restriction on the input, yet it has been shown that the problem is still strongly NP-complete [V.E. Brimkov, A. Leach, M. Mastroianni, and J. Wu, Guarding a set of line segments in the plane, Theor. Comput. Sci. 412 (2011), pp. 1313-1324]. In light of this result, in Brimkov et al. [Experimental studies on approximation algorithms for guarding sets of line segments, in Advances in Visual Computing, G. Bebis, R. Boyle, B. Parvin, D. Koracin, R. Chung, R. Hammoud, M. Hussain, T. Kar-Han, R. Crawfis, D. Thalmann, D. Kao, and L. Avila, eds., ISVC 2010, Part I, Lecture Notes in Computer Science, Vol. 6453, Springer, Berlin, 2010, pp. 592-601;V.E. Brimkov, A. Leach, M. Mastroianni, and J. Wu, approximation algorithms for a geometric set cover problem, Discrete Appl. Math. 160 (2012), pp. 1039-1052] the GSS approximability was studied both theoretically and experimentally. Here we continue these investigations. In particular, we obtain conditions under which GSS admits good approximation.

关键词： guarding a set of segments set cover vertex cover NP-complete problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Scheduling tool changes and special jobs on a single machine to minimize makespan

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2013年第2期41卷 299-304页

作者： Xu, Dehua Liu, Min Yin, Yungqiang Hao, Jinghua E China Inst Technol State Key Lab Breeding Base Nucl Resources & Envi Nanchang 330013 Jiangxi Peoples R China E China Inst Technol Sch Sci Fuzhou 344000 Jiangxi Peoples R China Tsinghua Univ Dept Automat Beijing 100084 Peoples R China

This paper considers a variation of the classical single machine scheduling problem with tool changes. In the variation, two sets of jobs, namely special jobs and normal jobs, are considered. By special jobs, we mean that each special job must be processed within the first prefixed time units of a tool life. To solve the scheduling problem with small size and moderate size, we propose two mathematical programming models. To solve the scheduling problem with large size, we propose three sets of algorithms and focus on the performance of six algorithms based on the studies of a new bin packing problem. Worst-case analysis is conducted. Numerical experiment shows that each of the six algorithms can solve instances with up to 5000 jobs in about 0.5 s with an average relative error less than 4%. (C) 2012 Elsevier Ltd. All rights reserved.

关键词： Scheduling Mathematical programming model Bin packing approximation algorithm Tool change

来源：评论

学校读者我要写书评

暂无评论

Asymptotics of the Chromatic Number for Quasi-Line Graphs

引用

JOURNAL OF GRAPH THEORY 2013年第3期73卷 327-341页

作者： King, Andrew D. Reed, Bruce Simon Fraser Univ Dept Math Burnaby BC V5A 1S6 Canada Simon Fraser Univ Dept Comp Sci Burnaby BC V5A 1S6 Canada McGill Univ Sch Comp Sci Montreal PQ Canada

As proved by Kahn, the chromatic number and fractional chromatic number of a line graph agree *** is, for any line graph G, we have (G)(1+o(1))f(G). We extend this result to quasi-line graphs, an important subclass of claw-free graphs. Furthermore, we prove that we can construct a coloring that achieves this bound in polynomial time, giving us an asymptotic approximation algorithm for the chromatic number of quasi-line graphs (C) 2012 Wiley Periodicals,

关键词： graph coloring fractional graph coloring quasi-line graph chromatic number approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A scheduling model for the refurbishing process in recycling management

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2013年第23-24期51卷 7120-7139页

作者： Cheng, T. C. E. Lin, B. M. T. Tian, Y. Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Natl Chiao Tung Univ Inst Informat Management Dept Informat Management & Finance Hsinchu Taiwan

We propose from the perspective of operations scheduling a novel model of the refurbishing process in recycling management. We model the refurbishing process as a two-stage flowshop that dismantles products into parts in stage one and refurbishes the parts on dedicated machines in stage two. The model also features that the performance measure of a schedule is defined by operation-based completion times, which is different from the job-based performance measures traditionally adopted in the scheduling literature. We analyse the optimality properties and computational complexity of some special cases of the problem. We derive lower bounds on the optimal solution based on a disaggregation technique and the assignment problem, and develop dominance rules incorporating estimates of the effects of partial schedules on unscheduled jobs. We present a heuristic approach, based on LP relaxation, and analyse its performance ratio. We also develop two metaheuristic algorithms, based on iterated local search and ant colony optimisation, to produce approximate solutions. The results of computational experiments show that the metaheuristics generate better solutions than the simple weighted shortest processing time dispatching rule, and the NEH-based and CDS-based algorithms, which are commonly deployed to treat the classical two-machine flowshop scheduling problem.

关键词： refurbishing flowshop operation-based performance measure weighted total completion time approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Computation of the optimal value function in time-dependent networks

引用

NETWORKS 2013年第2期62卷 105-124页

作者： Kluge, Sebastian Reif, Konrad Brokate, Martin Tech Univ Munich Fak Math D-81539 Munich Germany Tech Univ Munich Fak Math D-85747 Garching Germany

We consider a time-dependent network with a continuous-time variable, in which time constraints are imposed both on the arrival times and on the waiting times at the nodes. Under certain continuity assumptions, we prove the existence of optimal paths, and we show that the optimal value function is lower-semicontinuous. We present an exact solution algorithm, which computes both the optimal value function and the corresponding optimal paths. This algorithm is based on a Dijkstra-like interpretation of a decreasing order of time algorithm, which allows the generalization of this method to a heuristic search algorithm. Moreover, we present an approximation procedure for the computation of the optimal value function and the corresponding optimal paths in a time-dependent first-in first-out (FIFO) network. This method allows for the iterative construction of paths of monotone decreasing cost, starting from a path that is computable in polynomial time. We prove the correctness and termination of both algorithms. (c) 2013 Wiley Periodicals, Inc.

关键词： deterministic network models shortest path problem dynamic programming analysis of algorithms approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Partitioning Trees with Supply, Demand and Edge-Capacity

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2013年第6期E96A卷 1036-1043页

作者： Kawabata, Masaki Nishizeki, Takao Kwansei Gakuin Univ Sch Sci & Technol Sanda 6691337 Japan

Let T be a given tree. Each vertex of T is either a supply vertex or a demand vertex, and is assigned a positive number, called the supply or demand. Each demand vertex v must be supplied an amount of "power," equal to the demand of a, from exactly one supply vertex through edges in T. Each edge is assigned a positive number called the capacity. One wishes to partition T into subtrees by deleting edges from T so that each subtree contains exactly one supply vertex whose supply is no less than the sum of all demands in the subtree and the power flow through each edge is no more than capacity of the edge. The "partition problem" is a decision problem to ask whether T has such a partition. The "maximum partition problem" is an optimization version of the partition problem. In this paper, we give three algorithms for the problems. First is a linear-time algorithm for the partition problem. Second is a pseudo-polynomial-time algorithm for the maximum partition problem. Third is a fully polynomial-time approximation scheme (FPTAS) for the maximum partition problem.

关键词： tree maximum partition problem supply demand edge-capacity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：