Search

We consider the list update problem as defined in the seminal work on competitive analysis by Sleator and Tarjan [13] . An instance of the problem consists of a sequence of requests to access items in a linked list. After an item is accessed, that item can be moved to any position forward in the list at no cost (a move called free exchange), and, at any time, any two adjacent items can be swapped at a cost of 1 (a move called paid exchange). The cost to access an item is equal to its current position in the list. The goal is to dynamically rearrange the list so as to minimize the total cost (accrued from accesses and exchanges) over the request sequence. We show a lower bound of 12/11 on the worst-case ratio between the performance of an (offline) optimal algorithm that can only perform free exchanges and that of an (offline) optimal algorithm that can perform both paid and free exchanges. This answers the question of the asymptotic relative power of the two models which has been open since Reingold and Westbrook [11] showed in 1996 that Sleator and Tarjan erred in [13] when they claimed that the two models are equivalent.

Stochastic dominance is a technique for evaluating the performance of online algorithms that provides an intuitive, yet powerful stochastic order between the compared algorithms. Accordingly this holds for bijective analysis, which can be interpreted as stochastic dominance assuming the uniform distribution over requests. These techniques have been applied to some online problems, and have provided a clear separation between algorithms whose performance varies significantly in practice. However, there are situations in which they are not readily applicable due to the fact that they stipulate a stringent relation between the compared algorithms. In this paper, we propose remedies for these shortcomings. First, we establish sufficient conditions that allow us to prove the bijective optimality of a certain class of algorithms for a wide range of problems; we demonstrate this approach in the context of some well-studied online problems. Second, to account for situations in which two algorithms are incomparable or there is no clear optimum, we introduce the bijective ratio as a natural extension of (exact) bijective analysis. Our definition readily generalizes to stochastic dominance. This renders the concept of bijective analysis (and that of stochastic dominance) applicable to all online problems, and allows for the incorporation of other useful techniques such as amortized analysis. We demonstrate the applicability of the bijective ratio to one of the fundamental online problems, namely the continuous $k$-server problem on metrics such as the line, the circle, and the star. Among other results, we show that the greedy algorithm attains bijective ratios of $O(k)$ consistently across these metrics. These results confirm extensive previous studies that gave evidence of the efficiency of this algorithm on said metrics in practice, which, however, is not reflected in competitive analysis., Abridged abstract; full abstract in manuscript

PT.X is one of the largest consumer goods manufacturing companies in Indonesia. As manufacturing companies PT. X has Direct Material (DIM) Procurement Department to control all direct material, which also controls the price list. The process of controlling price list update is still handled via email. The use of email as communication between internal PT. X and also with the vendor, cause email pilling up in the DIM Procurement staff’s inbox. This causes the process of updating material price list to become long and hard to control. There are approximately 4 500 direct materials and approximately 130 active vendors are handled by the DIM Procurement department annually. A large number of materials and vendor handled by DIM Procurement is one of the reasons why the process of controlling price list is important. Digitalization is one way to help the process of controlling and simplifying the price list update process. Improvements to the process of price list update will be done by designing the concept of a platform that helps improve the performance of DIM Procurement Department. The platform called price list catalog can be used to store and record all vendor price list changes. The suggestions for price list update process is to facilitate DIM Procurement department so they can easily control material price list, provide trusted price list, and always available on time. Keywords: price list catalog; price list control; price list data; pricing management

On-line algorithm is an emerging area of research since last five decades with immense theoretical and practical significance. Here the sequence of inputs is received and processed by the algorithm one by one in order. At any instant of time, the algorithm has the knowledge of past and present inputs without knowledge of future inputs. Competitive analysis is a standard performance measure for on-line algorithms in which the performance of an on-line algorithm is compared with that of an optimum offline algorithm. List update problem is a well studied research problem in the area of on-line algorithms, which finds applications in data-compression, dictionary maintenance, collision resolution in hash table, symbol table organization in compiler and computing convex hull in computational geometry. From the literature it is known that Move To Front(MTF) is the best performing deterministic list update algorithm using singly linked list in all practical applications. In this paper, we study and analyse the performance of a deterministic on-line list update algorithm known as Move To Middle(MTM) using doubly linked list. We make a first attempt to find the competitive ratio of MTM algorithm, which was only experimentally studied in the literature. In our study by considering doubly linked list as the data structure and a new variant of standard full cost model, we obtain new competitive analysis result and prove that MTM is 2-competitive. From our competitive analysis result, we show that MTM outperforms MTF.

