当研究室で取り組んでいる研究に関する論文・講演などの情報（一部抜粋）です。
Here is a selection of our published papers on the research we’ve been working on in our laboratory.
Our Selected Papers and Keywords
2018
Takeshi Okano, Kengo Katayama, Kazuho Kanahara, Noritaka Nishihara
A local search based on variant variable depth search for the quadratic assignment problem Proceedings Article
In: GEEC-2018: 2018 IEEE 7th Global Conference on Consumer Electronics, pp. 60-63, 2018.
Abstract | BibTeX | タグ: Quadratic assignment problem, Variable depth search | Links:
@inproceedings{OKANO-GEEC-2018,
title = {A local search based on variant variable depth search for the quadratic assignment problem},
author = {Takeshi Okano and Kengo Katayama and Kazuho Kanahara and Noritaka Nishihara},
doi = {10.1109/GCCE.2018.8574497},
year = {2018},
date = {2018-10-09},
urldate = {2018-10-09},
booktitle = {GEEC-2018: 2018 IEEE 7th Global Conference on Consumer Electronics},
pages = {60-63},
abstract = {The quadratic assignment problem (QAP) has practical applications in the electronics domain, such as component placing on circuit boards, minimizing the number of transistors on integrated circuits, optimal placing of letters on touchscreen devices, etc. Since QAP is NP-hard and large problems are not practically solvable to optimality, heuristic methods such as local search are regarded as an efficient algorithm to obtain near optimal solutions within a reasonable time. In this paper, we present a new sophisticated local search algorithm, called variant k-opt local search (vKLS), based on a variant of the variable depth search for QAP. Computational results show that vKLS is capable of finding better solutions on average than the standard VDS and typical 2-opt local search algorithms.},
keywords = {Quadratic assignment problem, Variable depth search},
pubstate = {published},
tppubtype = {inproceedings}
}
The quadratic assignment problem (QAP) has practical applications in the electronics domain, such as component placing on circuit boards, minimizing the number of transistors on integrated circuits, optimal placing of letters on touchscreen devices, etc. Since QAP is NP-hard and large problems are not practically solvable to optimality, heuristic methods such as local search are regarded as an efficient algorithm to obtain near optimal solutions within a reasonable time. In this paper, we present a new sophisticated local search algorithm, called variant k-opt local search (vKLS), based on a variant of the variable depth search for QAP. Computational results show that vKLS is capable of finding better solutions on average than the standard VDS and typical 2-opt local search algorithms.
2007
Kengo Katayama, Hiroshi Yamashita, Hiroyuki Narihisa
Variable depth search and iterated local search for the node placement problem in multihop WDM lightwave networks Proceedings Article
In: CEC 2007: Proceedings of 2007 IEEE Congress on Evolutionary Computation, pp. 3508-3515, 2007.
Abstract | BibTeX | タグ: Iterated local search, Multihop networks, Node placement problem, Variable depth search | Links:
@inproceedings{KATAYAMA-CEC-2007,
title = {Variable depth search and iterated local search for the node placement problem in multihop WDM lightwave networks},
author = {Kengo Katayama and Hiroshi Yamashita and Hiroyuki Narihisa},
doi = {10.1109/CEC.2007.4424927},
year = {2007},
date = {2007-09-25},
urldate = {2007-09-25},
booktitle = {CEC 2007: Proceedings of 2007 IEEE Congress on Evolutionary Computation},
pages = {3508-3515},
abstract = {We address a problem of finding an optimal node placement that minimizes the amount of traffics by reducing the weighted hop distances in multihop lightwave networks. The problem is called Node Placement Problem (NPP). NPP is known to be NP-hard and one of the most important problems in wavelength division multiplexing (WDM) based networks. In this paper we propose a new local search algorithm for the NPP based on variable depth search, and show its extension to an iterated local search algorithm. To evaluate the performance of the proposed methods, we provided the benchmark instances with known optimal solutions, and performed extensive experiments on the instances. The computational results showed that our iterated local search outperformed multistart local search methods and the best available metaheuristic for the problem.},
keywords = {Iterated local search, Multihop networks, Node placement problem, Variable depth search},
pubstate = {published},
tppubtype = {inproceedings}
}
We address a problem of finding an optimal node placement that minimizes the amount of traffics by reducing the weighted hop distances in multihop lightwave networks. The problem is called Node Placement Problem (NPP). NPP is known to be NP-hard and one of the most important problems in wavelength division multiplexing (WDM) based networks. In this paper we propose a new local search algorithm for the NPP based on variable depth search, and show its extension to an iterated local search algorithm. To evaluate the performance of the proposed methods, we provided the benchmark instances with known optimal solutions, and performed extensive experiments on the instances. The computational results showed that our iterated local search outperformed multistart local search methods and the best available metaheuristic for the problem.
2005
Kengo Katayama, Akihiro Hamamoto, Hiroyuki Narihisa
An effective local search for the maximum clique problem Journal Article
In: Information Processing Letters, vol. 95, no. 5, pp. 503-511, 2005, ISSN: 0020-0190.
Abstract | BibTeX | タグ: Combinatorial optimization, Graph algorithms, Maximum clique problem, Neighborhood, Variable depth search | Links:
@article{KATAYAMA-IPL-2005,
title = {An effective local search for the maximum clique problem},
author = {Kengo Katayama and Akihiro Hamamoto and Hiroyuki Narihisa},
url = {https://www.sciencedirect.com/science/article/pii/S0020019005001444},
doi = {https://doi.org/10.1016/j.ipl.2005.05.010},
issn = {0020-0190},
year = {2005},
date = {2005-01-01},
urldate = {2005-01-01},
journal = {Information Processing Letters},
volume = {95},
number = {5},
pages = {503-511},
abstract = {We propose a variable depth search based algorithm, called k-opt local search (KLS), for the maximum clique problem. KLS efficiently explores the k-opt neighborhood defined as the set of neighbors that can be obtained by a sequence of several add and drop moves that are adaptively changed in the feasible search space. Computational results on DIMACS benchmark graphs indicate that KLS is capable of finding considerably satisfactory cliques with reasonable running times in comparison with those of state-of-the-art metaheuristics.},
keywords = {Combinatorial optimization, Graph algorithms, Maximum clique problem, Neighborhood, Variable depth search},
pubstate = {published},
tppubtype = {article}
}
We propose a variable depth search based algorithm, called k-opt local search (KLS), for the maximum clique problem. KLS efficiently explores the k-opt neighborhood defined as the set of neighbors that can be obtained by a sequence of several add and drop moves that are adaptively changed in the feasible search space. Computational results on DIMACS benchmark graphs indicate that KLS is capable of finding considerably satisfactory cliques with reasonable running times in comparison with those of state-of-the-art metaheuristics.