Fast approximation of matroid packing and covering

We study packing problems with matroid structures, which includes the strength of a graph of Cunningham and scheduling problems. If $$\mathcal {M}$$ M is a matroid over a set of elements S with independent set $$\mathcal {I}$$ I , and $$m=|S|$$ m = | S | , we suppose that we are given an oracle function that takes an independent set $$A\in \mathcal {I}$$ A ∈ I and an element $$e\in S$$ e ∈ S and determines if $$A\cup \{e\}$$ A ∪ { e } is independent in time I(m). Also, given that the elements of A are represented in an ordered way $$A=\{A_1,\dots ,A_k\}$$ A = { A 1 , ⋯ , A k } , we denote the time to check if $$A\cup \{e\}\notin \mathcal {I}$$ A ∪ { e } ∉ I and if so, to find the minimum $$i\in \{0,\dots ,k\}$$ i ∈ { 0 , ⋯ , k } such that $$\{A_1,\dots ,A_i\}\cup \{e\}\notin \mathcal {I}$$ { A 1 , ⋯ , A i } ∪ { e } ∉ I by $$I^*(m)$$ I ∗ ( m ) . Then, we describe a new FPTAS that computes for any $$\varepsilon >0$$ ε > 0 and for any matroid $$\mathcal {M}$$ M of rank r over a set S of m elements, in memory space O(m), the packing $$\varLambda ({\mathcal {M}})$$ Λ ( M ) within $$1+\varepsilon $$ 1 + ε in time $$O(mI^*(m)\log (m)\log (m/r)/\varepsilon ^2)$$ O ( m I ∗ ( m ) log ( m ) log ( m / r ) / ε 2 ) , and the covering $$\varUpsilon ({\mathcal {M}})$$ Υ ( M ) in time $$O(r\varUpsilon ({\mathcal {M}})I(m)\log (m)\log (m/r)/\varepsilon ^2)$$ O ( r Υ ( M ) I ( m ) log ( m ) log ( m / r ) / ε 2 ) . This method outperforms in time complexity by a factor of $$\varOmega (m/r)$$ Ω ( m / r ) the FPTAS of Plotkin, Shmoys, and Tardos, and a factor of $$\varOmega (m)$$ Ω ( m ) the FPTAS of Garg and Konemann. On top of the value of the packing and the covering, our algorithm exhibits a combinatorial object that proves the approximation. The applications of this result include graph partitioning, minimum cuts, VLSI computing, job scheduling and others.