Nieliniowe przekształcenia dla podziałów w kostce jednostkowej

• Autorzy: Pliszka Zbigniew

Identyfikatory

DOI

10.15199/13.2025.2.5

Warianty tytułu

EN

Nonlinear transformations for divisions in a unit cube

• Języki publikacji: PL

Abstrakty

PL

Praca jest kontynuacją artykułu [1] w którym przedstawiono nowy sposób klasyfikowania multizbiorów liczbowych po ich posortowaniu i narzuceniu ograniczenia na sumę elementów jego podzbiorów, co w efekcie pozwoliło wprowadzić podział na klasy abstrakcji (nazwane ”cięciem”) w zbiorze indeksów elementów badanego multizbioru przy zachowaniu warunków problemu. W prezentowanej obecnie czytelnikowi pracy pokazano, że przekształcenia nie wyprowadzające poza daną klasę abstrakcji (cięcie) stanowią szerszą klasę niż przekształcenia liniowe. Dla ułatwienia lektury, zacytowano konieczne definicje i twierdzenia bez dowodów.

EN

The work is a continuation of the article [1] in which a new method of classifying numerical multisets was presented after sorting them and imposing a restriction on the sum of elements of its subsets, which in effect allowed for introducing a division into abstraction classes (called “cut”) in the set of indexes of elements of the multiset under study while maintaining the conditions of the problem. In the work presented to the reader now, it was shown that transformations that do not go beyond a given abstraction class (cut) constitute a broader class than linear transformations. To facilitate reading, necessary definitions and theorems without proofs were quoted.

Słowa kluczowe

PL

optymalizacja; drzewo; kostka jednostkowa; multizbiór; problem podziału

EN

optimization; trees; unit cube; multiset; number partitioning

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Elektronika : konstrukcje, technologie, zastosowania
• Rocznik: 2025
• Tom: Vol. 66, Nr 2
• Strony: 27--30
• Opis fizyczny: Bibliogr. 33 poz.

Twórcy

autor

Pliszka Zbigniew

• Wroclaw University of Science and Technology, Department of Computer Science and Systems Engineering, Wyb. Wyspiańskiego 27, 50-370 Wrocław

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

Bibliografia

