NTT・九大共同研究周期スケジューリングと密度限界河村彰星（京大）大阪組合せ論セミナー令和2年10月3日
例
[HMRTV89]  R. Holte, A. Mok, L. Rosier, I. Tulchinsky, D. Varvel.  The pinwheel: a real-time scheduling problem.  In Proc. 22nd Hawaii International Conference on System Science, pp. 693–702, 1989.独獨純的によ13定理[HMRTV89] a = (a₁,a₂,…,a₂)が詰込可能ならば　αは周期a₁α₂ …a₂以内で詰込可能aの詰込スケジュールは次の有向グラフにおける無限の歩に対応する#19; ■頂点集合{1, ...,α₁} × {1, ...,α₂} × ... × {1, ...,α₂}頂点r = (r1,..,rk)は「各仕事iを最近ri日やってない」を表す■辺r → sは「rな日に或る仕事を行うと翌日sになる」とき設ける町ち1 (i = i)辺r → sあり  ⇒ 或るiが存在して各iについてs; = - (r; + 1 (i ≠ i)有限グラフ上の無限の歩なので閉路をもつこれにより詰込可能性は　有限時間で判定可能多項式時間で判定可能かは判っていない（NP困難性なども知られていない） [HMRTV89]  R. Holte, A. Mok, L. Rosier, I. Tulchinsky, D. Varvel.  The pinwheel: a real-time scheduling problem.  In Proc. 22nd Hawaii International Conference on System Science, pp. 693–702, 1989.湖沼畑すんグ河） 13定義[HMRTV89] α = (a1,a2,...,ακ)の密度（density）とはD(a) = − + −もしD(a) > 1ならば明らかにαは詰込不能逆は一般には成立たないが……定理[HMRTV89] aの各項が以降の項を割切りかつD(α) ≤ 1ならば  αは詰込可能(3, 6, 6, 6, 12, 36, 36)は詰込可能行∴貪慾に割当てていけばできる∴各項を2冪に切捨てても密度≤ 1なのでの(5, 7, 8, 30, 100) ≥ (4, 4, 8, 16, 64) は詰込可能D(a) ≤ ≒ならば  aは詰込可能[HMRTV89]  R. Holte, A. Mok, L. Rosier, I. Tulchinsky, D. Varvel.  The pinwheel: a real-time scheduling problem.  In Proc. 22nd Hawaii International Conference on System Science, pp. 693–702, 1989.こートベテン型湘羅羅時代がsio河） ve 13定理[HRTV92] ,e1,e2,...,e2) (二種類の値からなる)でD(a) ≤ 1ならばαは詰込可能例えば(5, 5, 5, 18, 18, 18, 18, 18, 18)は詰込可能自動車道k²—以上 e1-k1以下の直線を描方眼紙に傾き–この直線をぎりぎり超えずに格子点を歩くときの→と↑の並びをe₁とe₂に割当てる・どのe,日間にもk,個以上の■がある・どのe,日間にも k,個以上の■があるとなる三種類だと不成立　例えば(2,3,α₃)はα₃が幾ら大きくても詰込不可能[HRTV92]  R. Holte, L. Rosier, I. Tulchinsky, D. Varvel.  Pinwheel scheduling with two distinct numbers.  Theoretical Computer Science 100, pp. 105–135, 1992. D(a) < Bならばaは詰込可能と言える最大のBは？の（平[HMRTV89] D(a) ≤ ≥ = 0.5ならばaは詰込可能定理[CC93] D( a ) 13 = 0.65ならばaは詰込可能20気遣　[FL02] D(a) < = 0.75ならばaは詰込可能する。[CC93] D(a) < = = 0.833 ...ならばaは詰込可能[HMRTV89]  R. Holte, A. Mok, L. Rosier, I. Tulchinsky, D. Varvel.  The pinwheel: a real-time scheduling problem.  In Proc. 22nd Hawaii International Conference on System Science, pp. 693–702, 1989. [CC93]  M.Y. Chan, F. Chin.  Schedulers for larger classes of pinwheel instances.  Algorithmica 9, pp. 425–462, 1993. [FL02]  P.C. Fishburn, J.C. Lagarias.  Pinwheel scheduling: achievable densities.  Algorithmica 34, pp. 14–38, 2002. 19 13各項を2冪へ切捨て佐(7, 7, 13, 30, 100) → (4, 4, 8, 16, 64) は詰込可能|各項を2冪× iに切捨て」を最良のiで行う佐川(7, 7, 13, 30, 100) → (6, 6, 12, 24, 96)なども考慮←更に色々と頑張る
この問題はNPに属する 何故ならｒが与えられたら条件を満すか否かを次により判定できる（中華剰余定理） r i mod a iとr j mod a jが重なる⇒ r i ≡ r j （mod gcd(a i , a j ） [WL83]  W.D. Wei, C.L. Liu,.  On a periodic maintenance problem.  Operations Research Letters 2, pp. 90–93, 1983. [Sun92]  Z. Sun.  On disjoint residue classes.  Discrete Mathematics 104, pp. 321–326, 1992.視器班時によ(ヨ13気理[KS20]剰余類詰込問題はNP完全(入力中の各整数α;が文字列0ªで与えられたとしても)日本人の三角形のないグラフの点被覆（vertex cover）からの帰着グラフ(V, {1, ..., k})と数s ∈ Nこのグラフに大きさ≤ sの点被覆あり次のように作る(a 1 , …, a k )詰込可能各u ∈ Vに相異なる大きな素数p uを割当て各辺i = uvに対し　αi = s · pu · pvとする中華剰余定理により  α̣による剰余ṛıはs,pw,pvそれぞれによる剰余ri1,ri2,ri3で指定されると書く（図では添字を省略）そこでr į = [ r i1, r i2, r i3]s,p u,p v [KS20]  A. Kawamura, M. Soejima.  Simple strategies versus optimal schedules in multi-agent patrolling.  Theoretical Computer Science 839, pp. 195–206, 2020. 13 「逆」の問題（詰込を被覆に）前耳までの皆を知らず独立に考えてしまいました崎者荻窪問題（Point Patrolling） [KS20]正整数の組α = (α₁,α₂,…,α₁)が与えられる各人iはα;日に一度以下しか仕事を担当できないこれを満しながら毎日だれかが仕事をやり続けられるか？ (4, 4, 6, 6)被覆可能(2,3,4) ● 被覆可能被覆可能(2,3,5,9,...,2k + 1)被覆不可能(3,4,5,6,6) ■被覆不可能D(a) ≥ 2被覆可能 ·先程と同様（各要素を2冪に切り上げ）各要素≤ 16で被覆不可能なものの密度の最大値がD(2,3,5,9) = 103であることまでは計算機で確認できた90 [KS20]  A. Kawamura, M. Soejima.  Simple strategies versus optimal schedules in multi-agent patrolling.  Theoretical Computer Science 839, pp. 195–206, 2020.池沼畑時にソ.. 18定理［K未発表］（［KS20］の考え方に基づく） 113 = 1.4125ならばaは被覆可能D(a) > 80
これを(D,M) ll 113,8)で用いると前頁の計算機実験とから定理を得る行機（KS201 D(a) > D(2, 3, 5, 9, 17, ... ) = 1.263 ...ならばαは被覆可能[KS20]  A. Kawamura, M. Soejima.  Simple strategies versus optimal schedules in multi-agent patrolling.  Theoretical Computer Science 839, pp. 195–206, 2020.池沼畑すんグ9 13先程と同じく「a;日ちょうど」では？利点現役役員員
正整数の組a = (a1,...,ak)が与えられる剰余の組r = (r1,…,rk)をうまく選んで集合r; mod a;  (i = 1,...,k)で整数全体を覆えるか気
2 L 4
2 1 2この問題はNPに属するか不明(rが与えられても判定は容易でない)実はrが与えられて被覆性を判定する問題が既にcoNP完全（次頁） [Hou15]  B. Hough.  Solution of the minimum modulus problem for covering systems. Annals of Mathematics 181, pp. 361–382, 2015. [Erd50]  P. Erdõs.  On integers of the form 2 k + p and some related problems. Summa Brasiliensis Mathematicae 2, pp. 113–123, 1950.湖沼畑時にハまとめ止整数の組(a 1 , ..., a k )が与えられたとき集合A1, …, AkニZであって1, ...,kと長さα,の任意の区間Iについてを満すものはあるか判定せよIA; n I | _ (2)
D(a) ≤ 1が必要D(a) ≥ 1が必要密度D(a) = 1に制限すると  これら四問題は一致(整数全体を重なりなく分割する問題[Zná69] )行機[KS20]この問題すらNP完全[Zná69]  Š. Znám.  On exactly covering systems of arithmetic sequences.  Mathematische Annalen 180, pp. 227–232, 1969. [KS20]  A. Kawamura, M. Soejima.  Simple strategies versus optimal schedules in multi-agent patrolling.  Theoretical Computer Science 839, pp. 195–206, 2020.池沼畑じんり
仕事がある場所の間の移動時間（距離）が設定されている竹切り問題（Bamboo Garden Trimming [GKLLMR17] ）詰込問題警邏問題（Periodic Latency / Patrolling [CSW11・CGKK11] ）被覆問題先程までの問題は「どの二点間も距離1 lという特別な場合距離が入って複雑になる代りに間隔α,が一定の場合や　近似アルゴリズムなど➡別スライ様々な切り口から研究がなされている[GKLLMR17]  L. Gasieniec, R. Klasing, C. Levcopoulos, A. Lingas, J. Min, T. Radzik.  Bamboo garden trimming problem (perpetual maintenance of machines with different attendance urgency factors).  In Proc. 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), LNCS 10139, pp. 229–240, 2017. [CSW11]  S. Coene, F.C.R. Spieksma, G.J. Woeginger.  Charlemagne's challenge: the periodic latency problem. Operations Research 59, pp. 674–683, 2011. [CGKK11]   J. Czyzowicz, L. Gasieniec, A. Kosowski, E. Kranakis.  Boundary patrolling by mobile agents with distinct maximal speeds.  In Proc. 19th Annual European Symposium on Algorithms (ESA), LNCS 6942, pp. 701–712, 2011.羽冠冠すんグル