Consider a finite setE, a weight functionw:E→R, and two matroidsM 1 andM 2 defined onE. The weighted matroidintersection problem consists of finding a setI⊆E, independen...
详细信息
Consider a finite setE, a weight functionw:E→R, and two matroidsM
1 andM
2 defined onE. The weighted matroidintersection problem consists of finding a setI⊆E, independent in both matroids, that maximizes Σ{w(e):e inI}. We present an algorithm of complexity O(nr(r+c+logn)) for this problem, wheren=|E|,r=min(rank(M
1), rank (M
2)),c=max (c
1,c
2) and, fori=1,2,c
i
is the complexity of finding the circuit ofI∪{e} inM
i
(or show that none exists) wheree is inE andI⊆E is independent inM
1 andM
2. A related problem is to find a maximum weight set, independent in both matroids, and of given cardinalityk (if one exists). Our algorithm also solves this problem. In addition, we present a second algorithm that, given a feasible solution of cardinalityk, finds an optimal one of the same cardinality. A sensitivity analysis on the weights is easy to perform using this approach. Our two algorithms are related to existing algorithms. In fact, our framework provides new simple proofs of their validity. Other contributions of this paper are the existence of nonnegative reduced weights (Theorem 6), allowing the improved complexity bound, and the introduction of artificial elements, allowing an improved start and flexibility in the implementation of the algorithms.
We consider the problem of accessing large data files stored at multiple locations across a content distribution, peer-to- peer, or massive storage network. We assume that the data is stored in either original form, o...
详细信息
ISBN:
(纸本)9781424456383
We consider the problem of accessing large data files stored at multiple locations across a content distribution, peer-to- peer, or massive storage network. We assume that the data is stored in either original form, or encoded form at multiple network locations. Clients access the data through simultaneous downloads from several servers across the network. The central problem in this context is to find a set of disjoint paths of minimum total cost that connect the client with a set of servers such that the data stored at the servers is sufficient to decode the required file. We refer to this problem as the Distributed Data Retrieval (DDR) problem. We present an efficient polynomial-time solution for this problem that leverages the matroid intersection algorithm. Our experimental study shows the advantage of our solution over alternative approaches.
暂无评论