Simple Randomized Rounding for Max-Min Eigenvalue Augmentation
Authors: Jourdain Lamperski, Haeseong Yang, Oleg Prokopyev
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that a simple randomized rounding method provides a constant-factor approximation if the optimal increase is sufficiently large, specifically, if OPT − λmin(M) = Ω(R ln k), where OPT is the optimal value, and R is the maximum trace of an augmentation matrix. To establish the guarantee, we derive a matrix concentration inequality that is of independent interest. ... Finally, we plan to explore the empirical approximation performance of simple randomized rounding through a computational study. |
| Researcher Affiliation | Academia | 1Department of Industrial Engineering, University of Pittsburgh, 1025 Benedum Hall, Pittsburgh, PA 15261, USA 2Department of Business Administration, University of Zurich, Plattenstrasse 14, CH 8032 Zurich. Correspondence to: Jourdain Lamperski <EMAIL>. |
| Pseudocode | No | The paper describes a 'simple randomized rounding method' and its theoretical analysis, but it does not present this method or any other procedure in a structured pseudocode or algorithm block. |
| Open Source Code | No | Finally, we plan to explore the empirical approximation performance of simple randomized rounding through a computational study. |
| Open Datasets | No | The paper discusses theoretical problems like 'Bayesian E-optimal design' and 'maximum algebraic connectivity augmentation problems' as applications, which involve general problem formulations (e.g., 'design points x1, . . . , xm Rn'). It does not, however, conduct experiments using specific, named datasets nor provide access information for any such datasets. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments that would involve dataset splits. |
| Hardware Specification | No | The paper focuses on theoretical derivations and proofs; therefore, no hardware specifications for experiments are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper presents theoretical results, including a matrix concentration inequality and an approximation guarantee for a randomized rounding method. There are no experimental results, and thus no details on experimental setup or hyperparameters are provided. |