An Improved Algorithm for Online Min-Sum Set Cover
Authors: Marcin Bienkowski, Marcin Mucha
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We construct a computationally efficient randomized algorithm whose competitive ratio (ALG-to-OPT cost ratio) is O(r2) and prove the existence of a deterministic O(r4)-competitive algorithm. |
| Researcher Affiliation | Academia | Marcin Bienkowski,1 Marcin Mucha 2 1 University of Wroclaw 2 University of Warsaw marcin.bienkowski@cs.uni.wroc.pl, mucha@mimuw.edu.pl |
| Pseudocode | Yes | Routine 1: FETCH(z), where z is any element and Algorithm 2: LAZY-MOVE-ALL-TO-FRONT |
| Open Source Code | No | The paper does not provide any statements or links regarding the public availability of its source code. |
| Open Datasets | No | The paper is theoretical and does not involve experimental evaluation on datasets. Therefore, it does not provide access information for a dataset. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental evaluation on datasets, thus no dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not conduct experiments, so no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not conduct experiments, so no software dependencies are mentioned. |
| Experiment Setup | No | The paper is theoretical and does not conduct experiments, so no experimental setup details are provided. |