Matroidal Approximations of Independence Systems
| Autor: | Rakesh Vohra, Sven de Vries |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) Approximations of π 0211 other engineering and technologies Independence system 02 engineering and technology Management Science and Operations Research 01 natural sciences Matroid Industrial and Manufacturing Engineering 010104 statistics & probability FOS: Mathematics Mathematics - Combinatorics 0101 mathematics Greedy algorithm Mathematics Discrete mathematics 90C27 68W99 021103 operations research Basis (linear algebra) Heuristic Applied Mathematics Zero (complex analysis) Independence (mathematical logic) Combinatorics (math.CO) Software Computer Science - Discrete Mathematics |
| Popis: | Milgrom (2017) has proposed a heuristic for determining a maximum weight basis of an independence system ${\mathcal I}$ given that we want an approximation guarantee only for sets in a prescribed ${\mathcal O}\subseteq {\mathcal I}$. This ${\mathcal O}$ reflects prior knowledge of the designer about the location of the optimal basis. The heuristic is based on finding an `inner matroid', one contained in the independence system. We show that even in the case ${\mathcal O}={\mathcal I}$ of zero additional knowledge the worst-case performance of this new heuristic can be better than that of the classical greedy algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|