Centers & Labs

RIKEN Center for Advanced Intelligence Project

Discrete Optimization Unit

Unit Leader: Takanori Maehara (Ph.D.)
Takanori  Maehara(Ph.D.)

We study the theory of discrete optimization. Discrete optimization problems are problems of finding the optimal solution from a finite number of candidates. Since many human decision making can be formulated in this form, solving discrete optimization problems is a fundamental technology in artificial intelligence. Ideally, discrete optimization problems can be solved by examining all candidates. However, when the number of candidates is huge due to the combinatorial explosion, it is impossible to examine all candidates in a realistic time. For such problems, we design an efficient algorithm with theoretical guarantee by using discrete convex analysis, graph theory, etc.

Main Research Field

Computer Science

Related Research Fields

Mathematics

Research Subjects

  • Discrete Optimization
  • Graph Theory
  • Numerical Analysis

Selected Publications

Papers with an asterisk(*) are based on research conducted outside of RIKEN.
  1. Takanori Maehara, Hirofumi Suzuki and Masakazu Ishihata.:
    "Exact Computation of Influence Spread by Binary Decision Diagrams"
    Proceedings of the 26th International World Wide Conference (WWW'17), Perth, Australia, April 3rd—7th, 2017, pp. 947–956.
  2. Takanori Maehara, Naoki Marumo, and Kazuo Murota.:
    "Continuous relaxation for discrete DC programming"
    Mathematical Programming, Series B., April 4th, 2017.
  3. *Daisuke Hatano, Takuro Fukunaga, Takanori Maehara, and Ken-ichi Kawarabayashi.:
    "Scalable algorithm for higher-order co-clustering via random sampling"
    Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI'17), San Francisco. California, United States, February 4th--9th, 2017, pp. 1992--1999.
  4. *Takanori Maehara, Yasushi Kawase, Hanna Sumita, Katsuya Tono, and Ken-ichi Kawarabayashi.:
    "Optimal Pricing for Submodular Valuations with Bounded Curvature"
    Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI'17), San Francisco. California, United States, February 4th--9th, 2017, pp. 622--628.
  5. *Satoshi Hara and Takanori Maehara.:
    "Enumerate Lasso Solutions for Feature Selection"
    Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI'17), San Francisco. California, United States, February 4th--9th, 2017, 1985--1991.
  6. *Takuro Fukunaga and Takanori Maehara.:
    “Computing a tree having a small vertex cover”
    Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA'16), Hong Kong, China, December 16th--18th, 2016, pp. 77--91.
  7. *Danushka Bollegala, Alsuhaibani Mohammed, Takanori Maehara and Ken-ichi Kawarabayashi.:
    "Joint word representation learning using a corpus and a semantic lexicon"
    Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI'16), Phoenix, Arizona, United States, February 12th--17th, 2016, pp. 2690--2696.
  8. *Takanori Maehara, Kohei Hayashi, and Ken-ichi Kawarabayashi.:
    "Expected tensor decomposition with stochastic gradient descent"
    Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI'16), Phoenix, Arizona, United States, February 12th--17th, 2016, pp. 1919--1925.
  9. *Naoto Ohsaka, Takanori Maehara, and Ken-ichi Kawarabayashi.:
    "Efficient PageRank Tracking in Evolving Networks"
    Proceedings of 21st ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'15), Sydney, Australia, August 10th--13th, pp. 875--884.
  10. *Takanori Maehara and Kazuo Murota.:
    "A framework of discrete DC programming by discrete convex analysis"
    Mathematical Programming, Series A, vol. 152, no. 1 (published online in 2 July, 2014), pp. 435–466, 2015.

Contact information

Nihonbashi 1-chome Mitsui Building, 15th floor,
1-4-1 Nihonbashi,
Chuo-ku, Tokyo
103-0027, Japan

Email: takanori.maehara [at] riken.jp

Related links