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

Dynamically maintaining split graphs

DISCRETE APPLIED MATHEMATICS 2009年第9期157卷 2057-2069页

作者： Heggernes, Pinar Mancini, Federico Univ Bergen Dept Informat N-5020 Bergen Norway

We present an algorithm that supports operations for modifying a split graph by adding edges or vertices and deleting edges, such that after each modification the graph is repaired to become a split graph in a minimal way. In particular, if the graph is not split after the modification, the algorithm computes a minimal, or if desired even a minimum, split completion or deletion of the modified graph. The motivation for such operations is similar to the motivation for fully dynamic algorithms for particular graph classes. In our case we allow all modifications to the graph and repair, rather than allowing only the modifications that keep the graph split. Fully dynamic algorithms of the latter kind are known for split graphs [L Ibarra, Fully dynamic algorithms for chordal graphs and split graphs, Technical Report DCS-262-IR, University of Victoria, Canada, 2000]. Our results can be used to design linear time algorithms for some recognition and completion problems, where the input is supplied in an on-line fashion. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Split graphs Dynamic algorithms on-line algorithms Minimal split completions

来源：评论

学校读者我要写书评

暂无评论

On-line extensible bin packing with unequal bin sizes

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2009年第1期11卷 141-152页

作者： Ye, Deshi Zhang, Guochuan Zhejiang Univ Coll Comp Sci Hangzhou 310027 Peoples R China

In the extensible bin packing problem we are asked to pack a set of items into a given number of bins, each with an original size. However, the original bin sizes can be extended if necessary. The goal is to minimize the total size of the bins. We consider the problem with unequal (original) bin sizes and give the complete analysis on a list scheduling algorithm (LS). Namely we present tight bounds of LS for every collection of original bin sizes and every number of bins. We further show better on-line algorithms for the two-bin case and the three-bin case. Interestingly, it is proved that the on-line algorithms have better competitive ratios for unequal bins than for equal bins. Some variants of the problem are also discussed.

关键词： on-line algorithms extensible bin packing competitive ratio

来源：评论

学校读者我要写书评

暂无评论

ON THE POWER OF RANDOMIZATION FOR JOB SHOP SCHEDULING WITH k-UNITS LENGTH TASKS

引用

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2009年第2期43卷 189-207页

作者： Moemke, Tobias ETH Dept Informat CH-8092 Zurich Switzerland

In the job shop scheduling problem k-units-J(m), there are m machines and each machine has an integer processing time of at most k time units. Each job consists of a permutation of m tasks corresponding to all machines and thus all jobs have an identical dilation D. The contribution of this paper are the following results;(i) for d = o(root D) jobs and every fixed k, the makespan of an optimal schedule is at most D + o(D), which extends the result of [3] for k = 1;(ii) a randomized on-line approximation algorithm for k-units-J(m) is presented. This is the on-line algorithm with the best known competitive ratio against an oblivious adversary for d = o(root D) and k > 1;(iii) different processing times yield harder instances than identical processing times. There is no 5/3 competitive deterministic on-line algorithm for k-units-J(m), whereas the competitive ratio of the randomized on-line algorithm of (ii) still tends to 1 for d = o(root D).

关键词： on-line algorithms randomization competitive ratio scheduling

来源：评论

学校读者我要写书评

暂无评论

New lower bounds for online k-server routing problems

引用

INFORMATION PROCESSING LETTERS 2009年第11期109卷 563-567页

作者： Fink, Irene Krumke, Sven O. Westphal, Stephan Univ Kaiserslautern Dept Math D-67653 Kaiserslautern Germany

in a k-server routing problem k >= 1 servers move in a metric space in order to visit specified points or carry objects from sources to destinations. In the online version requests arrive online while the servers are traveling. Two classical objective functions are to minimize the makespan, i.e., the time when the last server has completed its tour (k-Traveling Salesman Problem or k-Tsp) and to minimize the sum of completion times (k-Traveling Repairman Problem or k-TRP). Both problems, the k-Tsp and the k-TRP have been studied from a competitive analysis point of view, where the cost of an online algorithm is compared to that of an optimal offline algorithm. However, the gap between the obtained competitive ratios and the corresponding lower bounds have mostly been quite large for k > 1, in particular for randomized algorithms against an oblivious adversary. We reduce a number of gaps by providing new lower bounds for randomized algorithms. The most dramatic improvement is in the lower bound for the k-Dial-a-Ride-Problem (the k-TRP when objects need to be carried) from 4e-5/2e-3 approximate to 2.4104 to 3 which is currently also the best lower bound for deterministic algorithms. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Routing on-line algorithms Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

On the two-dimensional cow search problem

引用

INFORMATION PROCESSING LETTERS 2009年第11期109卷 543-547页

作者： Jez, Artur Lopuszanski, Jakub Univ Wroclaw Inst Comp Sci PL-51151 Wroclaw Poland

We investigate the problem introduced by Baeza-Yates et al. [R.A. Baeza-Yates, J.C. Culberson, G.J.E. Rawlins, Searching with uncertainty, Research report, University of Waterloo, 1987]: given a plane and a horizontal or a vertical line in unknown location give a strategy to find this line. We use a competitive analysis to measure the performance of this strategy. This problem is one of the first generalisations of the cow search problem. (C) 2009 Elsevier B.V. All rights reserved.

关键词： on-line algorithms Search problems Uncertainty

来源：评论

学校读者我要写书评

暂无评论

Improving on-line construction of two-dimensional suffix trees for square matrices

引用

INFORMATION PROCESSING LETTERS 2009年第10期109卷 504-508页

