Approximate Multi-matroid Intersection via Iterative Refinement

André Linhares, Neil Olver, Chaitanya Swamy, Rico Zenklusen

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

We introduce a new iterative rounding technique to round a point in a matroid polytope subject to further matroid constraints. This technique returns an independent set in one matroid with limited violations of the other ones. On top of the classical steps of iterative relaxation approaches, we iteratively refine/split involved matroid constraints to obtain a more restrictive constraint system, that is amenable to iterative relaxation techniques. Hence, throughout the iterations, we both tighten constraints and later relax them by dropping constraints under certain conditions. Due to the refinement step, we can deal with considerably more general constraint classes than existing iterative relaxation/rounding methods, which typically round on one matroid polytope with additional simple cardinality constraints that do not overlap too much. We show how our rounding method, combined with an application of a matroid intersection algorithm, yields the first 2-approximation for finding a maximum-weight common independent set in 3 matroids. Moreover, our 2-approximation is LP-based, and settles the integrality gap for the natural relaxation of the problem. Prior to our work, no upper bound better than 3 was known for the integrality gap, which followed from the greedy algorithm. We also discuss various other applications of our techniques, including an extension that allows us to handle a mixture of matroid and knapsack constraints.

Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings
EditorsAndrea Lodi, Viswanath Nagarajan
PublisherSpringer Verlag
Pages299-312
Number of pages14
ISBN (Print)9783030179526
DOIs
Publication statusPublished - 1 Jan 2019
Event20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019 - Ann Arbor, United States
Duration: 22 May 201924 May 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11480 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019
CountryUnited States
CityAnn Arbor
Period22/05/1924/05/19

Fingerprint

Matroid Intersection
Iterative Refinement
Matroid
Rounding
Integrality
Independent Set
Polytope
Cardinality Constraints
Knapsack
Combined Method
Approximation
Greedy Algorithm
Overlap
Refinement
Upper bound
Iteration

Cite this

Linhares, AE., Olver, N., Swamy, C., & Zenklusen, R. (2019). Approximate Multi-matroid Intersection via Iterative Refinement. In A. Lodi, & V. Nagarajan (Eds.), Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings (pp. 299-312). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11480 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-17953-3_23
Linhares, André ; Olver, Neil ; Swamy, Chaitanya ; Zenklusen, Rico. / Approximate Multi-matroid Intersection via Iterative Refinement. Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. editor / Andrea Lodi ; Viswanath Nagarajan. Springer Verlag, 2019. pp. 299-312 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{8db91d4fe7a148a1b401bbba2399ddfc,
title = "Approximate Multi-matroid Intersection via Iterative Refinement",
abstract = "We introduce a new iterative rounding technique to round a point in a matroid polytope subject to further matroid constraints. This technique returns an independent set in one matroid with limited violations of the other ones. On top of the classical steps of iterative relaxation approaches, we iteratively refine/split involved matroid constraints to obtain a more restrictive constraint system, that is amenable to iterative relaxation techniques. Hence, throughout the iterations, we both tighten constraints and later relax them by dropping constraints under certain conditions. Due to the refinement step, we can deal with considerably more general constraint classes than existing iterative relaxation/rounding methods, which typically round on one matroid polytope with additional simple cardinality constraints that do not overlap too much. We show how our rounding method, combined with an application of a matroid intersection algorithm, yields the first 2-approximation for finding a maximum-weight common independent set in 3 matroids. Moreover, our 2-approximation is LP-based, and settles the integrality gap for the natural relaxation of the problem. Prior to our work, no upper bound better than 3 was known for the integrality gap, which followed from the greedy algorithm. We also discuss various other applications of our techniques, including an extension that allows us to handle a mixture of matroid and knapsack constraints.",
author = "André Linhares and Neil Olver and Chaitanya Swamy and Rico Zenklusen",
year = "2019",
month = "1",
day = "1",
doi = "10.1007/978-3-030-17953-3_23",
language = "English",
isbn = "9783030179526",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "299--312",
editor = "Andrea Lodi and Viswanath Nagarajan",
booktitle = "Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings",
address = "Germany",

}

Linhares, AE, Olver, N, Swamy, C & Zenklusen, R 2019, Approximate Multi-matroid Intersection via Iterative Refinement. in A Lodi & V Nagarajan (eds), Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11480 LNCS, Springer Verlag, pp. 299-312, 20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019, Ann Arbor, United States, 22/05/19. https://doi.org/10.1007/978-3-030-17953-3_23

Approximate Multi-matroid Intersection via Iterative Refinement. / Linhares, André Olver, Neil; Swamy, Chaitanya; Zenklusen, Rico.

Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. ed. / Andrea Lodi; Viswanath Nagarajan. Springer Verlag, 2019. p. 299-312 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11480 LNCS).

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Approximate Multi-matroid Intersection via Iterative Refinement

AU - Linhares, André

AU - Olver, Neil

AU - Swamy, Chaitanya

AU - Zenklusen, Rico

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We introduce a new iterative rounding technique to round a point in a matroid polytope subject to further matroid constraints. This technique returns an independent set in one matroid with limited violations of the other ones. On top of the classical steps of iterative relaxation approaches, we iteratively refine/split involved matroid constraints to obtain a more restrictive constraint system, that is amenable to iterative relaxation techniques. Hence, throughout the iterations, we both tighten constraints and later relax them by dropping constraints under certain conditions. Due to the refinement step, we can deal with considerably more general constraint classes than existing iterative relaxation/rounding methods, which typically round on one matroid polytope with additional simple cardinality constraints that do not overlap too much. We show how our rounding method, combined with an application of a matroid intersection algorithm, yields the first 2-approximation for finding a maximum-weight common independent set in 3 matroids. Moreover, our 2-approximation is LP-based, and settles the integrality gap for the natural relaxation of the problem. Prior to our work, no upper bound better than 3 was known for the integrality gap, which followed from the greedy algorithm. We also discuss various other applications of our techniques, including an extension that allows us to handle a mixture of matroid and knapsack constraints.

AB - We introduce a new iterative rounding technique to round a point in a matroid polytope subject to further matroid constraints. This technique returns an independent set in one matroid with limited violations of the other ones. On top of the classical steps of iterative relaxation approaches, we iteratively refine/split involved matroid constraints to obtain a more restrictive constraint system, that is amenable to iterative relaxation techniques. Hence, throughout the iterations, we both tighten constraints and later relax them by dropping constraints under certain conditions. Due to the refinement step, we can deal with considerably more general constraint classes than existing iterative relaxation/rounding methods, which typically round on one matroid polytope with additional simple cardinality constraints that do not overlap too much. We show how our rounding method, combined with an application of a matroid intersection algorithm, yields the first 2-approximation for finding a maximum-weight common independent set in 3 matroids. Moreover, our 2-approximation is LP-based, and settles the integrality gap for the natural relaxation of the problem. Prior to our work, no upper bound better than 3 was known for the integrality gap, which followed from the greedy algorithm. We also discuss various other applications of our techniques, including an extension that allows us to handle a mixture of matroid and knapsack constraints.

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

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

U2 - 10.1007/978-3-030-17953-3_23

DO - 10.1007/978-3-030-17953-3_23

M3 - Conference contribution

SN - 9783030179526

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 299

EP - 312

BT - Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings

A2 - Lodi, Andrea

A2 - Nagarajan, Viswanath

PB - Springer Verlag

ER -

Linhares AE, Olver N, Swamy C, Zenklusen R. Approximate Multi-matroid Intersection via Iterative Refinement. In Lodi A, Nagarajan V, editors, Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. Springer Verlag. 2019. p. 299-312. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-17953-3_23