- This package implements the Greedy Cover algorithm for multisets
in C++ and exposes it to Python. Given a universe of elements U, and a family of subsets F = {S1, …, Sn} of U, the set cover problem asks to find the smallest number of sets in F such that every element of U appears in at least one such set. This can be extended to a multicover problem, where we ask that every element be included at least k sets. This in turn, can be extended to accomodate multisets, where each element in Si also has a given multiplicity.
The set cover problem is NP hard. The best known algorithm is a greedy approach that iteratively selects the set with the largest number of elements that have not been covered yet. This algorithm has a log(n)-approximation guarantee where n is the size of the largest set. The same guarantee also applies to the multicover problem, as well as the multiset multicover problem (n here corresponds to the size of the largest set, counting multiplicities).
1 maintainer
Metadata
1 maintainer
Release files for multiset-multicover 1.0
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | |
|---|---|---|---|
| multiset_multicover-1.0.tar.gz | 11.9 kB | Details |
Built distributions (wheels)
Total release size: 2.8 MB
Release files / multiset_multicover-1.0.tar.gz
| Download URL | multiset_multicover-1.0.tar.gz |
|---|---|
| Size | 11.9 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
c1f8ccbf5ec583208b2c621167953fc5d967650fb9c8da27fcf69c65cea28ad8
|
|
BLAKE2b-256 checksum How to use checksums |
ec05bbf0285c3d5fb1934f9eb723ab296320a57f0cde90fbf9ccf185b0b817fb
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp311-cp311-win_amd64.whl
| Download URL | multiset_multicover-1.0-cp311-cp311-win_amd64.whl |
|---|---|
| Size | 23.7 kB |
| Tags | CPython 3.11 Windows x86-64 |
|
SHA-256 checksum How to use checksums |
285e800eebc51fb95c4d9c781f54359a387845c08fcc29eb8a371c97fa91e9dd
|
|
BLAKE2b-256 checksum How to use checksums |
a5bda8a04764b4df5f988f436db45e2378885d719ea7e069acc0d829b6fb6ecf
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp311-cp311-win32.whl
| Download URL | multiset_multicover-1.0-cp311-cp311-win32.whl |
|---|---|
| Size | 21.2 kB |
| Tags | CPython 3.11 Windows x86-32 |
|
SHA-256 checksum How to use checksums |
43501b8c03632ac5c67ce626f27b76c8aaa36ff2394239f9726120519ede5715
|
|
BLAKE2b-256 checksum How to use checksums |
5c6b280ccf943f578983682c573c8e9df8eacb6eff5cb6643ed45d291b001625
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
| Download URL | multiset_multicover-1.0-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl |
|---|---|
| Size | 246.1 kB |
| Tags | CPython 3.11 Linux glibc 2.17+ x86-64 |
|
SHA-256 checksum How to use checksums |
b471d606fa76db0208d693835715011f52108dc6cd45668c2f9d56756db4363a
|
|
BLAKE2b-256 checksum How to use checksums |
2d4ecdfa3b477e1b8488708c6727c703143e438844bdb07aca265c46ed44afae
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp311-cp311-manylinux_2_17_i686.manylinux2014_i686.whl
| Download URL | multiset_multicover-1.0-cp311-cp311-manylinux_2_17_i686.manylinux2014_i686.whl |
|---|---|
| Size | 238.0 kB |
| Tags | CPython 3.11 Linux glibc 2.17+ x86-32 |
|
SHA-256 checksum How to use checksums |
2a67a8589dd876525ac70d11fca879fa8e93eb9b73280bfa209b7f5372357648
|
|
BLAKE2b-256 checksum How to use checksums |
d156375e21751f6c9f8db95cbde12a41accab75f71867e9e156317852a867d03
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp311-cp311-macosx_10_9_x86_64.whl
| Download URL | multiset_multicover-1.0-cp311-cp311-macosx_10_9_x86_64.whl |
|---|---|
| Size | 27.8 kB |
| Tags | CPython 3.11 macOS 10.9+ x86-64 |
|
SHA-256 checksum How to use checksums |
f43673779d63f0c6922d5f97d45b04cd784a76eb45655ab1bb398811dc77eb71
|
|
BLAKE2b-256 checksum How to use checksums |
7cbd543735aefedc41a5fb0d8337505c8b54337b5bcd2939d7f17e17cf0efd2d
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp310-cp310-win_amd64.whl
| Download URL | multiset_multicover-1.0-cp310-cp310-win_amd64.whl |
|---|---|
| Size | 23.7 kB |
| Tags | CPython 3.10 Windows x86-64 |
|
SHA-256 checksum How to use checksums |
ab10c5414f89f932b89099b06071ab996b174d5e1b04827fba4b98f4075fcd71
|
|
BLAKE2b-256 checksum How to use checksums |
ea0d47f71244d34872ce577f4977f570c67145f6a489e7808c88c93d5c30aea6
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp310-cp310-win32.whl
| Download URL | multiset_multicover-1.0-cp310-cp310-win32.whl |
|---|---|
| Size | 21.2 kB |
| Tags | CPython 3.10 Windows x86-32 |
|
SHA-256 checksum How to use checksums |
d3c26b79ca6ca8435fbf6c5d95a1ab65d1aa32dc6975cd5fdad922f6405b5cd9
|
|
BLAKE2b-256 checksum How to use checksums |
4aca51b6f39a34290ea6849154013aad512e157b4c71846efc84b12d37b57427
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
| Download URL | multiset_multicover-1.0-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl |
|---|---|
| Size | 245.8 kB |
| Tags | CPython 3.10 Linux glibc 2.17+ x86-64 |
|
SHA-256 checksum How to use checksums |
bf3e14d42e45ea6fed0d20ea3ba2a72007302396f6b129726a63c8681a7f4822
|
|
BLAKE2b-256 checksum How to use checksums |
9742f6a93d3db5d4a7971d2eca198cab83702484957f75548ab8045335ef8426
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp310-cp310-manylinux_2_17_i686.manylinux2014_i686.whl
| Download URL | multiset_multicover-1.0-cp310-cp310-manylinux_2_17_i686.manylinux2014_i686.whl |
|---|---|
| Size | 237.6 kB |
| Tags | CPython 3.10 Linux glibc 2.17+ x86-32 |
|
SHA-256 checksum How to use checksums |
6f81eddc6894abe4a13325d49df31aa93c2abde3e4a036212c0fbe11b86f3da5
|
|
BLAKE2b-256 checksum How to use checksums |
f14e418cab8d94c723a698af3fa2d4d3e4424c5abecd5ad86b80f0c7109bd4e3
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp310-cp310-macosx_10_9_x86_64.whl
| Download URL | multiset_multicover-1.0-cp310-cp310-macosx_10_9_x86_64.whl |
|---|---|
| Size | 27.8 kB |
| Tags | CPython 3.10 macOS 10.9+ x86-64 |
|
SHA-256 checksum How to use checksums |
c5569d0a3d1bb0791b77dcbdf52a9e96c165b9cea032cf8d26c49a460c1c6f63
|
|
BLAKE2b-256 checksum How to use checksums |
9e530a826f213bf5a66f8039327bc14affe97f88ae97093cd6fd0a05b299d7eb
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp39-cp39-win_amd64.whl
| Download URL | multiset_multicover-1.0-cp39-cp39-win_amd64.whl |
|---|---|
| Size | 23.7 kB |
| Tags | CPython 3.9 Windows x86-64 |
|
SHA-256 checksum How to use checksums |
4d392b5ccee2cb762012c1fb656720a82720a6af6e8ab5d3ee19b686bb2db46f
|
|
BLAKE2b-256 checksum How to use checksums |
5bbc37e7793e5364e5545dd3a2fba0dd67647fb2da5c7c0cef6e08af235c132b
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp39-cp39-win32.whl
| Download URL | multiset_multicover-1.0-cp39-cp39-win32.whl |
|---|---|
| Size | 21.2 kB |
| Tags | CPython 3.9 Windows x86-32 |
|
SHA-256 checksum How to use checksums |
a172f5da90369862d7e9b892d561cc76b550906a20f6cfc9e30b39da8c18e61f
|
|
BLAKE2b-256 checksum How to use checksums |
9fe09a80b7b883b25d5e8a29fc4ee3f860f992ba599c90c24b68fc2d8b074552
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
| Download URL | multiset_multicover-1.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl |
|---|---|
| Size | 245.6 kB |
| Tags | CPython 3.9 Linux glibc 2.17+ x86-64 |
|
SHA-256 checksum How to use checksums |
1fca5d7e4d1df1b67a7eb36ef41d7f7863ca681caba99fbdb58572e0a776a864
|
|
BLAKE2b-256 checksum How to use checksums |
69a74de08aaaa3f36eabd410ee23320dbf0a7e8ac0af4251971d0c0399b85ead
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp39-cp39-manylinux_2_17_i686.manylinux2014_i686.whl
| Download URL | multiset_multicover-1.0-cp39-cp39-manylinux_2_17_i686.manylinux2014_i686.whl |
|---|---|
| Size | 237.4 kB |
| Tags | CPython 3.9 Linux glibc 2.17+ x86-32 |
|
SHA-256 checksum How to use checksums |
471f98d968cbe0f8a05d291c9d991499b90416e5e3c3f7bfe045c034617dd0b9
|
|
BLAKE2b-256 checksum How to use checksums |
b2a0cbc962fc9e354d5372963e5616b034d823e02416828b3611bf3a3ad82623
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp39-cp39-macosx_10_9_x86_64.whl
| Download URL | multiset_multicover-1.0-cp39-cp39-macosx_10_9_x86_64.whl |
|---|---|
| Size | 27.8 kB |
| Tags | CPython 3.9 macOS 10.9+ x86-64 |
|
SHA-256 checksum How to use checksums |
a0dd014191abf34625694bcd897a0ca4fe234eb1b83fb4326935cbc7a08e5880
|
|
BLAKE2b-256 checksum How to use checksums |
043539c2c41a83870089a479e34661a2b2a61c011ed501cc8fdc323aa622be7c
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp38-cp38-win_amd64.whl
| Download URL | multiset_multicover-1.0-cp38-cp38-win_amd64.whl |
|---|---|
| Size | 23.7 kB |
| Tags | CPython 3.8 Windows x86-64 |
|
SHA-256 checksum How to use checksums |
a2b1d37321faa127a50c1e5887c76ced5bc7d75408c4206fc3cd7a70d2ce6baf
|
|
BLAKE2b-256 checksum How to use checksums |
ccbf354496e87517821b65d3f4fe28d14bb91b71b53fc42bd58ff6f1ecd40601
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp38-cp38-win32.whl
| Download URL | multiset_multicover-1.0-cp38-cp38-win32.whl |
|---|---|
| Size | 21.2 kB |
| Tags | CPython 3.8 Windows x86-32 |
|
SHA-256 checksum How to use checksums |
61c970e50bc4dc71ea7d444616fd2d0aa0cdb6f8e626097c740240a16821d6a8
|
|
BLAKE2b-256 checksum How to use checksums |
0c9f0f4efa40614959ea07112faa5b4a2445324cf0cf3fce1e39a0f3a529ecc8
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
| Download URL | multiset_multicover-1.0-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl |
|---|---|
| Size | 245.2 kB |
| Tags | CPython 3.8 Linux glibc 2.17+ x86-64 |
|
SHA-256 checksum How to use checksums |
d8287552b58ba5258dbd6f84ff870d86f26fa3839161266eef40290b228bc945
|
|
BLAKE2b-256 checksum How to use checksums |
a1e060fe9d32d60622c4dec752180e54f8d9323d5eb9f082d9bb0c90844b219b
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp38-cp38-manylinux_2_17_i686.manylinux2014_i686.whl
| Download URL | multiset_multicover-1.0-cp38-cp38-manylinux_2_17_i686.manylinux2014_i686.whl |
|---|---|
| Size | 236.9 kB |
| Tags | CPython 3.8 Linux glibc 2.17+ x86-32 |
|
SHA-256 checksum How to use checksums |
d9493adc916e61df2feed8c621e9bf76dbb5601bc6cfd2af18a6a69ea7d4dc9c
|
|
BLAKE2b-256 checksum How to use checksums |
e31d754f66b366fb76b7a8709f1dadad6f68eb90ea163a16cbdd69bad35da6bf
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp38-cp38-macosx_10_9_x86_64.whl
| Download URL | multiset_multicover-1.0-cp38-cp38-macosx_10_9_x86_64.whl |
|---|---|
| Size | 27.7 kB |
| Tags | CPython 3.8 macOS 10.9+ x86-64 |
|
SHA-256 checksum How to use checksums |
56b92eeff64ed0ad502cb23bdc203c9cb7a348d6ad72e11f940522a956c20c17
|
|
BLAKE2b-256 checksum How to use checksums |
ca2d9e11aea4c26fbb7cec5b96aefdb8f7cf9789e57d3656b5c3adbddcdc1d6b
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp37-cp37m-win_amd64.whl
| Download URL | multiset_multicover-1.0-cp37-cp37m-win_amd64.whl |
|---|---|
| Size | 23.7 kB |
| Tags | CPython 3.7 CPython 3.7 pymalloc Windows x86-64 |
|
SHA-256 checksum How to use checksums |
876cb989a1317adab8567c19bd2b0bffa7f5d03f2faa9f114fb46e033bdfb0a5
|
|
BLAKE2b-256 checksum How to use checksums |
1d32b94ef3ee682513c7c2585740ab761c834f8d9a7e77dd92934db756a1e424
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp37-cp37m-win32.whl
| Download URL | multiset_multicover-1.0-cp37-cp37m-win32.whl |
|---|---|
| Size | 21.2 kB |
| Tags | CPython 3.7 CPython 3.7 pymalloc Windows x86-32 |
|
SHA-256 checksum How to use checksums |
0f175a8ffd0d1d86f86fe155339c16b62a4fa7a87f258149f8e5e2f1cb62e1ac
|
|
BLAKE2b-256 checksum How to use checksums |
b24cd155aa2ba57ed602bf7b445b322e4c1ecf43b52d3b589074497f471ef902
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
| Download URL | multiset_multicover-1.0-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl |
|---|---|
| Size | 245.0 kB |
| Tags | CPython 3.7 CPython 3.7 pymalloc Linux glibc 2.17+ x86-64 |
|
SHA-256 checksum How to use checksums |
205429f9ed906ad96d021119c4b703576766a25e4e8c946d56fc563a328a29d7
|
|
BLAKE2b-256 checksum How to use checksums |
663556d2f93c3054d2ef1c1f6e65d0f1ff9c11858db1e97b1c9f767717fecefd
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp37-cp37m-manylinux_2_17_i686.manylinux2014_i686.whl
| Download URL | multiset_multicover-1.0-cp37-cp37m-manylinux_2_17_i686.manylinux2014_i686.whl |
|---|---|
| Size | 236.6 kB |
| Tags | CPython 3.7 CPython 3.7 pymalloc Linux glibc 2.17+ x86-32 |
|
SHA-256 checksum How to use checksums |
e689b4d0c6a6cf397622ee49d12fd83aaa17eb7e3bbe72aa7247cd9f7d1f9277
|
|
BLAKE2b-256 checksum How to use checksums |
71ac249dce870be756bc3c3d47c8baa8d1e57460fd1d1d58f036d622dc830bf4
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
Release files / multiset_multicover-1.0-cp37-cp37m-macosx_10_9_x86_64.whl
| Download URL | multiset_multicover-1.0-cp37-cp37m-macosx_10_9_x86_64.whl |
|---|---|
| Size | 27.6 kB |
| Tags | CPython 3.7 CPython 3.7 pymalloc macOS 10.9+ x86-64 |
|
SHA-256 checksum How to use checksums |
1cfe40988faa8cba58589c3d9ccf72ccf683a8555fa1d9021cf383bbfac68d51
|
|
BLAKE2b-256 checksum How to use checksums |
e2d2f3c15d05b258f82c9e314c397c7dbf55bbfdbd91068c5b97f632da7336e8
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.9.14
|
