Seminar

• There are many real-world problems that can be formulated as combinatorial optimization problems. They tend to be NP-hard and are hard to solve exactly when the instance sizes are large. As a practical way to solve such problems, heuristic algorithms are often used to find good solutions, though not necessarily optimal, in a reasonable amount of time. Standard basic heuristic strategies include greedy methods and local search algorithms. Such basic strategies are often combined to make more sophisticated methods, called metaheuristics, to find better solutions using more computation time. This talk introduces some of our results on efficient heuristic algorithms based on such strategies.

  2023.02.06 Mon. 10:00-12:00

  35th CoRe Seminar
  Speaker :YAGIURA, Mutsunori (Nagoya U., invited talk) Title :Practical algorithms for combinatorial optimization problems Sumarry :
• An amidakuji (i.e., ladder lotteries, or Ghost Legs) consists of n vertical lines (lines for short) and some horizontal bars (bars for short), where lines have their labels, and each bar connects two lines. By regarding each bar as the exchange of the labels of a pair of lines, an amidakuji (i.e., the network of the lines and bars) represents a permutation. Amidakuji's also correspond to sorting networks, in which bars are regarded as comparators. An amidakuji corresponds to a primitive sorting network if every bar connects two consecutive lines. A rhombus tiling is a tiling of rhombuses of unit edge length without gap or overlap. In this talk, we begin with the relation between Amidakujis and rhombus tilings. Then, we move to the enumeration by the reverse search and ZDDs (Zero-Suppressed Binary Decision Diagrams).

  2023.01.16 Mon. 10:00-12:00

  34th CoRe Seminar
  Speaker :HORIYAMA, Takashi (Hokkaido U., invited talk) Title :Enumeration of amidakujis and rhombus tilings Sumarry :
• I will introduce the theoretical field of distributed computing to you in this talk by explaining recent results on two problems in the field. Specifically, I will talk about
   (i) the leader election problem in the population protocol model, and
   (ii) Byzantine gathering problem by mobile agents.

   

  The population protocol model represents a network consisting of tiny sensors that moves passibly (i.e., they constantly move, but cannot control their own move). This model was proposed by Angluin et al. in 2004 and has been intensively studied since then. In particular, the leader election problem and the majority problem are well studied. In this talk, I will discuss the former, that is, the leader election problem.

   

  Mobile agents are mobile entity that moves autonomously on a computer network. The gathering problem is a well-studied fundamental problem, which requires all agents to gather at a single node. In this talk, we will discuss a variant of this problem, i.e., the gathering problem with the assumption that some agents take arbitrary adversarial actions. 

  2022.12.05 Mon. 10:00-12:00

  33rd CoRe Seminar
  Speaker :SUDO, Yuichi (Hosei U., invited talk) Title :The theoretical field of distributed computing Sumarry :
• I am a researcher in the field of electric power and energy. I am researching mechanisms to maximize the introduction of renewable energy sources on the premise of ensuring safety, stable supply, economic efficiency, and environmental conservation. One of the issues in increasing the introduction of renewable energy sources is the degradation of power quality, which adversely affects social life. In this presentation, the mechanism and countermeasures for power quality degradation caused by renewable energy source will be described, and research to expand the amount of renewable energy sources that can be introduced will be introduced.

  2022.11.28 Mon. 10:00-12:00

  32nd CoRe Seminar
  Speaker :IIOKA, Daisuke (Chubu U., Group B01) Title :Development of electric power system based mainly on renewable energy sources Sumarry :