The list update problem is a well studied online problem in the area of self-adjusting data structures. Understanding the o?ine version of this problem is crucial because of the role it plays in the competitive analysis of online list update algorithms. In this paper we settle a long-standing open problem by showing that the o?ine list update problem is NP-hard.

The list update problem is a well studied online problem in the area of self-adjusting data structures. Understanding the o?ine version of this problem is crucial because of the role it plays in the competitive analysis of online list update algorithms. In this paper we settle a long-standing open problem by showing that the o?ine list update problem is NP-hard.

Inter-cell interference (ICI) may considerably degrade the detection performance of receivers in heterogeneous networks (HetNets). To increase the spectrum efficiency per area, the cell ranges of small cells may be expanded, making the ICI problem more severe. Furthermore, to pursue higher data rate, spatial multiplexing is often applied, incurring inter-antenna interference (IAI). This paper presents a turbo receiver with a dual-loop dual-list update (TRDDU) structure that efficiently detects data signal deteriorated by both ICI and IAI. The proposed lists maintained several likely data vectors and interference vectors, facilitating the receiver to more efficiently determine the most-likely solution. In addition, a dual-loop update algorithm was proposed to enhance the iteration efficiency. Moreover, two design techniques were proposed to reduce the detection complexity. Simulation results showed that the error rate performance of TRDDU is close to that of a receiver in the ICI-free scenario. The complexity needed by TRDDU is only 3.5% that of the receiver that considers all possible interference vectors. In addition, the TRDDU complexity is only approximately 1.56 times that of a successive-interference-cancellation-based receiver. Finally, an over-the-air experiment was conducted to validate the effectiveness of the proposed TRDDU, and the results demonstrated the feasibility of this receiver in the field.

In order to change the path candidates, reduce the average list size, and make more paths pass cyclic redundancy check (CRC), multiple CRC-aided variable successive cancellation list (SCL) decoding algorithm is proposed. In the decoding algorithm, the whole unfrozen bits are divided into several parts and each part is concatenated with a corresponding CRC code, except the last part which is concatenated with a whole unfrozen CRC code. Each CRC detection is performed, and only those satisfying each part CRC become the path candidates. A variable list is setup for each part to reduce the time complexity. Variable list size is setup for each part to reduce the time complexity until one survival path in each part can pass its corresponding CRC. The results show that the proposed algorithm can reduce the average list size, and the frame error rate (FER) performance, and has a better performance with the increase of the part number.

We introduce a new technique for the analysis of online algorithms, namely bijective analysis, that is based on pair-wise comparison of the costs incurred by the algorithms. Under this framework, an algorithm A is no worse than an algorithm B if there is a bijection $$\pi $$ defined over all request sequences of a given size such that the cost of A on $$\sigma $$ is no more than the cost of B on $$B(\pi (\sigma ))$$ . We also study a relaxation of bijective analysis, termed average analysis, in which we compare two algorithms based on their corresponding average costs over request sequences of a given size. We apply these new techniques in the context of two fundamental online problems, namely paging and list update. For paging, we show that any two lazy online algorithms are equivalent under bijective analysis. This result demonstrates that, without further assumptions on characteristics of request sequences, it is unlikely, or even undesirable, to separate online paging algorithms based on their performance. However, once we restrict the set of request sequences to those exhibiting locality of reference, and in particular using a model of locality due to Albers et al. (J Comput Syst Sci 70(2):145–175, 2005), we demonstrate that Least-Recently-Used (LRU) is the unique optimal strategy according to average analysis. This is, to our knowledge, the first deterministic model to provide full theoretical backing to the empirical observation that LRU is preferable in practice. Concerning list update, we obtain similar conclusions, in terms of the bijective comparison of any two online algorithms, and in terms of the superiority (albeit not necessarily unique) of the Move-To-Front (MTF) heuristic in the presence of locality of reference.

