Fast approximation of matroid packing and covering
Galtier, erome
Primary Author
mixed material
bibliography
Switzerland
Springer
2018
continuing
Weekly
vol.271issue 2
en
English
Abstract We study packing problems with matroid structures, which includes the strength ofagraphofCunninghamandschedulingproblems.IfMisamatroidoverasetofelements S with independent setI, andm =|S|, we suppose that we are given an oracle function that takesanindependentset A ∈Iandanelemente ∈ S anddeterminesif A∪{e}isindependent in time I(m). Also, given that the elements of A are represented in an ordered way A = {A1,...,Ak}, we denote the time to check ifA∪{e} / ∈I and if so, to ﬁnd the minimum i ∈ {0,...,k}such that{A1,...,Ai}∪{e} / ∈I by I∗(m). Then, we describe a new FPTAS thatcomputesforany ε>0andforanymatroidMofrankr overasetSofmelements,inmemoryspace O(m), the packing Λ(M) within 1+ε in time O(mI∗(m)log(m)log(m/r)/ε2), andthecovering Υ(M)intime O(rΥ(M)I(m)log(m)log(m/r)/ε2).Thismethodoutperforms in time complexity by a factor of Ω(m/r) the FPTAS of Plotkin, Shmoys, and Tardos, and a factor of Ω(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. Keywords Approximation algorithm·Matroid·Multiplicative-weights-update method· Kruskal algorithm·Strength and arboricity of a graph·Job scheduling
Business and Management
NONE15729338
54885
2019-07-11 10:23:25
2019-07-11 10:23:25
machine generated