On Constrained Boolean Pareto Optimization
Authors: Chao Qian, Yang Yu, Zhi-Hua Zhou
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This work theoretically compares Pareto optimization with a penalty approach, which is a common method transforming a constrained optimization into an unconstrained optimization. We prove that on two large classes of constrained Boolean optimization problems, minimum matroid optimization (P-solvable) and minimum cost coverage (NP-hard), Pareto optimization is more efficient than the penalty function method for obtaining the optimal and approximate solutions, respectively. |
| Researcher Affiliation | Academia | National Key Laboratory for Novel Software Technology, Nanjing University Collaborative Innovation Center of Novel Software Technology and Industrialization Nanjing 210023, China |
| Pseudocode | Yes | Algorithm 1 (The Penalty Function Method) |
| Open Source Code | No | The paper does not provide any specific information or links regarding the availability of open-source code for the methodology described. |
| Open Datasets | No | The paper focuses on theoretical analysis of algorithm running times on problem classes like 'minimum matroid optimization' and 'minimum cost coverage', rather than using specific publicly available datasets for training or evaluation. |
| Dataset Splits | No | This is a theoretical paper providing complexity analysis and proofs, and as such, it does not involve practical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical, focusing on computational complexity and running time analysis, rather than empirical evaluation. Therefore, it does not specify any hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithms and complexity analysis. It does not mention any specific software dependencies or their version numbers required for replication. |
| Experiment Setup | No | The paper is theoretical, presenting algorithms and complexity analysis rather than empirical experiments. Therefore, it does not include details about an experimental setup, hyperparameters, or training configurations. |