Constrained Submodular Minimisation
Open access
Author
Date
2017Type
- Master Thesis
ETH Bibliography
yes
Altmetrics
Abstract
We study two classes of constrained submodular minimisation problems, where a submodular function f defined on a lattice family L is to be minimised over a subfamily of L. In the first class, so-called congruency constrained submodular minimisation (CSM) problems, the subfamilies are of the form F = { S ∈ L : |S| ≡ r (mod m) }. For the second class of problems, namely generalised congruency constrained submodular minimisation (GCSM) problems, we are given a constant number of fixed sets S_1, ..., S_k and consider subfamilies of the form F = { S ∈ L : ∀ i: |S_i ∩ S| ≡ r_i (mod m) }.
If m is a prime power, we provide polynomial time algorithms to solve both CSM and GCSM problems. Our algorithms rely on guessing a constant number of elements that belong to an optimal solutions and a constant number that do not. While our approaches and algorithms for CSM and GCSM problems can be seen as generalisations of a result by Goemans and Ramakrishnan for minimising submodular functions over parity families, we introduce and apply new techniques for proving correctness of the algorithms. Among others, this includes handling purely combinatorial problems on existence of set systems with certain covering properties and restricted intersections modulo m.
We also show that for strong combinatorial reasons, our current methods do not generalise to CSM and GCSM problems with moduli other than prime powers. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000518694Publication status
publishedContributors
Examiner: Zenklusen, Rico
Publisher
ETH Zurich, Institute for Operations ResearchSubject
Mathematical Optimisation; Combinatorial Optimization; Submodular function minimization; congruency constraintsOrganisational unit
09487 - Zenklusen, Rico / Zenklusen, Rico
More
Show all metadata
ETH Bibliography
yes
Altmetrics