English
Polski
REPORT A PROBLEM
LINKS
Resource link (short)
http://zasobynauki.pl/zasoby/78457Resource link (repository)
https://id.e-science.pl/records/78457Resource metadata
| Title |
Probabilistic properties of threshold ang greedy algorithms for the binary knapsack problem (PN-1986-03) |
|---|---|
| Persons |
Authors:
Marek Sylwester Libura, Krzysztof Marcin Szkatuła
Partner: Systems Research Institute Polish Academy of Sciences, Warsaw |
| Description |
In this paper the threshold algorithm for the binary knapsack problem is considered and its connections with well-known greedy algorithm is analyzed. Probabilistic analysis of the threshold algorithm in the asymptotic case (for large sizes of problems) is performed. It is known that for a given class of random knapsack problems and for any sizes n of a problem, a threshold value can be found such that the corresponding threshold solution is both a greedy and optimal solution of the knapsack problem with a slightly perturbed right-hand side of the constraint. The perturbation is asymptotically equal to zero, almost surely. (English) |
| Keywords | "zachłanny algorytm"@pl, "binary knapsack problem"@en, "probabilistic properties"@en, "greedy algorithm"@en, "własności probabilistyczne"@pl, "binarny problem plecakowy"@pl |
| Classification |
Resource type:
article, chapter Scientific discipline: Dziedzina nauk ścisłych i przyrodniczych / informatyka (2018) Destination group: pupils, students, scientists Harmful content: No |
| Characteristics |
Title of source document: PN-1986-03
Place of publication: Warszawa Publisher: IBSPAN Time of publication: 1986 From page: 1 To page: 20 Resource language: English |
| License | CC BY-SA 4.0 |
| Technical information |
Submitter: Anna Wasilewska Availability date: 28-10-2022 |
| Collections | Kolekcja Instytutu Badań Systemowych PAN w Warszawie |
Citation
Marek Sylwester Libura, Krzysztof Marcin Szkatuła. Probabilistic properties of threshold ang greedy algorithms for the binary knapsack problem (PN-1986-03). [article, chapter] Available in Atlas of Open Science Resources, . License: CC BY-SA 4.0, https://creativecommons.org/licenses/by-sa/4.0/legalcode.pl. Date of access: DD.MM.RRRR.
Similar resources
Wybrane techniki przybliżonego rozwiązywania zadań programowania całkowitoliczbowego (PN-1981-18)
Krzysztof Szkatuła, article, chapter, Systems Research Institute Polish Academy of Sciences, Warsaw, Dziedzina nauk ścisłych i przyrodniczych / informatyka (2018)
Uczenie maszynowe na podstawie przykładów w przypadku błędów w danych
Grażyna Szkatuła, thesis, Systems Research Institute Polish Academy of Sciences, Warsaw, dziedzina nauk technicznych / informatyka (2011)
On probabilistic properties of greedy-like algorithms for the binary knapsack problem (PN-1987-13)
Marek Libura, Krzysztof Szkatuła, article, chapter, Systems Research Institute Polish Academy of Sciences, Warsaw, Dziedzina nauk ścisłych i przyrodniczych / informatyka (2018)
Analiza metod probabilistycznych optymalizacji dyskretnej
Krzysztof Szkatuła, thesis, Systems Research Institute Polish Academy of Sciences, Warsaw, dziedzina nauk technicznych / automatyka i robotyka (2011)
On probabilistic properties of greedy-like algorithms for the binary knapsack problem (PN-1987-13)
Marek Libura, Krzysztof Szkatuła, article, chapter, Systems Research Institute Polish Academy of Sciences, Warsaw, Dziedzina nauk ścisłych i przyrodniczych / informatyka (2018)
ON solving placement and routing problems in telephone exchange unit design (PN-1988-03)
Marek Libura, Jarosław Sikorski, Krzysztof Dudziński, article, chapter, Systems Research Institute Polish Academy of Sciences, Warsaw, Dziedzina nauk inżynieryjno-technicznych / automatyka, elektronika i elektrotechnika (2018)