Faster width-dependent algorithm for mixed packing and covering LPs
Authors: Digvijay Boob, Saurabh Sawlani, Di Wang
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we give a faster width-dependent algorithm for mixed packingcovering LPs. Mixed packing-covering LPs are fundamental to combinatorial optimization in computer science and operations research. Our algorithm finds a 1 ε approximate solution in time Op Nw{εq, where N is number of nonzero entries in the constraint matrix, and w is the maximum number of nonzeros in any constraint. This algorithm is faster than Nesterov s smoothing algorithm which requires Op N?nw{εq time, where n is the dimension of the problem. Our work utilizes the framework of area convexity introduced in [Sherman-FOCS 17] to obtain the best dependence on ε while breaking the infamous ℓ8 barrier to eliminate the factor of ?n. |
| Researcher Affiliation | Collaboration | Digvijay Boob Georgia Tech Atlanta, GA digvijaybb40@gatech.edu Saurabh Sawlani Georgia Tech Atlanta, GA sawlani@gatech.edu Di Wang Google AI Atlanta, GA wadi@google.com |
| Pseudocode | Yes | Algorithm 1 Area Convex Mixed Packing Covering (AC-MPC) and Algorithm 2 δ-OSO for φ |
| Open Source Code | No | The paper does not include an unambiguous statement that the authors are releasing the code for the work described, nor does it provide a direct link to a source-code repository. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and analysis. It does not mention the use of any datasets for training or evaluation, nor does it provide information about their public availability. |
| Dataset Splits | No | The paper is theoretical and does not describe experimental validation on specific datasets or provide details about training, validation, or test splits. |
| Hardware Specification | No | The paper does not mention any specific hardware used for running experiments. |
| Software Dependencies | No | The paper does not mention any specific software components with version numbers used for the implementation or experiments. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and analysis. It does not provide details about an experimental setup, such as hyperparameters or system-level training settings. |