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

On-line Scheduling on Parallel Machines to Minimize the Makespan

Journal of Systems Science & Complexity 2016年第2期29卷 472-477页

作者： LI Songsong ZHANG Yuzhong School of Management Qufu Normal University

This paper considers two parallel machine scheduling problems, where the objectives of both problems are to minimize the makespan, and the jobs arrive over time, on two uniform machines with speeds 1 and s （s 〉 1）, and on m identical machines, respectively. For the first problem, the authors show that the on-line LPT algorithm has a competitive ratio of （1 ＋ √5）/2 ≈ 1.6180 and the bound is tight. Furthermore, the authors prove that the on-line LPT algorithm has the best possible competitive ratio if s ≥ 1.8020. For the second problem, the authors present a lower bound of （15 - √17）/8 ≈ 1.3596 on the competitive ratio of any deterministic on-line algorithm. This improves a previous result of 1.3473.

关键词： Lower bound on-line algorithm scheduling.

来源：评论

学校读者我要写书评

暂无评论

On-line scheduling of unit time jobs with rejection: minimizing the total completion time

引用

OPERATIONS RESEARCH LETTERS 2002年第6期30卷 415-420页

作者： Epstein, L Noga, J Woeginger, GJ Univ Twente Dept Math NL-7500 AE Enschede Netherlands Interdisciplinary Ctr Sch Comp & Med Sci IL-46150 Herzliyya Israel Calif State Univ Northridge Dept Comp Sci Northridge CA 91330 USA Graz Tech Univ Math Inst A-1080 Graz Austria

We consider on-line scheduling of unit time jobs on a single machine with job-dependent penalties. The jobs arrive on-line (one by one) and can be either accepted and scheduled, or be rejected at the cost of a penalty. The objective is to minimize the total completion time of the accepted jobs plus the sum of the penalties of the rejected jobs. We give an on-line algorithm for this problem with competitive ratio 1/2(2 + root3) approximate to 1.86602. Moreover, we prove that there does not exist an on-line algorithm with competitive ratio better than 1.63784. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： scheduling on-line algorithm competitive analysis worst-case bounds

来源：评论

学校读者我要写书评

暂无评论

Robust principal component analysis with adaptive selection for tuning parameters

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2004年 5卷 453-471页

作者： Higuchi, I Eguchi, S Hiroshima Univ Dept Appl Math Higashihiroshima 7398527 Japan Grad Univ Adv Studies Minato Ku Tokyo 1068569 Japan Inst Stat Math Minato Ku Tokyo 1068569 Japan

The present paper discusses robustness against outliers in a principal component analysis (PCA). We propose a class of procedures for PCA based on the minimum psi principle, which unifies various approaches, including the classical procedure and recently proposed procedures. The reweighted matrix algorithm for off-line data and the gradient algorithm for on-line data are both investigated with respect to robustness. The reweighted matrix algorithm is shown to satisfy a desirable property with local convergence, and the on-line gradient algorithm is shown to satisfy an asymptotical stability of convergence. Some procedures in the class involve tuning parameters, which control sensitivity to outliers. We propose a shape-adaptive selection rule for tuning parameters using K-fold cross validation.

关键词： K-fold cross validation on-line algorithm reweighted matrix algorithm influence function data contamination

来源：评论

学校读者我要写书评

暂无评论

HYBRID NEXT-FIT algorithm FOR THE TWO-DIMENSIONAL RECTANGLE BIN-PACKING PROBLEM

引用

COMPUTING 1987年第3期39卷 201-217页

作者： FRENK, JBG GALAMBOS, G JOZSEF ATTILA UNIV KALMAR LAB CYBERNETH-6720 SZEGEDHUNGARY

We present a new approximation algorithm for the two-dimensional bin-packing problem. The algorithm is based on two one-dimensional bin-packing algorithms. Since the algorithm is of next-fit type it can also be used for those cases where the output is required to be on-line (e. g. if we open an new bin we have no possibility to pack elements into the earlier opened bins). We give a tight bound for its worst-case and show that this bound is a parameter of the maximal sizes of the items to be packed. Moreover, we also present a probabilistic analysis of this algorithm.

关键词： Two-dimensional packing bin-packing heuristic algorithm worst-case analysis probabilistic analysis on-line algorithm

来源：评论

学校读者我要写书评

暂无评论