Emerging networked systems become increasingly flexible, reconfigurable, and “self-\(*\)”. This introduces an opportunity to adjust networked systems in a demand-aware manner, leveraging spatial and temporal locality in the workload for online optimizations. However, it also introduces a tradeoff: while more frequent adjustments can improve performance, they also entail higher reconfiguration costs. This paper initiates the formal study of list networks which self-adjust to the demand in an online manner, striking a balance between the benefits and costs of reconfigurations. We show that the underlying algorithmic problem can be seen as a distributed generalization of the classic dynamic list update problem known from self-adjusting datastructures: in a network, requests can occur between node pairs. This distributed version turns out to be significantly harder than the classical problem it generalizes. Our main results are a \(\varOmega (\log {n})\) lower bound on the competitive ratio, and a (distributed) online algorithm that is \(\mathcal {O}(\log {n})\)-competitive if the communication requests are issued according to a linear order.

We consider lossless image compression using a technique similar to bZip2 for sequential data. Given an image represented with a matrix of pixel values, we consider different approaches for linearising the image into a sequence and then encoding the sequence using the Move-To-Front list update algorithm. In both linearisation and encoding stages, we exploit the locality present in the images to achieve encodings that are as compressed as possible. We consider a few approaches, and in particular Hilbert space-filling curves, for linearising the image. Using a natural model of locality for images introduced by Albers et al. [J. Comput. Syst. Sci. 2015], we establish the advantage of Hilbert space-filling curves over other linearisation techniques such as row-major or column-major curves for preserving the locality during the linearisation. We also use a result by Angelopoulos and Schweitzer [J. ACM 2013] to select Move-To-Front as the best list update algorithm for encoding the linearised sequence. In summary, our theoretical results show that a combination of Hilbert space-filling curves and Move-To-Front encoding has advantage over other approaches. We verify this with experiments on a dataset consisting of different categories of images.

We introduce the itinerant list update problem (ILU), which is a relaxation of the classic list update problem in which the pointer no longer has to return to a home location after each request. The motivation to introduce ILU arises from the fact that it naturally models the problem of track memory management in Domain Wall Memory. Both online and offline versions of ILU arise, depending on specifics of this application. First, we show that ILU is essentially equivalent to a dynamic variation of the classical minimum linear arrangement problem (MLA), which we call DMLA. Both ILU and DMLA are very natural, but do not appear to have been studied before. In this work, we focus on the offline ILU and DMLA problems. We then give an O ( log 2 ⁡ n ) -approximation algorithm for these problems. While the approach is based on well-known divide-and-conquer approaches for the standard MLA problem, the dynamic nature of these problems introduces substantial new difficulties. We also show an Ω ( log ⁡ n ) lower bound on the competitive ratio for any randomized online algorithm for ILU. This shows that online ILU is harder than online LU, for which O(1)-competitive algorithms, like Move-To-Front, are known.

An additive route problem with preceding conditions is considered in which the cost function and the move constraints both depend on a list of tasks that have not been performed by the current time. The problem is solved by applying a dynamic programming method that takes into account both these factors and is implemented in the construction of a (generally) incomplete array of Bellman function values.

A large number of contemporary research efforts focus on incomplete data streams handling. These efforts, usually, focus on the creation and maintenance of top-k lists useful to provide efficient responses to top-k queries. In case of large volumes of data accumulated at high rates the problem becomes more intense as an efficient method for maintaining the top-k list is considered imperative. In this paper, we focus on the behavior of an Observer Entity (OE) responsible to observe the incoming data and initiate the maintenance process of the top-k list. The maintenance process involves the calculation of a score for each object and the update of the top-k list. We adopt the principles of Optimal Stopping Theory (OST) and introduce a scheme that determines, in the appropriate time, when the OE decides to initiate the maintenance process. Due to the incomplete data setting, the high rate of the incoming data and the large volume of data, the maintenance process is initiated only when the OE has the appropriate amount of information for providing a top-k list. In contrast to other research approaches, we do not maintain any additional sets of objects. Instead, we attempt to minimize the number of the necessary processing tasks over the list of objects. We present a mathematical analysis for our scheme and an extensive experimental evaluation. The comparison with other models shows that the proposed model provides efficiency in the list management and minimizes the required time to result the final top-k list.

