ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P3.03
https://doi.org/10.26493/1855-3974.2701.b7d
(Also available at http://amc-journal.eu)
An online bin-packing problem with an
underlying ternary structure
Helmut Prodinger
Mathematics Department, Stellenbosch University, 7602 Stellenbosch, South Africa and
NITheCS (National Institute for Theoretical and Computational Sciences), South Africa
Received 19 September 2021, accepted 30 June 2023, published online 12 June 2024
Abstract
Following an original idea by Knödel, an online bin-packing problem is considered
where the large items arrive in double-packs. The dual problem where the small items
arrive in double-packs is also considered. The enumerations have a ternary random walk
flavour, and for the enumeration, the kernel method is employed.
Keywords: Knödel walks, third-order recursion, kernel method, coefficient extraction, state diagram.
Math. Subj. Class. (2020): 05A15, 68R05
E-mail address: hproding@sun.ac.za (Helmut Prodinger)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
ISSN 1855-3966 (tiskana izd.), ISSN 1855-3974 (elektronska izd.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P3.03
https://doi.org/10.26493/1855-3974.2701.b7d
(Dostopno tudi na http://amc-journal.eu)
Spletni problem pakiranja v koše s ternarno
strukturo
Helmut Prodinger
Mathematics Department, Stellenbosch University, 7602 Stellenbosch, South Africa and
NITheCS (National Institute for Theoretical and Computational Sciences), South Africa
Prejeto 19. septembra 2021, sprejeto 30. junija 2023, objavljeno na spletu 12. junija 2024
Povzetek
Sledeč izvorno Knödlovi ideji se spletni problem pakiranja v koše pojavi takrat, ko ve-
liki predmeti prispejo v dvojnih paketih. Obravnavamo tudi dualni problem, kjer v dvojnih
paketih prispejo majhni predmeti. Naštevanja imajo pečat ternarnega naključnega spreha-
janja, za naštevanje pa se uporablja metoda jedra.
Ključne besede: Knödlovi sprehodi, rekurzija tretjega reda, metoda jedra, ekstrakcija koeficienta,
diagram stanja.
Math. Subj. Class. (2020): 05A15, 68R05
E-poštni naslov: hproding@sun.ac.za (Helmut Prodinger)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/