Robot map verification of a graph world

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2001年第4期5卷 383-395页

作者： Deng, X Milios, E Mirzaian, A York Univ Dept Comp Sci N York ON M3J 1P3 Canada

In the map verification problem, a robot is given a (possibly incorrect) map M of the world G with its position and orientation indicated on the map. The task is to find out whether this map, for the given robot position and its orientation in the map, is correct for the world G. We consider the world model of a graph G = (V-G, E-G) in which, for each vertex, edges incident to the vertex are ordered cyclically around that vertex. (This also holds for the map M = (V-M, E-M).) The robot can traverse edges and enumerate edges incident on the current vertex, but it cannot distinguish vertices (and edges) from each other. To solve the verification problem, the robot uses a portable edge marker, that it can put down at an edge of the graph world G and pick up later as needed. The robot can recognize the edge marker when it encounters it in the world G. By reducing the verification problem to an exploration problem, verification can be completed in O(\V-G\ x \E-G\) edge traversals (the mechanical cost) with the help of a single vertex marker which can be dropped and picked up at vertices of the graph world (G. Dudek, M. Jenkin, E. Milios, and D. Wilkes, IEEE Trans. on Robotics and Automation, vol. 7, pp. 859-865, 1991;Robotics and Autonomous Systems, vol. 22(2), pp. 159-178, 1997). In this paper, we show a strategy that verifies a map in O(\V-M\) edge traversals only, using a single edge marker, when M is a plane embedded graph, even though G may not be planar (e.g., G may contain overpasses, tunnels, etc.).

关键词： robot exploration and map verification on-line algorithm topological graph face tracing

来源：评论

学校读者我要写书评

暂无评论

Fast Sequential Importance Sampling to Estimate the Graph Reliability Polynomial

引用

algorithmICA 2014年第4期68卷 916-939页

作者： Harris, David G. Sullivan, Francis Beichl, Isabel US Dept Def Washington DC 20305 USA IDA Ctr Comp Sci Bowie MD USA NIST Gaithersburg MD 20899 USA

The reliability polynomial of a graph counts its connected subgraphs of various sizes. algorithms based on sequential importance sampling (SIS) have been proposed to estimate a graph's reliability polynomial. We develop an improved SIS algorithm for estimating the reliability polynomial. The new algorithm runs in expected time O(mlogn alpha(m,n)) at worst and a parts per thousand m in practice, compared to I similar to(m (2)) for the previous algorithm. We analyze the error bounds of this algorithm, including comparison to alternative estimation algorithms. In addition to the theoretical analysis, we discuss methods for estimating the variance and describe experimental results on a variety of random graphs.

关键词： Reliability polynomial Graph Fully-polynomial relative approximation scheme fpras Network reliability Sequential importance sampling on-line algorithm Incremental algorithm

来源：评论

学校读者我要写书评

暂无评论

The impact of heterogeneity on master-slave scheduling

引用

PARALLEL COMPUTING 2008年第3期34卷 158-176页

作者： Pineau, Jean-Francois Robert, Yves Vivien, Frederic INRIA Paris France Ecole Normale Super Lyon F-69364 Lyon France Univ Lyon Lyon France UCBL INRIA CNRS ENS LyonUMR 5668LIP Lab Lyon France

In this paper, we assess the impact of heterogeneity on scheduling independent tasks on master-slave platforms. We assume a realistic one-port model where the master can communicate with a single slave at any time. We target both on-line and off-line scheduling problems, and we focus on simpler instances where all tasks have the same size. While such on-line problems can be solved in polynomial time on homogeneous platforms, we show that there does not exist any optimal deterministic algorithm for heterogeneous platforms. Whether the source of heterogeneity comes from computation speeds, or from communication bandwidths, or from both, we establish lower bounds on the competitive ratio of any deterministic algorithm. We provide such bounds for the most important objective functions: the minimization of the makespan (or total execution time), the minimization of the maximum response time (difference between completion time and release time), and the minimization of the sum of all response times. Altogether, we obtain nine theorems which nicely assess the impact of heterogeneity on on-line scheduling. For off-line scheduling, we prove several result for problems with release dates, either optimality or NP-hardness. These theoretical contributions are complemented on the practical side by the implementation of several heuristics on a small but fully heterogeneous MPI platform. Our results show the superiority of those heuristics which fully take into account the relative capacity of the communication links. (C) 2008 Elsevier B.V. All rights reserved.