retrieval is the most fundamental requirement for any kind of computing application and which requires search operation to be performed from massive databases implemented by various data structures. Searching an element from the list is the fundamental aspects in computing world. Numbers of algorithms are developed for searching an element among which linear search and binary search are the most popular algorithms. In this paper researcher has made efforts to compare these both algorithms to implement on various data structures and to find out the solution to implement binary search on linked linear list. This paper also analyzes both the algorithms at some extent for the applicability and execution efficiency. This paper also analyzes the few data structures to implement these algorithms. At last based on the linear search and binary search algorithms, one algorithm is designed to function on linked linear list.

In this article, we take advantage of the user behavior of requesting videos from the top of the related list provided by YouTube to improve the performance of YouTube caches. We recommend that local caches reorder the related lists associated with YouTube videos, presenting the cached content above noncached content. We argue that the likelihood that viewers select content from the top of the related list is higher than selection from the bottom, and pushing contents already in the cache to the top of the related list would increase the likelihood of choosing cached content. To verify that the position on the list really is the selection criterion more dominant than the content itself, we conduct a user study with 40 YouTube-using volunteers who were presented with random related lists in their everyday YouTube use. After confirming our assumption, we analyze the benefits of our approach by an investigation that is based on two traces collected from a university campus. Our analysis shows that the proposed reordering approach for related lists would lead to a 2 to 5 times increase in cache hit rate compared to an approach without reordering the related list. This increase in hit rate would lead to reduction in server load and backend bandwidth usage, which in turn reduces the latency in streaming the video requested by the viewer and has the potential to improve the overall performance of YouTube's content distribution system. An analysis of YouTube's recommendation system reveals that related lists are created from a small pool of videos, which increases the potential for caching content from related lists and reordering based on the content in the cache.

LazySorted is a Python C extension implementing a partially and lazily sorted list data structure. It solves a common problem faced by programmers, in which they need just part of a sorted list, like its middle element (the median), but sort the entire list to get it. LazySorted presents them with the abstraction that they are working with a fully sorted list, while actually only sorting the list partially with quicksort partitions to return the requested sub-elements. This enables programmers to use naive "sort first" algorithms but nonetheless attain linear run-times when possible. LazySorted may serve as a drop-in replacement for the built-in sorted function in most cases, and can sometimes achieve run-times more than 7 times faster.

The creation of the final rank list for the National Residency Matching Program every year is a laborious task requiring the time and input of numerous faculty members and residents. This article describes the creation of an automated visual rank list to efficiently organize and guide discussion at the yearly rank meeting so that the task may be efficiently and fairly completed. The rank list was created using a PowerPoint (Microsoft) macro that can pull information directly from a spreadsheet to generate a visual rank list that can be modified on-the-fly during the final rank list meeting. An automatically created visual rank list helps facilitate an efficient meeting and creates an open and transparent process leading to the final ranking.

Sorting a list means selection of the particular permutation of the members of that list in which the final permutation contains members in increasing or in decreasing order. Sorted list is prerequisite of some optimized operations such as searching an element from a list, locating or removing an element to/ from a list and merging two sorted list in a database etc. As volume of information is growing up day by day in the world around us and these data are unavoidable to manage for real life situations, the efficient and cost effective sorting algorithms are required. There are several numbers of fundamental and problem oriented sorting algorithms but still now sorting a problem has attracted a great deal of research, perhaps due to the complexity of solving it efficiently and effectively despite of its simple and familiar statements. Algorithms having same efficiency to do a same work using different mechanisms must differ their required time and space. For that reason an algorithm is chosen according to one’s need with respect to space complexity and time complexity. Now a day, space (Memory) is available in market comparatively in cheap cost. So, time complexity is a major issue for an algorithm. Here, the presented approach is to sort a list with linear time and space complexity using divide and conquer rule by partitioning a problem into n (input size) number of sub problems then these sub problems are solved recursively. Required time and space for the algorithm is optimized through reducing the height of the recursive tree and reduced height is too small (as compared to the problem size) to evaluate. So, asymptotic efficiency of this algorithm is very high with respect to time and space.

