Accelerating Matroid Optimization through Fast Imprecise Oracles
Authors: Franziska Eberle, Felix Hommelsheim, Alexander Lindermayr, Zhenwei Liu, Nicole Megow, Jens Schlöter
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We design and analyze practical algorithms that only use few clean queries w.r.t. the quality of the dirty oracle, while maintaining robustness against arbitrarily poor dirty oracles, approaching the performance of classic algorithms for the given problem. Notably, we prove that our algorithms are, in many respects, best-possible. [...] In this paper, we design optimal algorithms in the two-oracle model for the problem of finding a maximum-weight basis (defined later) of a matroid. |
| Researcher Affiliation | Academia | Franziska Eberle Technical University of Berlin Germany f.eberle@tu-berlin.de Felix Hommelsheim University of Bremen Germany fhommels@uni-bremen.de Alexander Lindermayr University of Bremen Germany linderal@uni-bremen.de Zhenwei Liu University of Bremen Germany zhenwei@uni-bremen.de Nicole Megow University of Bremen Germany nmegow@uni-bremen.de Jens Schlöter Centrum Wiskunde & Informatica The Netherlands jens.schloter@cwi.nl |
| Pseudocode | Yes | Algorithm 1: Find a maximum-weight basis [...] Algorithm 2: Find a maximum-weight basis (robustified) [...] Algorithm 3: Find a basis (robustified) [...] Algorithm 4: Augmenting path via dirty oracles [...] Algorithm 5: Obtaining a warm-start solution |
| Open Source Code | No | The paper is theoretical and focuses on algorithm design and analysis. It does not mention or provide any open-source code for the described methodologies or experiments. The NeurIPS checklist also indicates that the paper does not include experiments requiring code. |
| Open Datasets | No | The paper is purely theoretical and does not involve empirical studies, experiments, or the use of datasets. Therefore, it does not mention or provide access information for any publicly available or open datasets. |
| Dataset Splits | No | The paper is purely theoretical and does not involve empirical studies or the use of datasets. Consequently, it does not provide any information regarding training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and analysis. It does not involve experimental setups or computational execution that would require detailing hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not include any experimental section. Therefore, it does not specify any software dependencies with version numbers needed for replication. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and analysis. It does not describe any experimental setups, hyperparameters, or system-level training settings. |