作者： Na, Joong Chae Kim, Namhee Sim, Jeong Seop Kim, Dong Kyue Hanyang Univ Div Elect & Comp Engn Seoul 133791 South Korea Sejong Univ Dept Comp Sci & Engn Seoul 143747 South Korea Inha Univ Sch Comp & Informat Engn Inchon 402751 South Korea

The two-dimensional (2-D) suffix tree of an n x n square matrix A is a compacted trie that represents all square submatrices of A. We consider constructing 2-D suffix trees on-line, which means, instead of giving the whole matrix A in advance, A is separated and each part of A is given at different time as algorithms proceed. In general, developing an on-line algorithm is more difficult than developing an off-line algorithm. Moreover, the smaller the input grain size is, the harder it is to develop an on-line algorithm. In the case of 2-D suffix tree construction, dealing with a character at a time is harder than dealing with a row or a column at a time. In this paper we propose a randomized linear-time algorithm for constructing 2-D suffix trees on-line. This algorithm is superior to previous algorithms in two ways: (1) This is the first linear-time algorithm for constructing 2-D suffix trees on-line. Although there have been some linear-time algorithms for off-line construction, there were no linear-time algorithms for on-line construction. (2) We deal with the most fine-grain on-line case, i.e., our algorithm can construct a 2-D suffix tree even though only one character of A is given at a time, while previous on-line algorithms require at least a row and/or a column at a time. (C) 2009 Elsevier B.V.. All rights reserved.

关键词： Design of algorithms Two-dimensional suffix trees Index data structures on-line algorithms Randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Randomized algorithm for the k-server problem on decomposable spaces

引用

JOURNAL OF DISCRETE algorithms 2009年第4期7卷 411-419页

作者： Nagy-Gyorgy, Judit Univ Szeged Dept Math Aradi Vertanuk Tere 1 H-6720 Szeged Hungary

We study the randomized k-server problem on metric spaces consisting of widely separated subspaces. We give a method which extends existing algorithms to larger spaces with the growth rate of the competitive quotients being at most O(logk). This method yields o(k)-competitive algorithms solving the randomized k-server problem for some special underlying metric spaces, e.g. HSTs of "small" height (but unbounded degree). HSTs are important tools for probabilistic approximation of metric spaces. (C) 2009 Elsevier B.V. All rights reserved.

关键词： k-server on-line algorithms Randomized algorithms Metric spaces

来源：评论

学校读者我要写书评

暂无评论

Measuring the Impact of Supplier-Customer Information Sharing on Production Scheduling

引用

INTERNATIONAL JOURNAL OF INFORMATION SYSTEMS AND SUPPLY CHAIN MANAGEMENT 2009年第2期2卷 48-61页

作者： Rodriguez-Verjan, Gloria Montoya-Torres, Jairo R. Pontificia Univ Javeriana Bogota Colombia Univ Sabana Undergrad Program Int Mkt & logist management Sch Econ & Management Sci Chia Colombia

Nowadays, implementing collaboration strategies between the members of the supply chain has been an important research topic to obtain a more reactive and flexible supply chain in the highly competitive markets. However, few studies have been done on the impact of such collaboration strategies at one of the lower short-term decision levels: production scheduling. This article is devoted to the study of information sharing between the members of a supply chain in a dynamic context. We consider a typical make-to-order direct sell supply chain without finished products inventory, similar to the one implemented by Internet PC sellers. We compare various scheduling algorithms implemented to study different scenarios of information sharing among the members of the chain. We have considered scenarios where no information is shared and scenarios where some or all information is shared. A simulation study is developed in order to get some insights about the impact of information sharing on the performance of the chain. Our results suggest improvement in the performance that shows the importance of collaboration and information sharing between the members of the chain.

关键词： Collaboration Strategies on-line algorithms Scheduling Simulation Supply Chain

来源：评论

学校读者我要写书评

暂无评论

Online Document Filtering Using Adaptive k-NN

Online Document Filtering Using Adaptive k-NN

引用

9th Workshop of the Cross-Language Evaluation Forum (CLEF 2008)

作者： Bodinier, Vincent Qamar, Ali Mustafa Gaussier, Eric Univ Grenoble 1 LIG F-38041 Grenoble France

ISBN: (纸本)9783642044465

We propose in this paper an adaptation of the k-Nearest Neighbor (k-NN) algorithm using category specific thresholds in a multiclass environment where a document can belong to more than one class. Our method uses feedback to time the thresholds and in turn the classification performance over time. The experiments were run on the In File data, comprising 100,000 English documents and 50 topics.

关键词： Filtering on-line algorithms k-nearest neighbors

来源：评论

学校读者我要写书评

暂无评论

On-line models and algorithms for max independent set

引用

RAIRO-OPERATIONS RESEARCH 2006年第2期40卷 129-142页

作者： Escoffier, Bruno Paschos, Vangelis Th. Univ Paris 09 LAMSADE F-75775 Paris 16 France

In on-line computation, the instance of the problem dealt is not entirely known from the beginning of the solution process, but it is revealed step-by-step. In this paper we deal with on-line independent set. On-line models studied until now for this problem suppose that the input graph is initially empty and revealed either vertex-by-vertex, or cluster-by-cluster. Here we present a new on-line model quite different to the ones already studied. It assumes that a superset of the final graph is initially present ( in our case the complete graph on the order n of the final graph) and edges are progressively removed until the achievement of the final graph. Next, we revisit the model introduced in [Demange, Paradon and Paschos, Lect. Notes Comput. Sci. 1963 (2000) 326-334] and study relaxations assuming that some paying backtracking is allowed.

关键词： approximation algorithms competitive ratio maximum independent set on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：