Access control list have been implemented in many area. This concept of rules can be used to manage user authorization in the large organization. It can be designed based on standard Role Based Access Control List (RBAC) or equivalent. Role access control list should be surrounding by module such as identification, authentication, authorization and auditing which can make the system effective. Role mining will help to define each task correctly in order to avoid conflict when the system establish. Once the identification is been provided system will authenticate based on active directory or through protected database based on hardware of software. A strong authentication and encrypted will increase user confident to access and employ role based system. The database can be located in the same system or it can be in different location. The structure of access control list and the relation with database will define the efficiency and performance of the system. Once the system is working an audit trail will be provided to check all processing and action. A good policy will defined the correct access to specific task. The management of role and policies will assist the access control list to perform as been intended to reduce potential risks and vulnerabilities by embed in the network or through VPN workflow. In this paper architecture, design and policy will be further discussed through the observation and recommendation to increase the maturity of access control in the organization.

In today's busy schedule finding proper information within less time is important need. When user fires top-K list or any other query, user get multiple links as output. User has to visit sites and have to search the proper result manually. But one more problem is there all data available on web is not in same format. These two problems are solved by using proposed enhanced top-k list extraction system. It will give user direct top-k list as result when user fire top-k list as query. This top-k list extraction system depends upon top-k list extraction algorithm. This system handles all web pages that may be structured, unstructured or semi- structured. Also it consumes user time to find proper information.

A linked list is a complex data structure, especially useful in systems or application programming. Linked list uses dynamic allocation of memory by which it allocates memory at the runtime alike of array so it is also called as dynamic data structure. As dynamic list is used for runtime allocation of memory, This feature is very useful in making operating system to keep track of running process that are alive or in sleep mode. This requires either a node to be inserted in between or to be removed. On other side doubly linked list that helps in moving forward or backward mode. We Proposed singly linked list itself to implement operation of doubly linked list as well as singly linked list. Our approach makes use of EX-OR Technique to acquire next node and previous node, To traverse in both the direction but the problem with doubly linked list is that, it requires large amount of memory to store addresses and therefore singly linked list can perform same task of traversing in both direction without increasing its memory requirement. This concept can be usefully applicable to the system or application programming where memory requirement is more viz MRU list , cache in Browser that allow to hit back.

We propose a new way to build a combined list from K base lists, each containing N items. A combined list consists of top segments of various sizes from each base list so that the total size of all top segments equals N. A sequence of item requests is processed and the goal is to minimize the total number of misses. That is, we seek to build a combined list that contains all the frequently requested items. We first consider the special case of disjoint base lists. There, we design an efficient algorithm that computes the best combined list for a given sequence of requests. In addition, we develop a randomized online algorithm whose expected number of misses is close to that of the best combined list chosen in hindsight. We prove lower bounds that show that the expected number of misses of our randomized algorithm is close to the optimum. In the presence of duplicate items, we show that computing the best combined list is NP-hard. We show that our algorithms still apply to a linearized notion of loss in this case. We expect that this new way of aggregating lists will find many ranking applications.

The list update problem is a classical online problem, with an optimal competitive ratio that is still open, known to be somewhere between 1.5 and 1.6. An algorithm with competitive ratio 1.6, the smallest known to date, is COMB, a randomized combination of BIT and the TIMESTAMP algorithm TS. This and almost all other list update algorithms, like MTF, are projective in the sense that they can be defined by looking only at any pair of list items at a time. Projectivity (also known as "list factoring") simplifies both the description of the algorithm and its analysis, and so far seems to be the only way to define a good online algorithm for lists of arbitrary length. In this paper we characterize all projective list update algorithms and show that their competitive ratio is never smaller than 1.6 in the partial cost model. Therefore, COMB is a best possible projective algorithm in this model., Version 3 same as version 2, but date in LaTeX \today macro replaced by March 8, 2012

It is well-established that input sequences for paging and list update have locality of reference. In this paper we analyze the performance of algorithms for these problems in terms of the amount of locality in the input sequence. We define a measure for locality that is based on Denning’s working set model and express the performance of well known algorithms in terms of this parameter. This explicitly introduces parameterized-style analysis to online algorithms. The idea is that rather than normalizing the performance of an online algorithm by an (optimal) offline algorithm, we explicitly express the behavior of the algorithm in terms of two more natural parameters: the size of the cache and Denning’s working set measure. This technique creates a performance hierarchy of paging algorithms which better reflects their experimentally observed relative strengths. It also reflects the intuition that a larger cache leads to a better performance. We also apply the parameterized analysis framework to list update and show that certain randomized algorithms which are superior to MTF in the classical model are not so in the parameterized case, which matches experimental results.