关键词： master-slave scheduling on-line algorithm off-line algorithm

来源：评论

学校读者我要写书评

暂无评论

On-line disjoint path routing for network capacity maximization in energy-constrained ad hoc networks

引用

AD HOC NETWORKS 2007年第2期5卷 272-285页

作者： Liang, Weifa Liu, Yuzhen Australian Natl Univ Dept Comp Sci Canberra ACT 0200 Australia

In this paper we consider on-line disjoint path routing in energy-constrained ad hoc networks. The objective is to maximize the network capacity, i.e. maximize the number of messages routed successfully by the network without any knowledge of future disjoint path connection request arrivals and generation rates. Specifically, in this paper we first present two centralized on-line algorithms for the problem. One is based on maximizing local network lifetime, which aims to minimize the transmission energy consumption, under the constraint that the local network lifetime is no less than gamma times of the optimum after the realization of each disjoint path connection request, where gamma is constant with 0 < gamma <= 1. Another is based oil the exponential function of energy utilization at nodes, and the competitive ratio of this latter algorithm is also analyzed if admission control mechanism is employed. We then conduct extensive experiments by simulations to analyze the performance of the proposed algorithms, in terms of network capacity, network lifetime, and the transmission energy consumption for each disjoint path connection request. The experimental results show that the proposed algorithms outperform those existing algorithms that do not take into account the power load balancing at nodes in terms of maximizing the network capacity. (c) 2005 Elsevier B.V. All rights reserved.

关键词： Wireless communication network on-line algorithm Power awareness Ad hoc networks Energy consumption optimization Disjoint path routing Load-balanced routing Network capacity

来源：评论

学校读者我要写书评

暂无评论

On-line construction of two-dimensional suffix trees in O(n² log n) time

引用

algorithmICA 2007年第2期48卷 173-186页

作者： Na, Joong Chae Giancarlo, Raffaele Park, Kunsoo Seoul Natl Univ Sch Comp Sci & Engn Seoul 151742 South Korea Univ Palermo Dipartimento Matemat & Applicaz I-90123 Palermo Italy

The two-dimensional suffix tree of an n x n square matrix A is a compacted trie that represents all square submatrices of A [11]. For the off-line case, i.e., A is given in advance to the algorithm, it is known how to build it in optimal time, for any type of alphabet size [11], [18]. Motivated by applications in Image Compression [22], Giancarlo and Guaiana [14] considered the on-line version of the two-dimensional suffix tree and presented an 0(n(2) log(2) n)-time algorithm, which we refer to as GG. That algorithm is a nontrivial generalization of Ukkonen's on-line algorithm for standard suffix trees [23]. The main contribution in this paper is an 0(log n) factor improvement in the time complexity of the GG algorithm, making it optimal for unbounded alphabets [9]. Moreover, the ideas presented here also lead to a major simplification of the GG algorithm. Technically, we are able to preserve most of the structure of the original GG algorithm, by reducing a computational bottleneck to a primitive operation, i.e., comparison of Lcharacters, which is here implemented in constant time rather than 0 (log n) time as in GG. However, preserving that structure comes at a price. Indeed, in order to make everything work, we need a careful reorganization of another fundamental algorithm: Weiner's algorithm for the construction of standard suffix trees [24]. Specifically, here we provide a version of that algorithm which takes linear time and works on-line and concurrently over a set of strings.

关键词： two-dimensional suffix tree on-line algorithm index data structures

来源：评论

学校读者我要写书评

暂无评论

Optimal algorithms for single-machine scheduling with rejection to minimize the makespan

引用

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS 2011年第2期130卷 153-158页

作者： Lu, Lingfa Ng, C. T. Zhang, Liqi Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Zhengzhou Univ Dept Math Zhengzhou 450001 Henan Peoples R China

in this paper we consider the single-machine scheduling problem with rejection. Each job has an arrival time, a processing time and a rejection penalty. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. First, we present a polynomial-time algorithm for the off-line problem when split is allowed. Second, for the on-line problem with arbitrary arrival times, we provide a determined on-line algorithm with the best-possible competitive ratio 2. Finally, for the on-line problem with at most two distinct arrival times, we provide a determined on-line algorithm with the best-possible competitive ratio (root 5 + 1) approximate to 1.618. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Scheduling Rejection penalty on-line algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：