Objective functions with redundant domains |
| |
Authors: | Fatima Affif Chaouche Carrie Rutherford Robin Whitty |
| |
Affiliation: | 1. University of Sciences and Technology Houari Boumediene, Algiers, Algeria 2. London South Bank University, London, UK
|
| |
Abstract: | Let $(E,{ mathcal{A}})$ be a set system consisting of a finite collection ${ mathcal{A}}$ of subsets of a ground set E, and suppose that we have a function ? which maps ${ mathcal{A}}$ into some set S. Now removing a subset K from E gives a restriction ${ mathcal{A}}(bar{K})$ to those sets of ${ mathcal{A}}$ disjoint from K, and we have a corresponding restriction $phi|_{hspace {.02in}{ mathcal{A}}(bar{K})}$ of our function ?. If the removal of K does not affect the image set of ?, that is $mbox {Im}(phi|_{hspace {.02in}{ mathcal{A}}(bar{X})})=mbox {Im}(phi)$ , then we will say that K is a kernel set of ${ mathcal{A}}$ with respect to ?. Such sets are potentially useful in optimisation problems defined in terms of ?. We will call the set of all subsets of E that are kernel sets with respect to ? a kernel system and denote it by $mathrm {Ker}_{phi}({ mathcal{A}})$ . Motivated by the optimisation theme, we ask which kernel systems are matroids. For instance, if ${ mathcal{A}}$ is the collection of forests in a graph G with coloured edges and ? counts how many edges of each colour occurs in a forest then $mathrm {Ker}_{phi}({ mathcal{A}})$ is isomorphic to the disjoint sum of the cocycle matroids of the differently coloured subgraphs; on the other hand, if ${ mathcal{A}}$ is the power set of a set of positive integers, and ? is the function which takes the values 1 and 0 on subsets according to whether they are sum-free or not, then we show that $mathrm {Ker}_{phi}({ mathcal{A}})$ is essentially never a matroid. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|