http://hdl.handle.net/11320/12386 2026-06-01T20:22:18Z 2026-06-01T20:22:18Z Fujiwara, Hiroshi Adachi, Ryota Yamamoto, Hiroaki http://hdl.handle.net/11320/12391 2022-01-04T07:00:05Z 2021-01-01T00:00:00Z

Tytuł: Algorithm NextFit for the Bin Packing Problem Autorzy: Fujiwara, Hiroshi; Adachi, Ryota; Yamamoto, Hiroaki Abstrakt: The bin packing problem is a fundamental and important optimization problem in theoretical computer science [4], [6]. An instance is a sequence of items, each being of positive size at most one. The task is to place all the items into bins so that the total size of items in each bin is at most one and the number of bins that contain at least one item is minimum. Approximation algorithms have been intensively studied. Algorithm NextFit would be the simplest one. The algorithm repeatedly does the following: If the first unprocessed item in the sequence can be placed, in terms of size, additionally to the bin into which the algorithm has placed an item the last time, place the item into that bin; otherwise place the item into an empty bin. Johnson [5] proved that the number of the resulting bins by algorithm NextFit is less than twice the number of the fewest bins that are needed to contain all items. In this article, we formalize in Mizar [1], [2] the bin packing problem as follows: An instance is a sequence of positive real numbers that are each at most one. The task is to find a function that maps the indices of the sequence to positive integers such that the sum of the subsequence for each of the inverse images is at most one and the size of the image is minimum. We then formalize algorithm NextFit, its feasibility, its approximation guarantee, and the tightness of the approximation guarantee. Opis: This work was supported by JSPS KAKENHI Grant Numbers JP20K11689, JP20K11676, JP16K00033, JP17K00013, JP20K11808, and JP17K00183.

2021-01-01T00:00:00Z Schwarzweller, Christoph http://hdl.handle.net/11320/12389 2022-01-04T06:48:52Z 2021-01-01T00:00:00Z

Tytuł: Splitting Fields Autorzy: Schwarzweller, Christoph Abstrakt: In this article we further develop field theory in Mizar [1], [2]: we prove existence and uniqueness of splitting fields. We define the splitting field of a polynomial p ∈ F[X] as the smallest field extension of F, in which p splits into linear factors. From this follows, that for a splitting field E of p we have E = F(A) where A is the set of p’s roots. Splitting fields are unique, however, only up to isomorphisms; to be more precise up to F-isomorphims i.e. isomorphisms i with i|F = IdF . We prove that two splitting fields of p ∈ F[X] are F-isomorphic using the well-known technique [4], [3] of extending isomorphisms from F1 −→ F2 to F1(a) −→ F2(b) for a and b being algebraic over F1 and F2, respectively.

2021-01-01T00:00:00Z Nakasho, Kazuhisa Okazaki, Hiroyuki Shidama, Yasunari http://hdl.handle.net/11320/12388 2022-01-04T06:38:43Z 2021-01-01T00:00:00Z

Tytuł: Real Vector Space and Related Notions Autorzy: Nakasho, Kazuhisa; Okazaki, Hiroyuki; Shidama, Yasunari Abstrakt: In this paper, we discuss the properties that hold in finite dimensional vector spaces and related spaces. In the Mizar language [1], [2], variables are strictly typed, and their type conversion requires a complicated process. Our purpose is to formalize that some properties of finite dimensional vector spaces are preserved in type transformations, and to contain the complexity of type transformations into this paper. Specifically, we show that properties such as algebraic structure, subsets, finite sequences and their sums, linear combination, linear independence, and affine independence are preserved in type conversions among TOP-REAL(n), REAL-NS(n), and n-VectSp over F Real. We referred to [4], [9], and [8] in the formalization. Opis: This study was supported in part by JSPS KAKENHI Grant Numbers 17K00182 and 20K19863.

2021-01-01T00:00:00Z