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

Faster algorithms for Semi-Matching Problems

ACM TRANSACTIONS ON algorithmS 2014年第3期10卷 14-14页

作者： Fakcharoenphol, Jittat Laekhanukit, Bundit Nanongkai, Danupon Kasetsart Univ Dept Comp Engn Bangkok 10900 Thailand McGill Univ Sch Comp Sci Montreal PQ H3A 0E9 Canada Univ Vienna Fac Comp Sci A-1090 Vienna Austria

We consider the problem of finding semi-matching in bipartite graphs, which is also extensively studied under various names in the scheduling literature. We give faster algorithms for both weighted and unweighted cases. For the weighted case, we give an O(nmlog n)-time algorithm, where n is the number of vertices and ni is the number of edges, by exploiting the geometric structure of the problem. This improves the classical O(n(3))-time algorithms by Horn [1973] and Bruno et al. [1974b]. For the unweighted case, the bound can be improved even further. We give a simple divide-and-conquer algorithm that runs in O(root nmlog n) time, improving two previous O(nm)-time algorithms by Abraham [2003] and Harvey et al. [2003, 20061. We also extend this algorithm to solve the Balanced Edge Cover problem in O(root nmlog n) time, improving the previous O(nm)-time algorithm by Harada et al. [2008].

关键词： Semi-matching scheduling combinatorial optimization design and analysis of algorithm

来源：评论

学校读者我要写书评

暂无评论

ONLINE AND SEMI-ONLINE SCHEDULING ON CAPACITATED TWO-PARALLEL MACHINES

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2011年第2期28卷 163-182页

作者： Zhang, An Jiang, Yiwei Tan, Zhiyi Zhejiang Univ Dept Math State Key Lab CAD & CG Hangzhou 310027 Peoples R China Zhejiang Sci Tech Univ Key Lab Adv Textile Mat & Mfg Technol Hangzhou 310018 Peoples R China

In this paper, we investigate the capacitated two-parallel machines scheduling problem, where one machine is only available for a special period of time after which it can no longer process any job while the other machine is continuously available. Our objective is to minimize the completion time of the machine which is continuously available. The offline version of the problem is equivalent to the minimization version of the Subset-Sum problem. We first show the lower bound of the online version is infinite. We also consider the semi-online version with known the total job processing time in advance, for which both lower bound and semi-online algorithms are given.

关键词： Scheduling design and analysis of algorithm competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Machine covering with combined partial information

引用

JOURNAL OF STATISTICAL PLANNING AND INFERENCE 2010年第8期140卷 2351-2354页

作者： Wu, Yong Yang, Qifan Huang, Yikun Zhejiang Univ Dept Math Hangzhou 310027 Zhejiang Peoples R China Zhejiang Univ Ningbo Inst Technol Dept Fundamental Educ Ningbo 315100 Zhejiang Peoples R China Linyi Normal Univ Dept Math Linyi 276000 Peoples R China

Machine scheduling and covering problems may occur in many applications such as load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc. In this paper we study machine covering problems with combined partial information on m parallel identical machines. We consider sequences where the processing time of all jobs are at most 1/k times of the optimal value (for an integer k). For the case where the optimal value is not known in advance, we show that IS algorithm is optimal. For the case where the optimal value is known in advance, we give lower bounds and present semi-online algorithms. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Scheduling design and analysis of algorithm Semi-online Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Optimal Semi-online Scheduling algorithm on three machines with non-simultaneous machine available times

Optimal Semi-online Scheduling Algorithm on three machines w...

引用

2nd International Conference on Modelling and Simulation

作者： Huang, Yikun Wu, Yong Linyi Normal Univ Dept Math Linyi 276005 Peoples R China

This paper investigates the problem of semi-online scheduling on three parallel identical machines with non-simultaneous machine available times. We prove that if the total processing time of all jobs and the largest ... 详细信息

ISBN: (纸本)9781846260667

关键词： scheduling semi-online design and analysis of algorithm competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Online scheduling with reassignment

引用

OPERATIONS RESEARCH LETTERS 2008年第2期36卷 250-254页

作者： Tan, Zhiyi Yu, Shaohua Zhejiang Univ Dept Math State Key Lab CAD & CG Hangzhou 310027 Peoples R China

This paper studies online scheduling problems with reassignment on two identical machines. We can reassign some jobs under certain rules after all the jobs have been assigned. Three different versions are studied and ... 详细信息

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

来源：评论

学校读者我要写书评

暂无评论

Linear Time algorithms for Parallel Machine Scheduling

引用

Acta Mathematica Sinica,English Series 2007年第1期23卷 137-146页

作者： Zhi Yi TAN Yong HE Department of Mathematics State Key Lab of CAD & CG Zhejiang University Hangzhou 310027 P. R. China Department of Mathematics Zhejiang University Hangzhou 310027 P. R. China

This paper addresses linear time algorithms for parallel machine scheduling problems. We introduce a kind of threshold algorithms and discuss their main features. Three linear time threshold algorithm classes DT, PT and DTm are studied thoroughly. For all classes, we study their best possible algorithms among each class. We also present their application to several scheduling problems, The new algorithms are better than classical algorithms in time complexity and/or worst-case ratio. Computer-aided proof technique is used in the proof of main results, which greatly simplifies the proof and decreases case by case analysis.

关键词： scheduling design and analysis of algorithm worst-case ratio computer-aided proof

来源：评论

学校读者我要写书评

暂无评论

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 & 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

来源：评论

学校读者我要写书评

暂无评论

Semi-online machine covering on two uniform machines with known total size

引用

COMPUTING 2006年第4期78卷 369-378页

作者： Tan, Z. Y. Cao, S. J. Zhejiang Univ Dept Math State Key Lab CAD & CG Hangzhou 310027 Peoples R China Zhejiang Forestry Univ Dept Math Hangzhou 311300 Peoples R China

This paper investigates semi-online scheduling problem with known total size on two uniform machines for maximizing the minimum machine completion time. Lower bounds and optimal algorithms for every s >= 1 are given, where s is the speed ratio of two machines. Both the overall competitive ratio and the competitive ratio for s>1+root 5/2 are strictly smaller than those of the optimal algorithms of the corresponding semi-online scheduling problem with known optimal value. It indicates that two related semi-online problems are different.

关键词： scheduling design and analysis of algorithm competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Optimal sequential and parallel algorithms to compute all cut vertices on trapezoid graphs

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2004年第1期27卷 95-113页

作者： Hota, M Pal, M Pal, TK Vidyasagar Univ Dept Appl Math Oceanol & Comp Programming Midnapore 721102 India

In this paper, a sequential algorithm is presented to find all cut-vertices on trapezoid graphs. To every trapezoid graph G there is a corresponding trapezoid representation. If all the 4n corner points of n trapezoids, in a trapezoid representation of a trapezoid graph G with n vertices, are given, then the proposed sequential algorithm runs in O(n) time. Parallel implementation of this algorithm can be done in O( log n) time using O(n/log n) processors on an EREW PRAM model.

关键词： trapezoid graph cut vertex block design and analysis of algorithm parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Ordinal scheduling problem and its asymptotically optimal algorithms on parallel machine system

引用

Science in China(Series F) 2004年第2期47卷 161-169页

作者： TAN Zhiyi1,2 & HE Yong1 1. Department of Mathematics, Zhejiang University, Hangzhou 310027, China (email: tanzy@math.zju. *** heyong@math.zju.***) 2. State Key Laboratory of CAD & CG, Zhejiang University, Hangzhou 310027, China 1. Department of Mathematics Zhejiang University 310027 Hangzhou China 2. State Key Laboratory of CAD & CG Zhejiang University 310027 Hangzhou China

Focusing on the ordinal scheduling problem on a parallel machine system, we discuss the background of ordinal scheduling and the motivation of ordinal algorithms. In addition, for the ordinal scheduling problem on identical parallel machines with the objective to maximize the minimum machine load, we then give two asymptotically optimal algorithm classes which have worst-case ratios very close to the upper bound of the problem for any given m. These results greatly improve the results proposed by He Yong and Tan Zhiyi in 2002.

关键词： scheduling design and analysis of algorithm worst-case ratio.

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：