Abstract
Submodular maximization and set systems play a major role in combinatorial optimization. It is long known that the greedy algorithm provides a 1/(k + 1)-approximation for maximizing a monotone submodular function over a k-system. For the special case of k-matroid intersection, a local search approach was recently shown to provide an improved approximation of 1 / (k + δ) for arbitrary δ > 0. Unfortunately, many fundamental optimization problems are represented by a k-system which is not a k-intersection. An interesting question is whether the local search approach can be extended to include such problems.
We answer this question affirmatively. Motivated by the b-matching and k-set packing problems, as well as the more general matroid k-parity problem, we introduce a new class of set systems called k-exchange systems, that includes k-set packing, b-matching, matroid k-parity in strongly base orderable matroids, and additional combinatorial optimization problems such as: independent set in (k + 1)-claw free graphs, asymmetric TSP, job interval selection with identical lengths and frequency allocation on lines. We give a natural local search algorithm which improves upon the current greedy approximation, for this new class of independence systems. Unlike known local search algorithms for similar problems, we use counting arguments to bound the performance of our algorithm.
Moreover, we consider additional objective functions and provide improved approximations for them as well. In the case of linear objective functions, we give a non-oblivious local search algorithm, that improves upon existing local search approaches for matroid k-parity.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Anstee, R.P.: A polynomial algorithm for b-matchings: An alternative approach. Information Processing Letters 24(3), 153–157 (1987)
Berman, P.: A d/2 approximation for maximum weight independent set in d-claw free graphs. Nordic J. of Computing 7, 178–184 (2000)
Brualdi, R.A.: Comments on bases in dependence structures. Bull. of the Australian Math. Soc. 1(02), 161–167 (1969)
Brualdi, R.A.: Common transversals and strong exchange systems. J. of Combinatorial Theory 8(3), 307–329 (1970)
Brualdi, R.A.: Induced matroids. Proc. of the American Math. Soc. 29, 213–221 (1971)
Brualdi, R.A., Scrimger, E.B.: Exchange systems, matchings, and transversals. J. of Combinatorial Theory 5(3), 244–257 (1968)
Calinescu, G., Chekuri, C., Pal, M., Vondrák, J.: Maximizing a submodular set function subject to a matroid constraint. To appear in SIAM Journal on Computing, Special Issue for STOC 2008 (2008)
Chandra, B., Halldórsson, M.: Greedy local improvement and weighted set packing approximation. In: SODA, pp. 169–176 (1999)
Chekuri, C., Vondrák, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: STOC, pp. 783–792 (2011)
Conforti, M., Cornuèjols, G.: Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the rado-edmonds theorem. Disc. Appl. Math. 7(3), 251–274 (1984)
Edmonds, J.: Matroid intersection. In: Hammer, P., Johnson, E., Korte, B. (eds.) Discrete Optimization I, Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium. Annals of Discrete Mathematics, vol. 4, pp. 39–49. Elsevier, Amsterdam (1979)
Feige, U., Mirrokni, V.S., Vondrák, J.: Maximizing non-monotone submodular functions. In: FOCS, pp. 461–471 (2007)
Feldman, M., Naor, J.S., Schwartz, R.: Nonmonotone submodular maximization via a structural continuous greedy algorithm. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6755, pp. 342–353. Springer, Heidelberg (2011)
Feldman, M., Naor, J.S., Schwartz, R.: A unified continuous greedy algorithm for submodular maximization. To appear in FOCS 2011 (2011)
Fisher, M., Nemhauser, G., Wolsey, L.: An analysis of approximations for maximizing submodular set functions - ii. Math. Prog. Study 8, 73–87 (1978)
Gharan, S.O., Vondrák, J.: Submodular maximization by simulated annealing. In: SODA, pp. 1098–1116 (2011)
Gupta, A., Roth, A., Schoenebeck, G., Talwar, K.: Constrained non-monotone submodular maximization: Offline and secretary algorithms. In: Saberi, A. (ed.) WINE 2010. LNCS, vol. 6484, pp. 246–257. Springer, Heidelberg (2010)
Hausmann, D., Korte, B.: K-greedy algorithms for independence systems. Oper. Res. Ser. A-B 22(1), 219–228 (1978)
Hausmann, D., Korte, B., Jenkyns, T.: Worst case analysis of greedy type algorithms for independence systems. Math. Prog. Study 12, 120–131 (1980)
Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating k-set packing. Comput. Complex. 15, 20–39 (2006)
Hurkens, C.A.J., Schrijver, A.: On the size of systems of sets every t of which have an sdr, with an application to the worst case ratio of heuristics for packing problems. SIAM J. Disc. Math. 2(1), 68–72 (1989)
Jenkyns, T.: The efficacy of the greedy algorithm. Cong. Num. 17, 341–350 (1976)
Jensen, P.M., Korte, B.: Complexity of matroid property algorithms. SIAM J. Computing 11(1), 184 (1982)
Kalyanasundaram, B., Pruhs, K.: An optimal deterministic algorithm for online b-matching. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol. 1180, pp. 193–199. Springer, Heidelberg (1996)
Korte, B., Hausmann, D.: An analysis of the greedy heuristic for independence systems. Annals of Discrete Math. 2, 65–74 (1978)
Lee, J., Sviridenko, M., Vondrák, J.: Submodular maximization over multiple matroids via generalized exchange properties. To appear in Mathematics of Operations Research (2009)
Lee, J., Sviridenko, M., Vondrak, J.: Matroid matching: the power of local search. In: STOC, pp. 369–378 (2010)
Lovász, L.: The matroid matching problem. In: Lovász, L., Sós, V.T. (eds.) Algebraic Methods in Graph Theory, Amsterdam (1981)
Marsh III., A.B.: Matching algorithms. PhD thesis, The Johns Hopkins University (1979)
Mestre, J.: Greedy in approximation algorithms. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 528–539. Springer, Heidelberg (2006)
Nemhauser, G., Wolsey, L.: Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3), 177–188 (1978)
Nemhauser, G., Wolsey, L., Fisher, M.: An analysis of approximations for maximizing submodular set functions - i. Math. Prog. 14(1), 265–294 (1978)
Pulleyblank, W.: Faces of matching polyhedra. PhD thesis, Deptartment of Combinatorics and Optimization, University of Waterloo (1973)
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Heidelberg (2003)
Simon, H.: Approximation algorithms for channel assignment in cellular radio networks. In: Csirik, J., Demetrovics, J., Gècseg, F. (eds.) FCT 1989. LNCS, vol. 380, pp. 405–415. Springer, Heidelberg (1989)
Soto, J.A.: A simple PTAS for weighted matroid matching on strongly base orderable matroids. To appear in LAGOS (2011)
Tong, P., Lawler, E.L., Vazirani, V.V.: Solving the weighted parity problem for gammoids by reduction to graphic matching. Technical Report UCB/CSD-82-103, EECS Department, University of California, Berkeley (April 1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Feldman, M., Naor, J.(., Schwartz, R., Ward, J. (2011). Improved Approximations for k-Exchange Systems. In: Demetrescu, C., Halldórsson, M.M. (eds) Algorithms – ESA 2011. ESA 2011. Lecture Notes in Computer Science, vol 6942. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23719-5_66
Download citation
DOI: https://doi.org/10.1007/978-3-642-23719-5_66
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-23718-8
Online ISBN: 978-3-642-23719-5
eBook Packages: Computer ScienceComputer Science (R0)