For the discrete manufacturing enterprises, the job shop scheduling problem is an important class of actual combinatorial optimization problem with resources and sequence constraints. According to the needs of the job shop scheduling problem, a sequence list algorithm for the job shop scheduling problem was designed in this paper. In order to make all jobs being finished as soon as possible, the goal of the sequence list algorithm is minimizing the maximal the finish time of all operations. In the sequence list algorithm, two types of sequence lists were built. They are the job sequence lists and the machine sequence lists. A job sequence list was used to store all operations of a job on the basis of its process constraints. A machine sequence list which is null initially was used to store all operations on a machine in accordance with the actual processing order. The important tasks of the sequence list algorithm are inserting all operations of the job sequence lists into the machine sequence lists and adjusting the processing order of the operations in the machine sequence lists. The sequence list algorithm could always achieve a good job shop schedule which ensures the select performance indicators. The feasibility and efficiency of the algorithm was verified through examples.

In some languages, because there is no pointer data type, so the single linked list is described by the use of the array. When there are multiple nodes of the same type list, these lists can share the same static linked list of memory, so it can mutually adjust the remaining places to reduce the overflow space. To solve practical problems, this paper is designed from the static linked list sharing the same storage space, the constructor, inserting operations, deleting operations, and it puts up forward a suggestion of its specific implementation and analyzes time complexity of algorithms and its significances.

In this article, an efficient parallel algorithm for a hybrid CPU-GPU platform is proposed to enable large-scale molecular dynamics (MD) simulations of the metal solidification process. The results, implemented the parallel algorithm program on the hybrid CPU-GPU platform shows better performance than the program based on previous algorithms running on the CPU cluster platform. By contrast, the total execution time of the new program has been obviously decreased. Particularly, because of the use of the modified load balancing method, the neighbor list update time is approximately zero. The parallel program based on the CUDA+OpenMP model shows a factor of 6 16-core calculation speedups compared to the parallel program based on the MPI+OpenMP model, and the optimal computational efficiency is achieved in the simulation system including 10,000,000 aluminum atoms. Finally, the good consistency between them verifies the correctness of the algorithm efficiently, by comparison of the theoretical results and experimental results.

List Scheduling is one of the most widely used techniques for scheduling due to its simplicity and efficiency. In traditional list-based schedulers, a cost/priority function is used to compute the priority of tasks/jobs and put them in an ordered list. The cost function has been becoming more and more complex to cover increasing number of constraints in the system design. However, most of the existing list-based schedulers implement a static priority function that usually provides only one schedule for each task graph input. Therefore, they may not be able to satisfy the desire of system designers, who want to examine the trade-off between a number of design requirements (performance, power, energy, reliability ...). To address this problem, we propose a framework to utilize the Genetic Algorithm (GA) for exploring the design space and obtaining Pareto-optimal design points. Furthermore, multiple regression techniques are used to build predictive models for the Pareto fronts to limit the execution time of GA. The models are built using training task graph datasets and applied on incoming task graphs. The Pareto fronts for incoming task graphs are produced in time 2 orders of magnitude faster than the traditional GA, with only 4% degradation in the quality.

In the context of linear search, list accessing problem is a well known research problem. Unsorted linear list of distinct elements and a request sequence are the input to the list accessing problem where access operation is to be performed on each request on an element of the list. The main objective of list accessing algorithm is to minimize the access cost while processing a request sequence on the list. We have named our algorithm as Advanced Move-To-Front (AMTF) in which new list is updated each time based on the frequency count of accessed element's position in the list. In our paper we have compared Advanced MTF cost with MTF (Move to Front) cost of the accessed elements in the given request sequence and we have found that in most of the data sets, Advanced MTF cost is less as compared to MTF cost.

