Fast approximation of matroid packing and covering

Collection Location Koleksi E-book & E-Journal Perpustakaan Pusat Unila
Edition vol.271issue 2
Call Number
ISBN/ISSN 15729338
Author(s) Galtier, erome
Subject(s) Business and Management
Classification NONE
Series Title
GMD E-Journal
Language English
Publisher Springer
Publishing Year 2018
Publishing Place Switzerland
Abstract/Notes 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 find 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
Specific Detail Info
  Back To Previous