Constrained Submodular Minimisation
From Parity Families to Congruency Constraints
OPEN ACCESS
Loading...
Author / Producer
Date
2017
Publication Type
Master Thesis
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Editor
Contributors
Examiner : Zenklusen, Rico
Book title
Journal / series
Volume
Pages / Article No.
Publisher
ETH Zurich, Institute for Operations Research
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Mathematical Optimisation; Combinatorial Optimization; Submodular function minimization; congruency constraints
Organisational unit
09487 - Zenklusen, Rico / Zenklusen, Rico