TY - JOUR

T1 - Robust independence systems

AU - Kakimura, Naonori

AU - Makino, Kazuhisa

N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.

PY - 2013

Y1 - 2013

N2 - An independence system F is one of the most fundamental combinatorial concepts, which includes a variety of objects in graphs and hypergraphs such as matchings, stable sets, and matroids. We discuss the robustness for independence systems, which is a natural generalization of the greedy property of matroids. For a real number α > 0, a set X ∈ F is said to be α-robust if for any k, it includes an α-approximation of the maximum k-independent set, where a set Y in F is called k-independent if the size |Y | is at most k. In this paper, we show that every independence system has a 1/√μ(F)- robust independent set, where μ(F) denotes the exchangeability of F. Our result contains a classical result for matroids and the ones of Hassin and Rubinstein [SIAM J. Discrete Math., 15 (2002), pp. 530-537] for matchings and Fujita, Kobayashi, and Makino [SIAM J. Discrete Math., 27 (2013), pp. 1234-1256] for matroid 2-intersections, and provides better bounds for the robustness for many independence systems such as b-matchings, hypergraph matchings, matroid pintersections, and unions of vertex disjoint paths. Furthermore, we provide bounds of the robustness for nonlinear weight functions such as submodular and convex quadratic functions. We also extend our results to independence systems in the integral lattice with separable concave weight functions.

AB - An independence system F is one of the most fundamental combinatorial concepts, which includes a variety of objects in graphs and hypergraphs such as matchings, stable sets, and matroids. We discuss the robustness for independence systems, which is a natural generalization of the greedy property of matroids. For a real number α > 0, a set X ∈ F is said to be α-robust if for any k, it includes an α-approximation of the maximum k-independent set, where a set Y in F is called k-independent if the size |Y | is at most k. In this paper, we show that every independence system has a 1/√μ(F)- robust independent set, where μ(F) denotes the exchangeability of F. Our result contains a classical result for matroids and the ones of Hassin and Rubinstein [SIAM J. Discrete Math., 15 (2002), pp. 530-537] for matchings and Fujita, Kobayashi, and Makino [SIAM J. Discrete Math., 27 (2013), pp. 1234-1256] for matroid 2-intersections, and provides better bounds for the robustness for many independence systems such as b-matchings, hypergraph matchings, matroid pintersections, and unions of vertex disjoint paths. Furthermore, we provide bounds of the robustness for nonlinear weight functions such as submodular and convex quadratic functions. We also extend our results to independence systems in the integral lattice with separable concave weight functions.

KW - Exchangeability

KW - Independence systems

KW - Matroids

KW - Robustness

UR - http://www.scopus.com/inward/record.url?scp=84887936554&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84887936554&partnerID=8YFLogxK

U2 - 10.1137/120899480

DO - 10.1137/120899480

M3 - Article

AN - SCOPUS:84887936554

SN - 0895-4801

VL - 27

SP - 1257

EP - 1273

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -