日本オペレーションズ・リサーチ学会「離散アルゴリズムの応用と理論」研究部会
Seminar on Discrete Algorithms: Applications and Theory


2016年3月より, 日本オペレーションズ・リサーチ学会「離散アルゴリズムの応用と理論」研究部会(Seminar on Discrete Algorithms: Applications and Theory)が発足しました.
研究部会の紹介はこちらをご覧下さい.
第4回研究会のお知らせ
2016年度第4回(通算第4回)研究会を2017年1月6日(金)に行います. 多くの方のご参加をお待ちしております.
  • 講演者1: Nhan Bao Ho (La Trobe University)
    題目: The Sprague-Grundy function for Star Silver Dollar game

    We examine a generalization of the game Silver Dollar that we call Star Silver Dollar played with multiple strips sharing the same square labeled zero. We prove that computing Sprague-Grundy function can be simpli ed to that of a simpler game with at most two tokens in each strip. We analyze the simplest form, called Star Nim, of this generalization in which each strip has exactly one token. We give an algorithm that, for each Sprague-Grundy value g, computes the positions of two-token Star Nim whose Sprague-Grundy values are g. We prove a periodicity of the sequence of these positions.

  • 講演者2: Endre Boros (Rutgers University)
    題目: Generating maximal irredundant and minimal redundant subfamilies of a hypergraph

    A hypergraph is called irredundant is every hyperedge contains a vertex with degree =1, that is a so called private vertex. A non-irredundant hypergraph is called redundant. The problem of generating all maximal irredundant subfamilies -- MaxIRR (or minimal redundant ones -- MinRED) of a given hypergraph was raised recently by Takeaki Uno (Workshop on Enumeration Algorithms and Structure, Lorentz Center, August, 2015), who also pointed out that MinRED is not easier than monotone dualization. Problem MaxIRR is also strongly related to the problem of generating minimal dominating sets in graphs.

    In this talk we present a number of related results. Among others we show that (1) problems MaxIRR and MinRED are both NP-hard, even if the input is restricted to hypergraphs of maximal degree 3; (2) when restricted for hypergraphs of maximum degree 2, then MinRED is trivial, while MaxIRR is polynomially equivalent with monotone dualization; (3) if the input is restricted to hypergraphs with bounded edge sizes, then MinRED is solvable in polynomially time, while MaxIRR can be solved in polynomial incremental time; (4) finally, under a mild technical condition on the input hypergraphs, MaxIRR becomes solvable in quasi-polynomial incremental time.

  • 講演者3: Vladimir Gurvich (Rutgers University)
    題目: Metric and ultrametric spaces of resistances

    Consider an electrical circuit each edge \(e\) of which is an isotropic conductor with a monomial conductivity function \(y_e^* = y_e^ r/ \mu_e^s\). In this formula, \(y_e\) is the potential difference and \(y_e^∗\) current in \(e\), while \(\mu_e\) is the resistance of \(e\); furthermore, \(r\) and \(s\) are two strictly positive real parameters common for all edges. In particular, the case \(r = s = 1\) corresponds to the standard Ohm law, while \(r = 0.5\) is the standard square law of resistance typical for hydraulics or gas dynamics.

    For every two nodes \(a\) and \(b\) of the circuit, the effective resistance \(\mu(a,b)\) is well-defined and for every three nodes \(a\), \(b\), and \(c\) it holds that \(\mu^{s/r}(a,b) ≤ \mu^{s/r}(a,c) + \mu^{s/r}(c,b)\). It obviously implies the standard triangle inequality \(\mu(a,b) \leq \mu(a,c) + \mu(c,b)\) whenever \(s \geq r\). The equality takes place if and only if each path between \(a\) and \(b\) contains \(c\). One gets several examples of metric and ultrametric spaces playing with parameters \(r\) and \(s\); in particular,

    (i) the effective Ohm resistance for \(r(t) = s(t) \equiv 1\);
    (ii) the length of a shortest path for \(r(t) = s(t) \rightarrow \infty\);
    (iii) the inverse width of a bottleneck path for \(r(t) \equiv 1, s(t) \rightarrow \infty\);
    (iv) the inverse capacity (maximum flow per unit time) for \(r(t) \rightarrow 0, s(t) \equiv 1\);

    between any pair of terminals \(a\) and \(b\), as \(t \rightarrow \infty\). In all four cases the limits \(\mu(a,b) = \lim_{t \rightarrow \infty} \mu(a,b)(t)\) exist for all pairs \(a\), \(b\) and the metric inequality \(\mu(a,b) \leq \mu(a,c) + \mu(c,b)\) holds for all triplets \(a\), \(b\), and \(c\), since \(s(t) \geq r(t)\) for any sufficiently large \(t\). Moreover, a stronger ultrametric inequality \(\mu(a,b) \leq \max(\mu(a,c), \mu(c,b))\) holds for all triplets \(a\), \(b\), and \(c\) in examples (iii) and (iv), since in these two cases \(s(t)/r(t) \rightarrow \infty\), as \(t \rightarrow \infty\).


第3回研究会のお知らせ
2016年度第3回(通算第3回)研究会を10月7日(金)に行います. 多くの方のご参加をお待ちしております.
  • 講演者1: 田島 玲 氏(Yahoo! JAPAN研究所)
    題目(第一部): ヤフーにおけるデータ利活用(1) – サービスへの貢献
    題目(第二部):ヤフーにおけるデータ利活用(2) – 先進事例
  • 講演者2: 柳浦 睦憲 氏(名古屋大学)
    題目: メタ戦略の今
概要はこちら
第2回研究会(RIMS 共同研究「組合せ最適化セミナー」)のお知らせ
2016年度第2回(通算第2回)研究会を7月27日(水)〜29日(金)に行います. 今回はRIMS 共同研究「組合せ最適化セミナー」との共催です. 多くの方のご参加をお待ちしております.
今回は共催のため,参加を希望される方はこちらをご覧の上,事前登録をよろしくお願いいたします.
詳細なプログラムはこちらをご覧ください.
第1回研究会のお知らせ
2016年度第1回(通算第1回)研究会を6月10日(金)に行います. 多くの方のご参加をお待ちしております.
  • 講演者1: 岩岡 浩一郎 氏(パナソニック システムネットワークス)
    題目: 交通信号制御におけるメタヒューリスティックスの活用
  • 講演者2: 武田 朗子 氏(統計数理研究所)
    題目: 非凸二次最適化の二値判別への応用
概要はこちら