The ACM/ICPC (ACM International Collegiate Programming Contest) is famous as the world's largest and highest level of international collegiate programming contest. In this paper, by considering some problems of th...
详细信息
We consider the planar dynamic convex hull problem. In the literature, solutions exist supporting the insertion and deletion of points in poly-logarithmic time and various queries on the convex hull of the current set...
详细信息
We consider the planar dynamic convex hull problem. In the literature, solutions exist supporting the insertion and deletion of points in poly-logarithmic time and various queries on the convex hull of the current set of points in logarithmic time. If arbitrary insertion and deletion of points are allowed, constant time updates and fast queries are known to be impossible. This paper considers two restricted cases where worst-case constant time updates and logarithmic time queries are possible. We assume all updates are performed on a deque (double-ended queue) of points. The first case considers the monotonic path case, where all points are sorted in a given direction, say horizontally left-to-right, and only the leftmost and rightmost points can be inserted and deleted. The second case assumes that the points in the deque constitute a simple path. Note that the monotone case is a special case of the simple path case. For both cases, we present solutions supporting deque insertions and deletions in worst-case constant time and standard queries on the convex hull of the points in O(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log n)$$\end{document} time, where n is the number of points in the current point set. The convex hull of the current point set can be reported in O(h+logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(h+\log n)$$\end{document} time, where h is the number of edges of the convex hull. For the one-sided monotone path case, where updates are only allowed on one side, the reporting time can be reduced to O(h), and queries on the convex hull are supported in O(logh)\documentclas
We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and pattern, such as intervals, are si...
详细信息
We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and pattern, such as intervals, are singled out. A "match" is a text location where a specified relation between the text and pattern areas is satisfied. In particular we define the structural matching problem of overlap (parity) matching. We seek the text locations where all overlaps of the given pattern and text intervals have even length. We show that this problem can be solved in time O(n log m), where the text length is n and the pattern length is m. As an application of overlap matching, we show how to reduce the string matching with swaps problem to the overlap matching problem. The string matching with swaps problem is the problem of string matching in the presence of local swaps. The best deterministic upper bound known for this problem was O(nm(1/3) log m log sigma) for a general alphabet Sigma, where sigma = min(m, \Sigma\). Our reduction provides a solution to the pattern matching with swaps problem in time 0 (n log m log a). (C) 2002 Elsevier Science (USA). All rights reserved.
Given a tree T = (V, E) of n nodes such that each node v is associated with a value-weight pair (val(v), w(v)), where value val(v) is a real number and weight w(v) is a non-negative integer, the density of T is define...
详细信息
Given a tree T = (V, E) of n nodes such that each node v is associated with a value-weight pair (val(v), w(v)), where value val(v) is a real number and weight w(v) is a non-negative integer, the density of T is defined as Sigma(v is an element of V) val(v)/Sigma(v is an element of V) w(v). A subtree of T is a connected subgraph (V', E') of T, where V' subset of V and E' subset of E. Given two integers w(min) and w(max), the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T' = (V', E') satisfying w(min) <= Sigma(v is an element of V')w(v) <= W-max. In this paper, we first present an O(w(max)n)-time algorithm to find a weight-constrained maximum-density path in a tree T, and then present an O (w(max)(2)n)-time algorithm to find a weight-constrained maximum-density subtree in T. Finally, given a node subset S subset of V, we also present an O(w(max)(2)n)-time algorithm to find a weight-constrained maximum-density subtree in T which covers all the nodes in S.
This paper investigates the semi-online machine covering problems on m >= 3 parallel identical machines. Three different semi-online versions are studied and optimal algorithms are proposed. We prove that if the to...
详细信息
This paper investigates the semi-online machine covering problems on m >= 3 parallel identical machines. Three different semi-online versions are studied and optimal algorithms are proposed. We prove that if the total processing time of all jobs or the largest processing time of all jobs is known in advance, the competitive ratios of the optimal algorithms are both m - 1. If the total processing time and the largest processing time of all jobs are both known in advance, the competitive ratios of the optimal algorithms are 3 when m = 3, and m - 2 when m >= 4. (c) 2006 Elsevier B.V. All rights reserved.
For given edge-capacitated connected graph and two its vertices s and t, the bottleneck (or maxmin\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \use...
详细信息
For given edge-capacitated connected graph and two its vertices s and t, the bottleneck (or maxmin\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\max \min $$\end{document}) path problem is to find the maximum value of path-minimum edge capacities among all paths, connecting s and t. It can be generalized by finding the bottleneck values between s and all possible t. These problems arise as subproblems in the known maximum flow problem, having applications in many real-life tasks. For any graph with n vertices and m edges, they can be solved in O(m) and O(t(m, n)) times, respectively, where t(m,n)=min(m+nlog(n),m alpha(m,n))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t(m,n)=\min (m+n\log (n),m\alpha (m,n))$$\end{document} and alpha(center dot,center dot)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha (\cdot ,\cdot )$$\end{document} is the inverse Ackermann function. In this paper, we generalize of the bottleneck path problems by considering their versions with k sources. For the first of them, where k pairs of sources and targets are (offline or online) given, we present an O((m+k)log(n))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O((m+k)\log (n))$$\end{document}-time randomized and an O(m+(n+k)log(n))\documentclass[12pt]{minimal} \usepa
We consider the problem of scheduling orders for multiple different product types in an environment with in dedicated machines in parallel. The objective is to minimize the total weighted completion time. Each product...
详细信息
We consider the problem of scheduling orders for multiple different product types in an environment with in dedicated machines in parallel. The objective is to minimize the total weighted completion time. Each product type is produced by one and only one of the in dedicated machines;that is, each machine is dedicated to a specific product type. Each order has a weight and may also have a release date. Each order asks for certain amounts of various different product types. The different products for an order can be produced concurrently. Preemptions are not allowed. Even when all orders are available at time 0, the problem has been shown to be strongly NP-hard for any fixed number ( >= 2) of machines. This paper focuses on the design and analysis of efficient heuristics for the case without release dates. Occasionally, however, we extend our results to the case with release dates. The heuristics considered include some that have already been proposed in the literature as well as several new ones. They include various static and dynamic priority rules as well as two more sophisticated LP-based algorithms. We analyze the performance bounds of the priority rules and of the algorithms and present also an in-depth comparative analysis of the various rules and algorithms. The conclusions from this empirical analysis provide insights into the trade-offs with regard to solution quality, speed, and memory space. (C) 2006 Elsevier B.V. All rights reserved.
Scaled Matching refers to the problem of finding all locations in the text where the pattern, proportionally enlarged according to an arbitrary real-sized scale, appears. Scaled matching is an important problem that w...
详细信息
Scaled Matching refers to the problem of finding all locations in the text where the pattern, proportionally enlarged according to an arbitrary real-sized scale, appears. Scaled matching is an important problem that was originally inspired by Computer Vision. Finding a combinatorial definition that captures the concept of real scaling in discrete images has been a challenge in the pattern matching field. No definition existed that captured the concept of real scaling in discrete images, without assuming an underlying continuous signal, as done in the image processing field. We present a combinatorial definition for real scaled matching that scales images in a pleasing natural manner. We also present efficient algorithms for real scaled matching. The running times of our algorithms are as follows. For T, a two-dimensional nxn text array, and P, an mxm pattern array, we find in T all occurrences of P scaled to any real value in time O(nm (3)+n (2) mlog m).
A variety of data structures such as inverted file, multi-lists, quad tree, k-d tree, range tree, polygon tree, quintary tree, multidimensional tries, segment tree, doubly chained tree, the grid file, d -fold tree. su...
详细信息
A variety of data structures such as inverted file, multi-lists, quad tree, k-d tree, range tree, polygon tree, quintary tree, multidimensional tries, segment tree, doubly chained tree, the grid file, d -fold tree. super B -tree, Multiple Attribute Tree (MAT), etc. have been studied for multidimensional searching and related problems. Physical data base organization, which is an important application of multidimensional searching, is traditionally and mostly handled by employing inverted file. This study proposes MAT data structure for bibliographic file systems, by illustrating the superiority of MAT data structure over inverted file. Both the methods are compared in terms of preprocessing, storage and query costs. Worst-case complexity analysis of both the methods, for a partial match query, is carried out in two cases: (a) when directory resides in main memory, (b) when directory resides in secondary memory. In both cases, MAT data structure is shown to be more efficient than the inverted file method. Arguments are given to illustrate the superiority of MAT data structure in an average case also. An efficient adaptation of MAT data structure, that exploits the special features of MAT structure and bibliographic files, is proposed for bibliographic file systems. In this adaptation, suitable techniques for fixing and ranking of the attributes for MAT data structure are proposed. Conclusions and proposals for future research are presented.
We present a new linear algorithm for coloring the edges of a tree. Although this is not the first linear algorithm for the problem, our algorithm unlike the existing ones can be parallelized directly. The paralleliza...
详细信息
We present a new linear algorithm for coloring the edges of a tree. Although this is not the first linear algorithm for the problem, our algorithm unlike the existing ones can be parallelized directly. The parallelization is obtained by showing that edge-coloring can be carried out using tree contraction. Hence, it can be done in O(log n) time using n/log n processors on the EREW PRAM. When the problem is extended to one of coloring the edges of a graph with edge-disjoint cycles, the said algorithm for trees can be extended very easily without increasing the resource requirement.
暂无评论