用户:TNTErick/Draft:k Restriction

来自维基学院
跳到导航 跳到搜索

證明之定理同應用[编辑 | 编辑源代码]

應用一: 項鍊分割問題[编辑 | 编辑源代码]

項鍊分割,或更精確地說,k-段,t-相項鍊分割,指的是

A k-wise t-way splitter is a set of partitions of [m] into b sets, so that for every k coordinates within [m], each having a color in [t], there exists a partition so that every set 1 ≤ j ≤ b contains the same number of coordinates of each color up to rounding. This is a generalization of the existing notion of a splitter introduced by [18]. Splitters are multi-way splitters for t = 1. Splitters and multi-way splitters are used to split a problem of the form “for every k coordinates,...” into b problems of the form “for every dk/be coordinates,...”. The advantage of 2 multi-way splitters is that they give more control on the split. They allow us to split a problem of the form “for every k coordinates, for every partition of the coordinates into t types,...” into b problems of the form “for every dk/be coordinates, for every partition of the coordinates into t types,...”.

定理3[编辑 | 编辑源代码]

A k-wise t-way splitter for splitting m coordinates into b blocks of size where , may be constructed in time poly (m, t^k and the size of construction) .