Reprezentowanie cięć przy pomocy układów nierówności liniowych

• Autorzy: Pliszka Zbigniew

Identyfikatory

DOI

10.15199/13.2025.7.5

Warianty tytułu

EN

Representing cuts using systems of linear inequalities

• Języki publikacji: PL

Abstrakty

PL

W pracy [1] Richard Karp problem partycjonowania multizbiorów zakwalifikował jako najłatwiejszy z trudnych problemów. W prezentowanej pracy, nawiązującej do artykułów [2], [3] i [4], wykorzystując wprowadzone w tychże publikacjach pojęcie „cięcia”, pokazano związki pomiędzy poszczególnymi elementami liczbowego multizbioru (złożonego z liczb całkowitych dodatnich) po jego posortowaniu niemalejąco i układami nierówności wynikającymi z właściwości badanego cięcia.

EN

In [1], Richard Karp classified the problem of partitioning multisets as the easiest of the hard problems. In the presented work, referring to articles [2], [3] and [4], using the concept of “cut” (“cutting”) introduced in those publications, the relations between individual elements of a numerical multiset (composed of positive integers) after its nondecreasing sorting and systems of inequalities resulting from the properties of the examined cut were shown.

Słowa kluczowe

PL

multizbiór; problem podziału

EN

multiset; number partitioning

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Elektronika : konstrukcje, technologie, zastosowania
• Rocznik: 2025
• Tom: Vol. 66, Nr 7
• Strony: 23--25
• Opis fizyczny: Bibliogr. 7 poz., tab.

Twórcy

autor

Pliszka Zbigniew

• Politechnika Wrocławska, Wydział Informatyki i Telekomunikacji

• https://orcid.org/0000-0001-8466-037X

Bibliografia

• [1] Richard M. Karp, Reducibility among combinatorial problems, in: Complexity of computer computations, Springer, 1972, pp. 85–103.
• [2] Zbigniew Pliszka. On some similarity of finite sets (and what we can say today about certain old problem). Information Sciences, 590:296–321, 2022.
• [3] Zbigniew Pliszka. Nieliniowe przekształcenia dla podziałów w kostce jednostkowej. Elektronika 2025.
• [4] Zbigniew Pliszka. Wiarygodność testów wydajności w zależności od zakresu użytych liczb. Elektronika 2025.
• [5] R Gary Parker and Ronald L Rardin. Discrete optimization. Elsevier, 2014.
• [6] Jes´us A De Loera, Raymond Hemmecke, K Matthias, et al. Algebraic and geometric ideas in the theory of discrete optimization, volume 14. SIAM, 2013.
• [7] Marek Siudak. Badania operacyjne. Oficyna Wydawnicza Politechniki Warszawskiej, 1998.

Uwagi

The research was supported by a statutory grant of the Wroclaw University of Science and Technology, Department of Comupter Science and Systems Engineering and by the Polish National Science Centre under grant no. 2020/37/B/HS4/03235.

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).