Probability-boosting technique for combinatorial optimization
In many combinatorial optimization problems we want a particular set of k out of n items with some certain properties (or constraints). These properties may involve the k items. In the worst case a deterministic algorithm must scan n−k items in the set to verify the k items. If we pick a set of k it...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
PeerJ Inc.
2024-11-01
|
| Series: | PeerJ Computer Science |
| Subjects: | |
| Online Access: | https://peerj.com/articles/cs-2499.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1846159969187004416 |
|---|---|
| author | Sanpawat Kantabutra |
| author_facet | Sanpawat Kantabutra |
| author_sort | Sanpawat Kantabutra |
| collection | DOAJ |
| description | In many combinatorial optimization problems we want a particular set of k out of n items with some certain properties (or constraints). These properties may involve the k items. In the worst case a deterministic algorithm must scan n−k items in the set to verify the k items. If we pick a set of k items randomly and verify the properties, it will take about (n/k)k verifications, which can be a really large number for some values of k and n. In this article we introduce a significantly faster randomized strategy with very high probability to pick the set of such k items by amplifying the probability of obtaining a target set of k items and show how this probability boosting technique can be applied to solve three different combinatorial optimization problems efficiently. In all three applications algorithms that use the probability boosting technique show superiority over their deterministic counterparts. |
| format | Article |
| id | doaj-art-0503723bac6d4fe48b0de6b5986da1a8 |
| institution | Kabale University |
| issn | 2376-5992 |
| language | English |
| publishDate | 2024-11-01 |
| publisher | PeerJ Inc. |
| record_format | Article |
| series | PeerJ Computer Science |
| spelling | doaj-art-0503723bac6d4fe48b0de6b5986da1a82024-11-22T15:05:17ZengPeerJ Inc.PeerJ Computer Science2376-59922024-11-0110e249910.7717/peerj-cs.2499Probability-boosting technique for combinatorial optimizationSanpawat KantabutraIn many combinatorial optimization problems we want a particular set of k out of n items with some certain properties (or constraints). These properties may involve the k items. In the worst case a deterministic algorithm must scan n−k items in the set to verify the k items. If we pick a set of k items randomly and verify the properties, it will take about (n/k)k verifications, which can be a really large number for some values of k and n. In this article we introduce a significantly faster randomized strategy with very high probability to pick the set of such k items by amplifying the probability of obtaining a target set of k items and show how this probability boosting technique can be applied to solve three different combinatorial optimization problems efficiently. In all three applications algorithms that use the probability boosting technique show superiority over their deterministic counterparts.https://peerj.com/articles/cs-2499.pdfRandomized algorithmsAlgorithm design and analysis |
| spellingShingle | Sanpawat Kantabutra Probability-boosting technique for combinatorial optimization PeerJ Computer Science Randomized algorithms Algorithm design and analysis |
| title | Probability-boosting technique for combinatorial optimization |
| title_full | Probability-boosting technique for combinatorial optimization |
| title_fullStr | Probability-boosting technique for combinatorial optimization |
| title_full_unstemmed | Probability-boosting technique for combinatorial optimization |
| title_short | Probability-boosting technique for combinatorial optimization |
| title_sort | probability boosting technique for combinatorial optimization |
| topic | Randomized algorithms Algorithm design and analysis |
| url | https://peerj.com/articles/cs-2499.pdf |
| work_keys_str_mv | AT sanpawatkantabutra probabilityboostingtechniqueforcombinatorialoptimization |