• Dynamical Systems is a field that studies the collective behavior of objects that update their states according to some rules. Discrete-Time Boolean Finite Dynamical System (DT-BFDS) is a subfield where the systems have some finite number of objects whose states are Boolean values, and the state updates occur in discrete time. In the subfield of DT-BFDS, researchers aim to (i) design models for capturing real-world phenomena and using the models to make predictions and (ii) develop simulation techniques for acquiring insights about the systems' behavior. Useful for both aims is understanding the system dynamics mathematically before executing the systems. Obtaining a mathematical understanding of BFDS is quite challenging, even for simple systems, because the state space of a system grows exponentially in the number of objects. Researchers have used computational complexity to circumvent the challenge. The complexity theoretic research in DT-BFDS has successfully produced complete characterizations for many dynamical problems.

   

  The DT-BFDS studies have mainly dealt with deterministic models, where the update at each time step is deterministic, so the system dynamics are completely determinable from the initial setting. However, natural systems have uncertainty. Models having uncertainty may lead to far-better understandings of nature. Although a few attempts have explored DT-BFDS with uncertainty, including stochastic initialization and tie-breaking, they have scratched only a tiny surface of models with uncertainty. The introduction of uncertainty can be through two schemes. One is the introduction of alternate update functions. The other is the introduction of alternate update schedules. In this talk, I present a set of new DT-BFDS models with uncertainty and present some initial results.
   

  2022.11.14 Mon. 10:00-12:00

  31st CoRe Seminar
  Speaker :OGIHARA, Mitsunori (U. Miami, invited talk) Title :A theory for discrete-time Boolean finite dynamical systems with uncertainty Sumarry :
• In the k-recoloring problem, we are given two (vertex-)colorings of a graph using k colors, and asked to transform one into the other by recoloring only one vertex at a time, while at all times maintaining a proper k-coloring. In this talk, we consider a (directed) recolorability constraint on the k colors, which forbids some pairs of colors to be recolored directly. The recolorability constraint is given in terms of a digraph, whose vertices correspond to the colors and whose arcs represent the pairs of colors that can be recolored directly. We provide algorithms for the problem based on the structure of the digraph, showing that the problem is solvable in linear time when the digraph is a directed cycle or is in a class of multitrees. This talk is based on joint work with Soichiro Fujii, Yuni Iwamasa, and Akira Suzuki.

  2022.10.31 Mon. 10:00-12:00

  30th CoRe Seminar
  Speaker :KIMURA, Kei (Kyushu U., invited talk) Title :Algorithms for coloring reconfiguration under recolorability digraphs Sumarry :
• The online bipartite matching problem is the problem of finding a maximum-size matching when vertices on one side arrive one by one. The problem has practical applications such as online advertisement, ride-sharing, and crowd sourcing. This talk proposes a variant of the problem motivated by such applications, and presents online algorithms with constant competitive ratio. This talk is based on joint work with Hanna Sumita, Shinji Ito, Kei Takemura, Daisuke Hatano, Takuro Fukunaga, Ken-ichi Kawarabayashi.

  2022.10.17 Mon. 10:00-12:00

  29th CoRe Seminar
  Speaker :KAKIMURA, Naonori (Keio U., Group C01) Title :Constrained online bipartite matching Sumarry :
• In this talk, we introduce a Python library for solving combinatorial reconfiguration problems, which is under development in our project. The library is based on graphillion, a subgraph enumeration library. It can solve combinatorial reconfiguration problems for families of sets that can be represented by graphillion. We also introduce the algorithm used in the library.

  2022.07.25 Mon. 15:00-17:00

  28th CoRe Seminar
  Speaker :KAWAHARA, Jun (Kyoto U., Group B01) Title :Reconfillion: a combinatorial reconfiguration solver Sumarry :
• Navigation for a team of agents is a challenging but interesting problem with a variety of applications, including fleet operations in warehouses, video games, and drone shows. In this talk, I provide an overview of techniques for controlling multiple moving agents. The talk includes multi-agent pathfinding (MAPF) which aims at finding a set of collision-free paths on graphs, planning in continuous spaces, and robust execution policies for real robots.

  2022.07.11 Mon. 15:00-17:00

  27th CoRe Seminar
  Speaker :OKUMURA, Keisuke (Tokyo Institute of Technology, invited talk) Title :Navigation for a team of agents Sumarry :
• To evaluate the fittings of statistical models on finite discrete spaces, we consider Monte Carlo simulation methods using Markov chain. To construct a connected Markov chain on a given space, we consider a Markov basis, which is characterized algebraically and is calculated by the theory of Groebner basis of the polynomial rings. In this talk, I give some primers on statistics and algebra to understand this topic, with some related works.

  2022.06.13 Mon. 15:00-17:00

  26th CoRe Seminar
  Speaker :AOKI, Satoshi (Kobe U., invited talk) Title :Computational algebra for Markov chain Monte Carlo sampling Sumarry :