检索结果-南通市图书馆

Incremental algorithms for the maximum internal spanning tree problem

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2021年第5期64卷 77-84页

作者： Xianbin ZHU Wenjun LI Yongjie YANG Jianxin WANG School of Computer Science and Engineering Central South University Chair of Economic Theory Saarland University Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation Changsha University of Science and Technology

The maximum internal spanning tree(MIST) problem is utilized to determine a spanning tree in a graph G,with the maximum number of possible internal *** incremental maximum internal spanning tree(IMIST) problem is the incremental version of MIST whose feasible solutions are edge-sequences e,e,…,esuch that the first k edges form trees for all k ∈ [n-1].A solution’s quality is measured using maxopt(G,k)/|In(T)| with lower being ***,opt(G,k) denotes the number of internal vertices in a tree with k edges in G,which has the largest possible number of internal vertices,and |In(T)| is the number of internal vertices in the tree comprising the solution’s first k *** first obtained an IMIST algorithm with a competitive ratio of 2,followed by a 12/7-competitive algorithm based on an approximation algorithm for MIST.

关键词： maximum internal spanning tree incremental problem approximation algorithm competitive ratio

Semi-Online Algorithms for Scheduling with Machine Cost

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Journal of Computer Science & Technology 2006年第6期21卷 984-988页

作者：蒋义伟何勇 Faculty of Science Zhejiang Sci- Tech University Hangzhou 310018 P R. China Department of Mathematics Zhejiang University Hangzhou 310027 P.R. China

In this paper, we consider the following semi-online List Model problem with known total size. We are given a sequence of independent jobs with positive sizes, which must be assigned to be processed on machines. No machines are initially provided, and when a job is revealed the algorithm has the option to purchase new machines. By normalizing all job sizes and machine cost, we assume that the cost of purchasing one machine is 1. We further know the total size of all jobs in advance. The objective is to minimize the sum of the makespan and the number of machines to be purchased. Both non-preemptive and preemptive versions are considered. For the non-preemptive version, we present a new lower bound 6/5 which improves the known lower bound 1.161. For the preemptive version, we present an optimal semi-online algorithm with a competitive ratio of 1 in the case that the total size is not greater than 4, and an algorithm with a competitive ratio of 5/4 otherwise, while a lower bound 1.0957 is also presented for general case.

关键词： semi-online preemptive scheduling machine cost competitive ratio

Preemptive Semi-Online Scheduling with Tightly-Grouped Processing Times

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of Computer Science & Technology 2004年第6期19卷 733-739页

作者： YongHe Yi-WeiJiang DepartmentofMathematics ZhejiangUniversityHangzhou310027P.R.China StateKeyLabofCAD＆CG ZhejiangUniversityHangzhou310027P.R.China

This paper investigates a preemptive semi-online scheduling problem onm identical parallel machines wherem=2,3. It is assumed that all jobs have their processing times in betweenp andrp (p > 0,r ≥1). The goal is to minimize the makespan. Best possible algorithms are designed for anyr≥1 whenm=2,3. Keywords semi-online - scheduling - preemption - competitive ratio Regular PaperThis research is supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE. China, and the National Natural Science Foundation of China (Grant Nos. 10271110 and 60021201).Yong He received his B.S., M.S., and Ph.D. degrees all from Zhejiang University in 1989, 1992, 1996, respectively. He is currently a professor and Ph.D. supervisor at Department of Mathematics, Zhejiang University. His current research interests include combinatorial and network optimization, scheduling theory, computational biology, mathematical modeling, etc.Yi-Wei Jiang received his B.S. degree from Zhejiang University in 2002. He is currently a Ph.D. candidate of Zhejiang University. His current interests include scheduling theory and online algorithms.

关键词： semi-online scheduling preemption competitive ratio

competitive Analysis of Two Special Online Device Replacement Problems

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of Computer Science & Technology 2008年第2期23卷 203-213页

作者：辛春林马卫民杨磊 School of Economics and Management Tsinghua UniversityBeijing 100084China School of Economics and Management Tongji UniversityShanghai 200092China

When a new investment opportunity of purchasing a new device occurs, the investors must decide whether or not and when to buy this device in an online fashion. That is, the online player must make an investment decision while neither future demand for orders nor future investment opportunities are known. This problem which generalizes the basic leasing problem has been introduced by Azar et al., and then two special cases have been studied by Damaschke. In the so-called equal prices model a 2-competitive algorithm is devised and a 1.618 lower bound is given. Here we make use of an averaging technique and obtain a better tight lower bound of 2, in other words, this lower bound cannot be improved. Furthermore, another special case which only considers two-stage device replacement is studied in this paper. Accounting for the interest rate is an essential feature of any reasonable financial model. Therefore, we explore the two-stage model with and without the interest rate respectively. In addition, we introduce the risk-reward model to analyze this problem and improve the competitive ratio performance.

关键词： online algorithm device replacement competitive analysis competitive ratio

ON-LINE SCHEDULING OF UNIT TIME JOBS WITH REJECTION ON UNIFORM MACHINES

在线全文

