Secondary indexes are frequently used to facilitate fast access to records in a large database. If chosen properly, secondary indexes allow a system to bypass exhaustive searches of the data file; however, poorly cho...
详细信息
Secondary indexes are frequently used to facilitate fast access to records in a large database. If chosen properly, secondary indexes allow a system to bypass exhaustive searches of the data file; however, poorly chosen indexes may lead to deteriorating performance because of the maintenance effort required for frequent changes to the database, through updates, insertions, and deletions. The selection of indexes are therefore one of the critical problems in the design of any database management system. This research presents a probabilistic model of transactions to a file. An evaluation function is developed, based on the cost saving in terms of the number of pages accessed which are attributable to the use of an index set. The maximization of this function would provide an optimal set of indexes. algorithms known to solve this maximization problem need an order of time exponential in the total number of attributes in the file. The theoretical basis is developed, which leads to an algorithm that provides a near optimal solution to the index selection problem in polynomial time. A theoretical boundary for the amount by which the solution obtained by this algorithm deviates from the true optimum is offered. This result is interpreted in the light of evidence gathered through experiments.
To minimize costs in the storage and retrieval of information, it is desirable to place the information in such a way as to minimize read/write head movement. Although a cost function exists, no general formula exist...
详细信息
To minimize costs in the storage and retrieval of information, it is desirable to place the information in such a way as to minimize read/write head movement. Although a cost function exists, no general formula exists as a guide for placement of records under all circumstances. Optimal solutions are available in 2 special cases: independent access probabilities and purely sequential accesses. Although a specially derived algorithm supplies the optimal placements in the 2 special cases of independent and sequential accesses, the standard placement sequence conforms to the arrangement of Markov transition matrices.
Many problems, such as cutting stock problems and the scheduling of tasks with a shared resource, can be viewed as two-dimensional bin packing problems. Using the two-dimensional packing model of Baker, Coffman, and R...
详细信息
Many problems, such as cutting stock problems and the scheduling of tasks with a shared resource, can be viewed as two-dimensional bin packing problems. Using the two-dimensional packing model of Baker, Coffman, and Rivest, a finite list L of rectangles is to be packed into a rectangular bin of finite width but infinite height, so as to minimize the total height used. An algorithm which packs the list in the order given without looking ahead or moving pieces already packed is called an on-line algorithm. Since the problem of finding an optimal packing is NP-hard, previous work has been directed at finding approximation algorithms. Most of the approximation algorithms which have been studied are on-line except that they require the list to have been previously sorted by height or width. This paper examines lower bounds for the worst-case performance of on-line algorithms for both non-preordered lists and for lists preordered by increasing or decreasing height or width.
Graph augmentation problems on a weighted graph involve determining a minimum-cost set of edges to add to a graph to satisfy a specified property, such as biconnectivity, bridge-connectivity or strong connectivity. Th...
详细信息
Graph augmentation problems on a weighted graph involve determining a minimum-cost set of edges to add to a graph to satisfy a specified property, such as biconnectivity, bridge-connectivity or strong connectivity. These augmentation problems are shown to be NP-complete in the restricted case of the graph being initially connected. approximation algorithms with favorable time complexity are presented and shown to have constant worst-case performance ratios.
Many problems in computer science can be termed problems of, given a graph, finding a spanning tree that satisfies a specified property. Many NP-complete problems result, and another large class of properties deals w...
详细信息
Many problems in computer science can be termed problems of, given a graph, finding a spanning tree that satisfies a specified property. Many NP-complete problems result, and another large class of properties deals with structure of the leaves of a spanning tree. This analysis addresses the problem of finding a spanning tree with a maximum number of leaves (an NP-complete problem), or equivalently, finding a full spanning tree (one with a large number of internal nodes with large degrees). Communications networks, graph theoretic problems, and circuit layout constitute applications of this problem. An approximation algorithm is presented for constructing full spanning trees for graphs with maximum degree 3. Although it is a restricted class of graphs, it is sufficient for many applications. Figures.
The construction of alphabetic prefix codes with unequal letter costs and unequal probabilities is considered. A variant of the noiseless coding theorem is proved giving closely matching lower and upper bounds for the...
详细信息
Several polynomial time algorithms finding “good,” but not necessarily optimal, tours for the traveling salesman problem are considered. We measure the closeness of a tour by the ratio of the obtained tour length to...
详细信息
Several polynomial time algorithms finding “good,” but not necessarily optimal, tours for the traveling salesman problem are considered. We measure the closeness of a tour by the ratio of the obtained tour length to the minimal tour length. For the nearest neighbor method, we show the ratio is bounded above by a logarithmic function of the number of nodes. We also provide a logarithmic lower bound on the worst case. A class of approximation methods we call insertion methods are studied, and these are also shown to have a logarithmic upper bound. For two specific insertion methods, which we call nearest insertion and cheapest insertion, the ratio is shown to have a constant upper bound of 2, and examples are provided that come arbitrarily close to this upper bound. It is also shown that for any n≧8
traveling salesman problem
approximation algorithm
-optimal
minimal spanning tree
triangle inequality
Given a positive integer M and n pairs of positive integers [formula omitted], maximize the [formula omitted] subject to the constramts [formula omitted] and δi = 0 or 1 This is the well-known 0/1 knapsack problem An...
详细信息
This paper is concerned with the problem of scheduling on two processors tasks with 1- or 2-unit execution time and having arbitrary precedence constraints. An analysis is made of the algorithm (called f LPTS-schedule...
详细信息
暂无评论