• [1] Zbigniew Pliszka. On some similarity of finite sets (and what we can say today about certain old problem). Information Sciences, 590:296-321, 2022.
• [2] Aniruddha S Vaidya, PS Nagendra Rao, and S Ravi Shankar. A class of hypercube-like networks. In Proceedings of 1993 5th IEEE Symposium on Parallel and Distributed Processing, pages 800-803. IEEE, 1993.
• [3] Youcef Saad and Martin H Schultz. Topological properties of hypercubes. IEEE Transactions on computers, 37(7):867-872, 1988.
• [4] Säıd Bettayeb. On the k-ary hypercube. Theoretical Computer Science, 140(2):333-339, 1995.
• [5] Khaled Day and Anand Tripathi. A comparative study of topological properties of hypercubes and star graphs. IEEE Transactions on Parallel and Distributed Systems, 5(1):31-38, 1994.
• [6] Frank Nielsen. Topology of interconnection networks. In Introduction to HPC with MPI for Data Science, pages 63-97. Springer, 2016.
• [7] Frank Harary, John P Hayes, and Horng-Jyh Wu. A survey of the theory of hypercube graphs. Computers & Mathematics with Applications, 15(4):277-289, 1988.
• [8] Amin Sahba and John J Prevost. Hypercube based clusters in cloud computing. In 2016 World Automation Congress (WAC), pages 1-6. IEEE, 2016.
• [9] Henry Martyn Mulder. What do trees and hypercubes have in common? In Graph Theory, pages 149-170. Springer, 2016.
• [10] Woei-Kae Chen and Matthias FM Stallmann. On embedding binary trees into hypercubes. Journal of Parallel and Distributed Computing, 24(2):132-138, 1995.
• [11] Alan S Wagner. Embedding all binary trees in the hypercube. Journal of Parallel and Distributed Computing, 18(1):33-43, 1993.
• [12] Alan Wagner. Embedding arbitrary binary trees in a hypercube. Journal of Parallel and Distributed Computing, 7(3):503-520, 1989.
• [13] Sandeep N Bhatt, Fan RK Chung, F Thomson Leighton, and Arnold L Rosenberg. Efficient embeddings of trees in hypercubes. SIAM Journal on Computing, 21(1):151-162, 1992.
• [14] Sandeep N Bhatt and Ilse CF Ipsen. How to embed trees in hypercubes. Technical report, YALE UN IV NEW HAVEN CT DEPT OF COMPUT ER SCIENCE, 1985.
• [15] Volker Heun and Ernst W Mayr. A new efficient algorithm for embedding an arbitrary binary tree into its optimal hypercube. Journal of Algorithms, 20(2):375-399, 1996.
• [16] Jessie Abraham and Micheal Arockiaraj. Wirelength of enhanced hypercubes into r-rooted complete binary trees. Electronic Notes in Discrete Mathematics, 53:373-382, 2016.
• [17] Joanna Ammerlaan and T. Vassilev. Properties of the binary hypercube and middle level graph. Applied Mathematics, 3(1):20-26, 2013.
• [18] Guillermo Aparicio, Jose MG Salmerón, Leocadio G Casado, Rafael Asenjo, and Eligius MT Hendrix. Parallel algorithms for computing the smallest binary tree size in unit simplex refinement. Journal of Parallel and Distributed Computing, 112:166-178, 2018.
• [19] Micheal Arockiaraj, Jasintha Quadras, Indra Rajasingh, and Arul Jeya Shalini. Embedding of hypercubes into sibling trees. Discrete Applied Mathematics, 169:9-14, 2014.
• [20] Ronald L Graham and Pavol Hell. On the history of the minimum spanning tree problem. Annals of the History of Computing, 7(1):43-57, 1985.
• [21] Petr Gregor. Subgraphs of hypercubes-embeddings with restrictions or prescriptions. PhD, 2006.
• [22] Zhao Liu, Jianxi Fan, and Xiaohua Jia. Embedding complete binary trees into parity cubes. The Journal of Supercomputing, 71(1):1-27, 2015.
• [23] Gurmeet Singh Manku. Balanced binary trees for id management and load balance in distributed hash tables. In Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, pages 197-205. ACM, 2004.
• [24] Paul Manuel. Minimum average congestion of enhanced and augmented hypercubes into complete binary trees. Discrete Applied Mathematics, 159(5):360-366, 2011.
• [25] Indra Rajasingh, Paul Manuel, Bharati Rajan, and Micheal Arockiaraj. Wirelength of hypercubes into certain trees. Discrete Applied Mathematics, 160(18):2778-2786, 2012.
• [26] Indhumathi Raman. Certain height-balanced subtrees of hypercubes. International Journal of Computer Mathematics: Computer Systems Theory, 1(1):32-41, 2016.
• [27] Zbigniew Pliszka and Olgierd Unold. On transforming unit cube into tree by one-point mutation. In International Conference on Information Systems Architecture and Technology, pages 71-82. Springer, 2018.
• [28] Kai Hwang and Naresh Jotwani. Advanced computer architecture, 3e, 2011.
• [29] F Thomson Leighton. Introduction to parallel algorithms and architectures: Arrays· trees· hypercubes. Elsevier, 2014.
• [30] Ravipudi Rao. Jaya: A simple and new optimization algorithm for solving constrained and unconstrained optimization problems. International Journal of Industrial Engineering Computations, 7(1):19-34, 2016.
• [31] Dimitri P Bertsekas and Athena Scientific. Convex optimization algorithms. Athena Scientific Belmont, 2015.
• [32] Hamed Hashemi Mehne and Seyedali Mirjalili. A parallel numerical method for solving optimal control problems based on whale optimization algorithm. Knowledge-Based Systems, 151:114-123, 2018.
• [33] S´ebastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends® in Machine Learning, 8(3-4):231-357, 2015.

Uwagi

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).