Discrete-Smoothness in Online Algorithms with Predictions
Authors: Yossi Azar, Debmalya Panigrahi, Noam Touitou
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 5 Experiments, Table 1: Competitive ratios for varying p, q, in a "mean (standard deviation)" format. Best values in each row are underlined., Figure 2: The competitive ratio for varying numbers of sets. |
| Researcher Affiliation | Collaboration | Yossi Azar Tel Aviv University azar@tau.ac.il Debmalya Panigrahi Duke University debmalya@cs.duke.edu Noam Touitou Amazon noamtwx@gmail.com |
| Pseudocode | Yes | Algorithm 1: Smooth merging framework (The combiner algorithm), Algorithm 2: TREEPROXY for Prize Collecting Facility Location with Predictions, Algorithm 3: Online Prize-Collecting Fractional Set Cover, Algorithm 4: Variant of Fotakis Algorithm for Prize-Collecting OFLP |
| Open Source Code | No | The paper does not provide a direct link to source code or explicitly state that the code for their methodology is publicly available. |
| Open Datasets | No | Our set cover instances contain 100 elements. ... We generate random costs for the sets, independently drawn from a log-normal distribution (μ= 0, σ= 1.6). For a given input, we generate a prediction in the following way: 1. Using an LP solver, we obtain an optimal fractional solution to the problem instance. 2. We randomly round the solution, such that every set appears in the prediction with probability proportional to its value in the fractional solution. 3. We apply noise to the prediction, of two types: false-positive noise, in which every set is added to the prediction with some probability p; and false-negative noise, in which every set is removed from the prediction with some probability q. |
| Dataset Splits | No | The paper does not provide specific train/validation/test dataset splits or reference predefined splits for reproducibility. |
| Hardware Specification | Yes | Our experiments were run on an AWS EC2 r5.16xlarge machine. |
| Software Dependencies | No | The paper mentions using an 'LP solver' but does not provide specific software names with version numbers for reproducibility. |
| Experiment Setup | Yes | We ran the following experiments: (a) we vary the false-positive rate p and the false-negative rate q keeping the number of sets fixed at 10000 (Table 1), and (b) we vary the number of sets in the input, fixing p= 0.005, q= 0.15 (Figure 2). |