Neighbourhood-based Collaborative Filtering (CF) has been applied in the industry for several decades because of its easy implementation and high recommendation accuracy. As the core of neighbourhood-based CF, the task of dynamically maintaining users’ similarity list is challenged by cold-start problem and scalability problem. Recently, several methods are presented on addressing the two problems. However, these methods require mn steps to compute the similarity list against the kNN attack, where m and n are the number of items and users in the system respectively. Observing that the k new users from the kNN attack, with enough recommendation data, have the same rating list, we present a faster algorithm, TwinSearch, to avoid computing and sorting the similarity list for each new user repeatedly to save the time. The computational cost of our algorithm is 1/125 of the existing methods. Both theoretical and experimental results show that the TwinSearch Algorithm achieves better running time than the traditional method.

In this paper we study the performance of list update algorithms under arbitrary distributions that exhibit strict locality of reference and prove that Move-To-Front (MTF) is the best list update algorithm under any such distribution. We also show that the performance of MTF depends on the amount of locality of reference, while the performance of any static list update algorithm is independent of the amount of locality.

Classical list scheduling is a very popular and efficient technique for scheduling jobs for parallel and distributed platforms. It is inherently centralized. However, with the increasing number of processors, the cost for managing a single centralized list becomes too prohibitive. A suitable approach to reduce the contention is to distribute the list among the computational units: each processor only has a local view of the work to execute. Thus, the scheduler is no longer greedy and standard performance guarantees are lost. The objective of this work is to study the extra cost that must be paid when the list is distributed among the computational units. We first present a general methodology for computing the expected makespan based on the analysis of an adequate potential function which represents the load imbalance between the local lists. We obtain an equation giving the evolution of the potential by computing its expected decrease in one step of the schedule. Our main theorem shows how to solve such equations to bound the makespan. Then, we apply this method to several scheduling problems, namely, for unit independent tasks, for weighted independent tasks and for tasks with precedence constraints. More precisely, we prove that the time for scheduling a global workload W composed of independent unit tasks on m processors is equal to W/m plus an additional term proportional to log2 W. We provide a lower bound which shows that this is optimal up to a constant. This result is extended to the case of weighted independent tasks. In the last setting, precedence task graphs, our analysis leads to an improvement on the bound of Arora et al. (Theory Comput. Syst. 34(2):115–144, 2001). We end with some experiments using a simulator. The distribution of the makespan is shown to fit existing probability laws. Moreover, the simulations give a better insight into the additive term whose value is shown to be around 3log2 W confirming the precision of our analysis.

We give an explicit representation for the offline optimum strategy for list update under the MRM model of Martinez and Roura [C. Martinez, S. Roura, On the competitiveness of the move-to-front rule, Theoret. Comput. Sci. 242 (1-2) (2000) 3130-325] and Munro [J.I. Munro, On the competitiveness of linear search, in: Proc. 8th Annual European Symposium on Algorithms (ESA 2000), in: Lecture Notes in Comput. Sci., vol. 1879, 2000, pp. 338-345] and give an O(n^3) algorithm to compute it. This is in contrast to the standard model of Sleator and Tarjan [D.D. Sleator, R.E. Tarjan, Amortized efficiency of list update and paging rules, Commun. ACM 28 (2) (1985) 202-208] under which computing the offline optimum was shown to be NP-hard [C. Ambuhl, Offline list update is NP-hard, in: Proc. 8th Annual European Symposium on Algorithms (ESA 2000), in: Lecture Notes in Comput. Sci., vol. 1879, 2000, pp. 42-51]. This algorithm follows from a new characterization theorem for realizable visiting sequences in the MRM model.

List accessing problem is associated with the searching and sorting of unordered records arranged linearly. Many approaches are followed and invented since more than four decades such as self-organizing linear lists in order to obtain a minimal cost for accessing the list. This paper introduces a hybrid method that is the combination of Move to Front (MTF) and transposes (TRANS) methods for the list accessing problem which results in a minimum of total access costs as compared to the cost of accessing of list using individual methods. Our paper also uses the randomized bit algorithm and look ashead concepts for obtaining the self-organizing linear list.

The problem of routing movements on a finite system of sets with constraints in the form of antecedence (the generalized courier problem) is addressed. The specific feature of the problem is that the cost function for the movement from one set to another involves a dependence on a list of remaining jobs on visiting of the mentioned sets.

