Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Dependent randomized rounding for clustering and partition systems with knapsack constraints
Authors: David G. Harris, Thomas Pensyl, Aravind Srinivasan, Khoa Trinh
JMLR 2022 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We develop new randomized algorithms targeting such problems, and study two in particular: multi-knapsack median and multi-knapsack center. Our rounding algorithms give new approximation and pseudo-approximation algorithms for these problems. One key technical tool, which may be of independent interest, is a new tail bound analogous to Feige (2006) for sums of random variables with unbounded variances. |
| Researcher Affiliation | Collaboration | David G. Harris EMAIL Department of Computer Science, University of Maryland, College Park, MD 20742 Thomas Pensyl EMAIL Bandwidth, Inc. Raleigh, NC. Aravind Srinivasan EMAIL Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742 Khoa Trinh EMAIL Google, Mountain View, CA 94043 |
| Pseudocode | Yes | Algorithm 1 KPR(G, M, y, t) Algorithm 2 KPR(G, M, y, t), summarized Algorithm 3 FULLKPR(G, M, y, t) Algorithm 4 ROUNDSTARS(t) Algorithm 5 MULTIKNAPSACKMEDIANROUND(t) Algorithm 6 KNAPSACKCENTERMWU Algorithm 7 SINGLEKNAPSACKCENTERROUND (M, a, δ) Algorithm 8 MULTIKNAPSACKCENTERROUND (M, a, δ, t) |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code for the methodology described, nor does it provide links to a code repository. |
| Open Datasets | No | The paper discusses clustering problems and refers to a conceptual 'data-set C', but it does not describe specific datasets used for experiments or provide any access information (links, DOIs, citations) for publicly available datasets. The research is theoretical. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments on specific datasets, therefore, no dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithmic development and proofs; it does not describe any experimental setup or specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and presents algorithms and proofs. It does not mention any specific software dependencies with version numbers that would be required to reproduce experimental results. |
| Experiment Setup | No | The paper is theoretical, presenting new algorithms and their analysis. It does not include any experimental results or details about an experimental setup, such as hyperparameters or training configurations. |