共查询到20条相似文献,搜索用时 31 毫秒
1.
We study the probabilistic model in the key tree management problem. Users have different behaviors. Normal users have probability
p to issue join/leave request while the loyal users have probability zero. Given the numbers of such users, our objective is
to construct a key tree with minimum expected updating cost. We observe that a single LUN (Loyal User Node) is enough to represent
all loyal users. When 1−p≤0.57 we prove that the optimal tree that minimizes the cost is a star. When 1−p>0.57, we try to bound the size of the subtree rooted at every non-root node. Based on the size bound, we construct the optimal
tree using dynamic programming algorithm in O(n⋅K+K
4) time where K=min {4(log (1−p)−1)−1,n} and n is the number of normal users. 相似文献
2.
Rocchio’s similarity-based relevance feedback algorithm, one of the most important query reformation methods in information
retrieval, is essentially an adaptive supervised learning algorithm from examples. In practice, Rocchio’s algorithm often
uses a fixed query updating factor. When this is the case, we strengthen the linear Ω(n) lower bound obtained by Chen and Zhu (Inf. Retr. 5:61–86, 2002) and prove that Rocchio’s algorithm makes Ω(k(n−k)) mistakes in searching for a collection of documents represented by a monotone disjunction of k relevant features over the n-dimensional binary vector space {0,1}
n
, when the inner product similarity measure is used. A quadratic lower bound is obtained when k is linearly proportional to n. We also prove an O(k(n−k)3) upper bound for Rocchio’s algorithm with the inner product similarity measure in searching for such a collection of documents
with a constant query updating factor and a zero classification threshold. 相似文献
3.
We study job scheduling on processors capable of running at variable voltage/speed to minimize energy consumption. Each job
in a problem instance is specified by its arrival time and deadline, together with required number of CPU cycles. It is known
that the minimum energy schedule for n jobs can be computed in O(n3) time, assuming a convex energy function. We investigate more efficient algorithms for computing the optimal schedule when
the job sets have certain special structures. When the time intervals are structured as trees, the minimum energy schedule
is shown to have a succinct characterization and is computable in time O(P) where P is the tree’s total path length. We also study an on-line average-rate heuristics AVR and prove that its energy consumption
achieves a small constant competitive ratio for nested job sets and for job sets with limited overlap. Some simulation results
are also given.
This work is supported in part by Research Grants Council of Hong Kong under grant No. CityU 1165/04E, National Natural Science
Foundation of China under Grant No. 60135010, 60321002 and the Chinese National Key Foundation Research & Development Plan
(2004CB318108). 相似文献
4.
Hanno Lefmann 《Journal of Combinatorial Optimization》2008,16(2):182-195
In this paper generalizations of Heilbronn’s triangle problem to convex hulls of j points in the unit square [0,1]2 are considered. By using results on the independence number of linear hypergraphs, for fixed integers k≥3 and any integers n≥k a deterministic o(n
6k−4) time algorithm is given, which finds distributions of n points in [0,1]2 such that, simultaneously for j=3,…,k, the areas of the convex hulls determined by any j of these n points are Ω((log n)1/(j−2)/n
(j−1)/(j−2)). 相似文献
5.
We present algorithms and lower bounds for the Longest Increasing Subsequence (LIS) and Longest Common Subsequence (LCS) problems
in the data-streaming model. To decide if the LIS of a given stream of elements drawn from an alphabet αbet has length at least k, we discuss a one-pass algorithm using O(k log αbetsize) space, with update time either O(log k) or O(log log αbetsize); for αbetsize = O(1), we can achieve O(log k) space and constant-time updates. We also prove a lower bound of Ω(k) on the space requirement for this problem for general alphabets αbet, even when the input stream is a permutation of αbet. For finding the actual LIS, we give a ⌈log (1 + 1/ɛ)-pass algorithm using O(k1+ɛlog αbetsize) space, for any ɛ > 0. For LCS, there is a trivial Θ(1)-approximate O(log n)-space streaming algorithm when αbetsize = O(1). For general alphabets αbet, the problem is much harder. We prove several lower bounds on the LCS problem, of which the strongest is the following: it
is necessary to use Ω(n/ρ2) space to approximate the LCS of two n-element streams to within a factor of ρ, even if the streams are permutations of each other.
A preliminary version of this paper appears in the Proceedings of the 11th International Computing and Combinatorics Conference
(COCOON'05), August 2005, pp. 263–272. 相似文献
6.
In a graph G, a vertex dominates itself and its neighbors. A subset S ⊂eqV(G) is an m-tuple dominating set if S dominates every vertex of G at least m times, and an m-dominating set if S dominates every vertex of G−S at least m times. The minimum cardinality of a dominating set is γ, of an m-dominating set is γ
m
, and of an m-tuple dominating set is mtupledom. For a property π of subsets of V(G), with associated parameter f_π, the k-restricted π-number r
k
(G,f_π) is the smallest integer r such that given any subset K of (at most) k vertices of G, there exists a π set containing K of (at most) cardinality r. We show that for 1< k < n where n is the order of G: (a) if G has minimum degree m, then r
k
(G,γ
m
) < (mn+k)/(m+1); (b) if G has minimum degree 3, then r
k
(G,γ) < (3n+5k)/8; and (c) if G is connected with minimum degree at least 2, then r
k
(G,ddom) < 3n/4 + 2k/7. These bounds are sharp.
Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal. 相似文献
7.
Changcun Ma Donghyun Kim Yuexuan Wang Wei Wang Nassim Sohaee Weili Wu 《Journal of Combinatorial Optimization》2010,20(3):249-258
Given a k-connected graph G=(V,E) and V
′⊂V, k-Vertex-Connected Subgraph Augmentation Problem (k-VCSAP) is to find S⊂V∖V
′ with minimum cardinality such that the subgraph induced by V
′∪S is k-connected. In this paper, we study the hardness of k-VCSAP in undirect graphs. We first prove k-VCSAP is APX-hard. Then, we improve the lower bound in two ways by relying on different assumptions. That is, we prove no
algorithm for k-VCSAP has a PR better than O(log (log n)) unless P=NP and O(log n) unless NP⊆DTIME(n
O(log log n)), where n is the size of an input graph. 相似文献
8.
Liang Zhao Hiroshi Nagamochi Toshihide Ibaraki 《Journal of Combinatorial Optimization》2001,5(4):397-410
For an edge weighted undirected graph G and an integer k > 2, a k-way cut is a set of edges whose removal leaves G with at least k components. We propose a simple approximation algorithm to the minimum k-way cut problem. It computes a nearly optimal k-way cut by using a set of minimum 3-way cuts. We show that the performance ratio of our algorithm is 2 – 3/k for an odd k and 2 – (3k – 4)/(k
2 – k) for an even k. The running time is O(kmn
3 log(n
2/m)) where n and m are the numbers of vertices and edges respectively. 相似文献
9.
We study the problem of separating sublinear time computations via approximating the diameter for a sequence S=p
1
p
2
⋅⋅⋅
p
n
of points in a metric space, in which any two consecutive points have the same distance. The computation is considered respectively
under deterministic, zero error randomized, and bounded error randomized models. We obtain a class of separations using various
versions of the approximate diameter problem based on restrictions on input data. We derive tight sublinear time separations
for each of the three computation models via proving that computation with O(n
r
) time is strictly more powerful than that with O(n
r−ε
) time, where r and ε are arbitrary parameters in (0,1) and (0,r) respectively. We show that, for any parameter r∈(0,1), the bounded error randomized sublinear time computation in time O(n
r
) cannot be simulated by any zero error randomized sublinear time algorithm in o(n) time or queries; and the same is true for zero error randomized computation versus deterministic computation. 相似文献
10.
Sequence alignment is a central problem in bioinformatics. The classical dynamic programming algorithm aligns two sequences
by optimizing over possible insertions, deletions and substitutions. However, other evolutionary events can be observed, such
as inversions, tandem duplications or moves (transpositions). It has been established that the extension of the problem to
move operations is NP-complete. Previous work has shown that an extension restricted to non-overlapping inversions can be
solved in O(n
3) with a restricted scoring scheme. In this paper, we show that the alignment problem extended to non-overlapping moves can
be solved in O(n
5) for general scoring schemes, O(n
4log n) for concave scoring schemes and O(n
4) for restricted scoring schemes. Furthermore, we show that the alignment problem extended to non-overlapping moves, inversions
and tandem duplications can be solved with the same time complexities. Finally, an example of an alignment with non-overlapping
moves is provided.
A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS, vol. 4598, pp. 151–164. 相似文献
11.
Arindam Karmakar Sandip Das Subhas C. Nandy Binay K. Bhattacharya 《Journal of Combinatorial Optimization》2013,25(2):176-190
Given a set P of n points and a straight line L, we study three important variations of minimum enclosing circle problem as follows:
- Computing k identical circles of minimum radius with centers on L, whose union covers all the points in P.
- Computing the minimum radius circle centered on L that can enclose at least k points of P.
- If each point in P is associated with one of the k given colors, then compute a minimum radius circle with center on L such that at least one point of each color lies inside it.
12.
Scheduling a single semi-continuous batching machine 总被引:3,自引:0,他引:3
This paper addresses a new problem, called semi-continuous batch scheduling, which arises in the heating-operation of tube-billets in the steel industry. Each heating furnace can be regarded as a semi-continuous batching machine, which can handle up to C jobs simultaneously. The jobs in the same batch enter and leave the machine semi-continuously, which differs from the traditional batching machine scheduling where the jobs in same batch have a starting time and a finishing time. In this paper the processing time of a batch depends on the capacity of the semi-continuous batching machine, the longest processing time of jobs in the batch and its size. The objectives are to schedule jobs on the machine so that the makespan and the total completion time are minimized. A schedule for a semi-continuous batching machine consists of a batching and sequencing for the batches. We propose the optimal properties of two different objective functions and present the different dynamic programming algorithms with a running time of O(n2), respectively. 相似文献
13.
Bang Ye Wu 《Journal of Combinatorial Optimization》2004,8(1):29-39
We investigated the problem of constructing the maximum consensus tree from rooted triples. We showed the NP-hardness of the problem and developed exact and heuristic algorithms. The exact algorithm is based on the dynamic programming strategy and runs in O((m + n
2)3
n
) time and O(2
n
) space. The heuristic algorithms run in polynomial time and their performances are tested and shown by comparing with the optimal solutions. In the tests, the worst and average relative error ratios are 1.200 and 1.072 respectively. We also implemented the two heuristic algorithms proposed by Gasieniec et al. The experimental result shows that our heuristic algorithm is better than theirs in most of the tests. 相似文献
14.
Peter Che Bor Lam Wensong Lin Jianzhuan Wu 《Journal of Combinatorial Optimization》2007,14(2-3):219-227
Let j and k be two positive integers with j≥k. An L(j,k)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between labels of any two adjacent vertices is at least j, and the difference between labels of any two vertices that are at distance two apart is at least k. The minimum range of labels over all L(j,k)-labellings of a graph G is called the λ
j,k
-number of G, denoted by λ
j,k
(G). A σ(j,k)-circular labelling with span m of a graph G is a function f:V(G)→{0,1,…,m−1} such that |f(u)−f(v)|
m
≥j if u and v are adjacent; and |f(u)−f(v)|
m
≥k if u and v are at distance two apart, where |x|
m
=min {|x|,m−|x|}. The minimum m such that there exists a σ(j,k)-circular labelling with span m for G is called the σ
j,k
-number of G and denoted by σ
j,k
(G). The λ
j,k
-numbers of Cartesian products of two complete graphs were determined by Georges, Mauro and Stein ((2000) SIAM J Discret Math 14:28–35). This paper determines the λ
j,k
-numbers of direct products of two complete graphs and the σ
j,k
-numbers of direct products and Cartesian products of two complete graphs.
Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.
This work is partially supported by FRG, Hong Kong Baptist University, Hong Kong; NSFC, China, grant 10171013; and Southeast
University Science Foundation grant XJ0607230. 相似文献
15.
Sergey Bereg Marcin Kubica Tomasz Waleń Binhai Zhu 《Journal of Combinatorial Optimization》2007,13(2):179-188
In this paper, we present a new model for RNA multiple sequence structural alignment based on the longest common subsequence. We consider both the off-line and on-line cases. For the off-line case, i.e., when the longest common subsequence is given
as a linear graph with n vertices, we first present a polynomial O(n
2) time algorithm to compute its maximum nested loop. We then consider a slightly different problem—the Maximum Loop Chain
problem and present an algorithm which runs in O(n
5) time. For the on-line case, i.e., given m RNA sequences of lengths n, compute the longest common subsequence of them such that this subsequence either induces a maximum nested loop or the maximum
number of matches, we present efficient algorithms using dynamic programming when m is small.
This research is partially supported by EPSCOR Visiting Scholar's Program and MSU Short-term
Professional Development Program. 相似文献
16.
The following planar minimum disk cover problem is considered in this paper: given a set
D\mathcal{D}
of n disks and a set ℘ of m points in the Euclidean plane, where each disk covers a subset of points in ℘, to compute a subset of disks with minimum
cardinality covering ℘. This problem is known to be NP-hard and an algorithm which approximates the optimal disk cover within
a factor of (1+ε) in
O(mnO(\frac1e2log2\frac1e))\mathcal{O}(mn^{\mathcal{O}(\frac{1}{\epsilon^{2}}\log^{2}\frac{1}{\epsilon})})
time is proposed in this paper. This work presents the first polynomial time approximation scheme for the minimum disk cover
problem where the best known algorithm can approximate the optimal solution with a large constant factor. Further, several
variants of the minimum disk cover problem such as the incongruent disk cover problem and the weighted disk cover problem
are considered and approximation schemes are designed. 相似文献
17.
In this paper, we study the problem of supporting range sum queries on a compressed sequence of values. For a sequence of
n k-bit integers, k ≤ O(log n), our data structures require asymptotically the same amount of storage as the compressed sequence if compressed using the
Lempel-Ziv algorithm. The basic structure supports range sum queries in O(log n) time. With an increase by a constant factor in the storage complexity, the query time can be improved to O(log log n + k).
The work described in this paper is fully supported by a grant from the Research Grant Council of the Hong Kong Special Administrative
Region, China (CityU 1071/02E). A preliminary version has appeared in 11th International Conference in Computing and Combinatorics
(COCOON'05). 相似文献
18.
A vector merging problem is introduced where two vectors of length n are merged such that the k-th entry of the new vector is the minimum over of the -th entry of the first vector plus the sum of the first k – + 1 entries of the second vector. For this problem a new algorithm with O(n log n) running time is presented thus improving upon the straightforward O(n
2) time bound.The vector merging problem can appear in different settings of dynamic programming. In particular, it is applied for a recent fully polynomial time approximation scheme (FPTAS) for the classical 0–1 knapsack problem by the same authors. 相似文献
19.
Let k 5 be a fixed integer and let m = (k – 1)/2. It is shown that the independence number of a C
k-free graph is at least c
1[ d(v)1/(m – 1)](m – 1)/m
and that, for odd k, the Ramsey number r(C
k, K
n) is at most c
2(n
m + 1/log n)1/m
, where c
1 = c
1(m) > 0 and c
2 = c
2(m) > 0. 相似文献
20.
Chung-Haw Chang Chao-Ming Sun Hua-Min Huang Lih-Hsing Hsu 《Journal of Combinatorial Optimization》2007,14(2-3):349-364
Let G be a finite undirected bipartite graph. Let u, v be two vertices of G from different partite sets. A collection of k internal vertex disjoint paths joining u to v is referred as a k-container C
k
(u,v). A k-container is a k
*-container if it spans all vertices of G. We define G to be a k
*-laceable graph if there is a k
*-container joining any two vertices from different partite sets. A k
*-container C
k
*(u,v)={P
1,…,P
k
} is equitable if ||V(P
i
)|−|V(P
j
)||≤2 for all 1≤i,j≤k. A graph is equitably k
*-laceable if there is an equitable k
*-container joining any two vertices in different partite sets. Let Q
n
be the n-dimensional hypercube. In this paper, we prove that the hypercube Q
n
is equitably k
*-laceable for all k≤n−4 and n≥5.
Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.
The work of H.-M. Huang was supported in part by the National Science Council of the Republic of China under NSC94-2115-M008-013. 相似文献