min-knapsack-with-compactness
Algorithms for the min-Knapsack problem with compactness constraints.
https://github.com/alberto-santini/min-knapsack-with-compactness
Science Score: 67.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
✓CITATION.cff file
Found CITATION.cff file -
✓codemeta.json file
Found codemeta.json file -
✓.zenodo.json file
Found .zenodo.json file -
✓DOI references
Found 5 DOI reference(s) in README -
✓Academic publication links
Links to: zenodo.org -
○Academic email domains
-
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (10.0%) to scientific vocabulary
Keywords
Repository
Algorithms for the min-Knapsack problem with compactness constraints.
Basic Info
Statistics
- Stars: 2
- Watchers: 1
- Forks: 0
- Open Issues: 0
- Releases: 1
Topics
Metadata Files
README.md

Min-Knapsack Problem with Compactness Constraints
This is a collection of algorithms to solve:
- The min-Knapsack Problem with Compactness Constraints (mKPC), a generalisation of the classical min-Knapsack problem. The mKPC arises as a sub-problem in some algorithms for change-point detection in time series analysis (such as the PRISCA algorithm) and for variable selection in genetic fine-mapping (such as the SuSiE algorithm).
- The unit-cost mKPC, a polynomially-solvable particular case of the mKPC.
This software was developed as part of the following manuscript:
bib
@article{Santini_Malaguti_2023
title={The min-Knapsack Problem with Compactness Constraints and Applications in Statistics},
author={Santini, Alberto and Malaguti, Enrico},
journal={European Journal of Operational Research},
doi={10.1016/j.ejor.2023.07.020},
year=2024,
volume=312,
issue=1,
pages={385--397}
}
You can cite this repository itself as follows:
bib
@misc{Santini_2022,
title={Algorithms for the min-Knapsack problem with compactness constraints},
author={Santini, Alberto},
date={2022-12-29},
year=2022,
doi={10.5281/zenodo.7492799},
url={https://github.com/alberto-santini/min-knapsack-with-compactness},
howpublished={Github repository}
}
Data
- Data in
data/cappello-raw-datais raw csv data from Cappello and Madrid Padilla. - Data in
data/cappello-instancesis JSON data created starting from the above csv data, usingdata/cappello_transform_raw_data.py. - Data in
data/synthetic-instancesis data generated by us usingdata/generator.py.
Licence
Released under the 2-clause BSD licence.
Refer to the file LICENSE in the repository's root directory.
Included software:
- Licence for cxxopts
- Licence for date
- Licence for nlohmann/json
- Licence for rapidcsv
Owner
- Name: Alberto Santini
- Login: alberto-santini
- Kind: user
- Location: Barcelona, Spain
- Website: http://santini.in/
- Repositories: 38
- Profile: https://github.com/alberto-santini
Citation (CITATION.cff)
cff-version: 1.2.0
message: "If you use this software, please cite it as below."
authors:
- family-names: "Santini"
given-names: "Alberto"
orcid: "https://orcid.org/0000-0002-0440-0357"
title: "Algorithms for the min-Knapsack problem with compactness constraints"
version: 0.1
doi: 10.5281/zenodo.7492799
date-released: 2020-12-29
url: "https://github.com/alberto-santini/min-knapsack-with-compactness"
preferred-citation:
type: article
authors:
- family-names: "Santini"
given-names: "Alberto"
orcid: "https://orcid.org/0000-0002-0440-0357"
- family-names: "Malaguti"
given-names: "Enrico"
journal: "European Journal of Operational Research"
title: "The min-Knapsack Problem with Compactness Constraints and Applications to Statistics"
year: 2024
volume: 312
issue: 1
start: 385
end: 397
doi: "10.1016/j.ejor.2023.07.020"