This paper describes how the more mathematical topics in the data structures curriculum can be illustrated with visual proofs. This frees students from difficult algebraic manipulation. Visual proofs are provided for the average case of searching for a unique item in a list and for searching for an item which occurs independently (and not necessarily uniquely) in the list with a known probability.

This paper describes a new representation for the solutions of the resource-constrained project scheduling problem (RCPSP) denoted Activity Set List. The most efficient heuristics for the problem use the activity list representation and the serial SGS method to construct the corresponding solution (schedule). The activity list may induce a search space of representations much larger then the space of schedules because the same schedule can correspond to many different activity list representations. We indicate how the activity set list representation can significantly reduce the search space, and how to move more efficiently through it. Furthermore, this new representation never excludes the optimal solution and it has many interesting properties. An evaluation of the search space reduction induced by this representation is made for the most used library of instances in the literature. The activity set list representation may be used to construct a new category of more efficient solution procedures for the problem.

Efficient resource management is an important requirement for many process-oriented applications. Typically, work items are assigned to resources through their work lists. There are many reasons for reordering work items in a resource's work list. For process scheduling, for example, swapping process instances constitutes a mean to keep due times. At the same time, reducing the throughput time of the global process is typically not the primary goal. For process optimization, in turn, the implications of reordering work items on the overall temporal performance of the process might be crucial. In this paper, we investigate how reordering work items affects performance parameters that are typically associated with a first-in-first-out processing mechanism at resources. The analysis is conducted for single process tasks and for typical control flow patterns such as sequence as well as parallel and alternative branchings. It is shown that the implications on the global throughput time are less than expected, while the effects on instance based parameters strongly depend on the control-flow pattern in which the reordering mechanism is implemented. The results are supported by means of a simulation.

International audience; Algorithms for learning to rank Web documents, display ads, or other types of items constitute a fundamental component of search engines and more generally of online services. In such systems, when a user makes a request or visits a web page, an ordered list of items (e.g. documents or ads) is displayed; the user scans this list in order, and clicks on the first relevant item if any. When the user clicks on an item, the reward collected by the system typically decreases with the position of the item in the displayed list. The main challenge in the design of sequential list selection algorithms stems from the fact that the probabilities with which the user clicks on the various items are unknown and need to be learned. We formulate the design of such algorithms as a stochastic bandit optimization problem. This problem differs from the classical bandit framework: (1) the type of feedback received by the system depends on the actual relevance of the various items in the displayed list (if the user clicks on the last item, we know that none of the previous items in the list are relevant); (2) there are inherent correlations between the average relevance of the items (e.g. the user may be interested in a specific topic only). We assume that items are categorized according to their topic and that users are clustered, so that users of the same cluster are interested in the same topic. We investigate several scenarios depending on the available side-information on the user before selecting the displayed list: (a) we first treat the case where the topic the user is interested in is known when she places a request; (b) we then study the case where the user cluster is known but the mapping between user clusters and topics is unknown. For both scenarios, we derive regret lower bounds and devise algorithms that approach these fundamental limits.

This study analyzed patient adoption of secure messaging to update medication list in an ambulatory care setting. The objective was to establish demographic differences between users and non-users of secure messaging for medications list update. Efficiency of secure messaging for the updates was compared to fax and telephone based updates.The study used a retrospective, cross-sectional study of patient medical records and pharmacy call logs at Mayo Clinic, Arizona from December 2012 to May 2013, approximately one year after organizing a pharmacy call center for medication updates. A subgroup analysis during a 2-week period was used to measure time to complete update.Main dependent variable is the frequency of medication list updates over the study duration. Technician time required for the update was also utilized.A total of 22,495 outpatient visits were drawn and 18,702 unique patients were included in the primary analysis. A total of 402 unique patients were included in sub-group analysis. Secure message response rate (49.5%) was statistically significantly lower than that for phone calls (54.8%, p0.001). Time to complete the update was significantly higher for faxed medication lists (Wilcoxon rank-sum tests, p0.001) when compared to those for secure message or phone.Around 50% of the patients respond to medication update requests before office visit when contacted using phone calls and secure messages. Given the demographic differences between users and non-users of patient portal, mixed mode communication with patients is likely to be the norm for the foreseeable future in outpatient settings.