Ticket #5827 (closed enhancement: fixed)
[with patch, positive review] knapsack: subset sum problem for super-increasing sequences
| Reported by: | mvngu | Owned by: | jkantor |
|---|---|---|---|
| Priority: | major | Milestone: | sage-4.0.1 |
| Component: | numerical | Keywords: | knapsack problems, subset sum |
| Cc: | Work issues: | ||
| Report Upstream: | Reviewers: | Mike Hansen | |
| Authors: | Minh Van Nguyen | Merged in: | 4.0.1.rc1 |
| Dependencies: | Stopgaps: |
Description (last modified by mvngu) (diff)
Since all of COIN-OR is covered by licenses that are incompatible with GNU GPL v2+, I've thought of implementing something along the lines of a knapsack problems solver. The goal of this ticket is to first implement a class for solving the subset sum problem for super-increasing sequences. The long-term goal is to implement a module for solving various knapsack problems.
Attachments
-
trac_5827-subset-sum.patch
(18.4 KB) -
added by mvngu 4 years ago.
- based on Sage 3.4.1
-
trac_5827-subset-sum.2.patch
(18.7 KB) -
added by mvngu 4 years ago.
- based on Sage 4.0
Change History
comment:1 Changed 4 years ago by mvngu
- Summary changed from crypto: subset sum problem for super-increasing sequences to [with patch, needs review] crypto: subset sum problem for super-increasing sequences
comment:2 Changed 4 years ago by mvngu
- Summary changed from [with patch, needs review] crypto: subset sum problem for super-increasing sequences to [with patch, not ready for review] crypto: subset sum problem for super-increasing sequences
comment:3 Changed 4 years ago by mvngu
- Summary changed from [with patch, not ready for review] crypto: subset sum problem for super-increasing sequences to [with patch, needs review] crypto: subset sum problem for super-increasing sequences
- Milestone changed from sage-4.0 to sage-3.4.2
comment:6 Changed 4 years ago by mvngu
- Summary changed from [with patch, needs review] crypto: subset sum problem for super-increasing sequences to [with patch, needs work] crypto: subset sum problem for super-increasing sequences
comment:7 Changed 4 years ago by mvngu
- Keywords problems, added; cryptosystem, removed
- Owner changed from somebody to jkantor
- Component changed from cryptography to numerical
- Description modified (diff)
- Summary changed from [with patch, needs work] crypto: subset sum problem for super-increasing sequences to [with patch, needs review] knapsack: subset sum problem for super-increasing sequences
Only apply trac_5827-subset-sum.2.patch. This patch depends on the patch at #6176.
comment:8 Changed 4 years ago by mhansen
- Status changed from new to closed
- Resolution set to fixed
- Summary changed from [with patch, needs review] knapsack: subset sum problem for super-increasing sequences to [with patch, positive review] knapsack: subset sum problem for super-increasing sequences
Looks good to me.
Merged in 4.0.1.rc1.
comment:10 Changed 4 years ago by mhansen
- Reviewers set to Mike Hansen
- Merged in set to 4.0.1.rc1
- Authors set to Minh Van Nguyen
Note: See
TracTickets for help on using
tickets.
The patch implements an algorithm for solving the subset sum problem for super-increasing sequences. This is useful in the Merkle-Hellman knapsack cryptosystem, which I plan to work on later.