学校读者我要写书评

暂无评论

Journal of Systems Science & Complexity 2008年第1期21卷 114-118页

作者： Shoupeng LIU Yuzhong ZHANG Binzhou Medical University Yantai 264003 China. ZHANG Institute of Operations Research Qufu Normal University Rizhao 276826 China.

The authors consider the problem of on-line scheduling of unit execution time jobs on uniform machines with rejection penalty. The jobs arrive one by one and can be either accepted and scheduled, or be rejected. The objective is to minimize the total completion time of the accepted jobs and the total penalty of the rejection jobs. The authors propose an on-line algorithm and prove that the competitive ratio is 1/2 （2 W √3） ≈ 1.86602.

关键词： competitive ratio on-line scheduling uniform machine.

A 16-competitive algorithm for hierarchical median problem

在线全文

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2014年第3期57卷 147-153页

作者： DAI WenQiang School of Management and Economics University of Electronic Science and Technology of China

The hierarchical median problem consists of finding a hierarchical assignment function sequence of solutions to the well-known k-median problems with growing *** sequence is said to be rcompetitive if the cost of each solution is at most r-times of the optimum cost of median problem with a same cardinality,where r is called the competitive *** the best algorithm available for this problem has competitive ratio *** this paper an improved algorithm is proposed with competitive ratio factor 16.

关键词： hierarchical location median algorithm competitive ratio

Online uniform machine covering with the known largest size

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Progress in Natural Science:Materials International 2007年第11期17卷 1271-1278页

作者： Cao Shunjuan1,2 and Tan Zhiyi1,3(1. Department of Mathematics, Zhejiang University, Hangzhou 310027, China 2. Department of Mathematics, Zhejiang Forestry University, Hangzhou 311300, China 3. State Key Laboratory of CAD & CG, Zhejiang University, Hangzhou 310027, China) Department of Mathematics Zhejiang University Hangzhou 310027 China Department of Mathematics Zhejiang Forestry University Hangzhou 311300 China State Key Laboratory of CAD and CG Zhejiang University Hangzhou 310027 China

This paper investigates the semi-online scheduling problem with the known largest size on two uniform machines. The objective is to maximize the minimum machine completion time. Both lower bounds and algorithms are given. Algorithms are optimal for the majority values of s≥1, where s is the speed ratio of the two machines. The largest gap between the competitive ratio and the lower bound is about 0.064. Moreover, the overall competitive ratio 2 matches the overall lower bound.

关键词： scheduling and covering uniform machine design and analysis of algorithm online competitive ratio

A Better Semi-online Algorithm for Q3/s_1=s_2≤s_3/C_(min) with the Known Largest Size

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2012年第1期28卷 111-116页

作者： Sheng-yi CAI Qi-fan YANG Department of Mathematics Zhejiang UniversityHangzhou 310027China School of Mathematics&Information Science Wenzhou UniversityWenzhou 325035China

This paper investigates the semi-online machine covering problem on three special uniform machines with the known largest size. Denote by sj the speed of each machine, j = 1, 2, 3. Assume 0 〈 s1 = s2 = r 〈 t = s3, and let s = t/r be the speed ratio. An algorithm with competitive ratio max（2, 3s＋6/s＋6 is presented. We also show the lower bound is at least max（2, 38 3s/s＋6）. For s ≤ 6, the algorithm is an optimal algorithm with the competitive ratio 2. Besides, its overall competitive ratio is 3 which matches the overall lower bound. The algorithm and the lower bound in this paper improve the results of Luo and Sun.

关键词： analysis of algorithms scheduling machine covering semi-online competitive ratio

Optimal Preemptive Online Algorithms for Scheduling with Known Largest Size on Two Uniform Machines

在线全文

学校读者我要写书评

暂无评论

Acta Mathematica Sinica,English Series 2007年第1期23卷 165-174页

作者： Yong HE Yi Wei JIANG Hao ZHOU Department of Mathematics Zhejiang University. Hangzhou 310027. P. R. China Faculty of Science Zhejiang Sci- Tech University Hangzhou 310018 P. R. China. Department of Mathematics Zhejiang University Hangzhou 310027. P. R. China Basic Course Department Zhejiang Shorten University Hangzhou 310015. P. R. China

In this paper, we consider the seml-online preemptive scheduling problem with known largest job sizes on two uniform machines. Our goal is to maximize the continuous period of time （starting from time zero） when both machines are busy, which is equivalent to maximizing the minimum machine completion time if idle time is not introduced. We design optimal deterministic semi-online algorithms for every machine speed ratio s ∈ [1, ∞）, and show that idle time is required to achieve the optimality during the assignment procedure of the algorithm for any s 〉（s^2 ＋ 3s ＋ 1）/（s^2 ＋ 2s ＋ 1）. The competitive ratio of the algorithms is （s^2 ＋ 3s ＋ 1）/（s^2 ＋ 2s ＋ 1）, which matches the randomized lower bound for every s ≥ 1. Hence randomization does not help for the discussed preemptive scheduling problem.

关键词： semi-online preemptive scheduling uniform machines competitive ratio