Constrained Submodular Minimisation
Open access
Autor(in)
Datum
2017Typ
- Master Thesis
ETH Bibliographie
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. Mehr anzeigen
Persistenter Link
https://doi.org/10.3929/ethz-b-000518694Publikationsstatus
publishedBeteiligte
Referent: Zenklusen, Rico
Verlag
ETH Zurich, Institute for Operations ResearchThema
Mathematical Optimisation; Combinatorial Optimization; Submodular function minimization; congruency constraintsOrganisationseinheit
09487 - Zenklusen, Rico / Zenklusen, Rico
ETH Bibliographie
yes
Altmetrics