Zobrazeno 1 - 10
of 66
pro vyhledávání: '"Naonori Kakimura"'
Autor:
Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-Ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
Publikováno v:
ACM Transactions on Algorithms. 19:1-22
We initiate the study of k -edge-connected orientations of undirected graphs through edge flips for k ≥ 2. We prove that in every orientation of an undirected 2k -edge-connected graph, there exists a sequence of edges such that flipping their direc
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::091269ec193a84decaffaf7a8ef858db
https://doi.org/10.1145/3561302
https://doi.org/10.1145/3561302
A parameterized view to the robust recoverable base problem of matroids under structural uncertainty
Publikováno v:
Operations Research Letters. 50(3):370-375
We study a robust recoverable version of the matroid base problem where the uncertainty is imposed on combinatorial structures rather than on weights as studied in the literature. We prove that the problem is NP-hard even when a given matroid is unif
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::68fb1929b28f93b21687e682d4759e9d
http://hdl.handle.net/2433/279147
http://hdl.handle.net/2433/279147
Publikováno v:
SIAM Journal on Discrete Mathematics. 36(2):1102-1123
Motivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings via alternating cycles. Namely, we want to find a shortest sequence of perfect matchings which transforms one given perfect match
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::99964942a49093628cae1e1350f6a01f
http://hdl.handle.net/2433/279146
http://hdl.handle.net/2433/279146
Autor:
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
Publikováno v:
PRIMA 2022: Principles and Practice of Multi-Agent Systems ISBN: 9783031212024
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7592da33a47bb0e8035dc368fe50b476
https://doi.org/10.1007/978-3-031-21203-1_43
https://doi.org/10.1007/978-3-031-21203-1_43
Publikováno v:
Theoretical Computer Science. 842:18-27
The multi-service center problem is a variant of facility location problems. In the problem, we consider locating p facilities on a graph, each of which provides distinct service required by all vertices. Each vertex incurs the cost determined by the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f92c284fc5a3223728fca9ce2b34159a
https://doi.org/10.1016/j.tcs.2020.07.021
https://doi.org/10.1016/j.tcs.2020.07.021
Publikováno v:
Discrete Applied Mathematics. 283:565-576
In this paper, we introduce the concept of b -branchings in digraphs, which is a generalization of branchings serving as a counterpart of b -matchings. Here b is a positive integer vector on the vertex set of a digraph D , and a b -branching is defin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::efa3bbdffc2b80fca76eeed1e0e9e615
https://doi.org/10.1016/j.dam.2020.02.005
https://doi.org/10.1016/j.dam.2020.02.005
Autor:
Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3843510a2471360afe504b7f3ab9ba79
https://doi.org/10.1137/1.9781611977073.56
https://doi.org/10.1137/1.9781611977073.56
Autor:
Hanna Sumita, Shinji Ito, Kei Takemura, Daisuke Hatano, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
We study online task assignment problem with reusable resources, motivated by practical applications such as ridesharing, crowdsourcing and job hiring. In the problem, we are given a set of offline vertices (agents), and, at each time, an online vert
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::48086e392054523930afc86426e01c8b
Autor:
Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
We consider the problem of reforming an envy-free matching when each agent is assigned a single item. Given an envy-free matching, we consider an operation to exchange the item of an agent with an unassigned item preferred by the agent that results i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8110977269531176860668bcb8815656
Publikováno v:
Algorithmica. 82:1006-1032
In this paper, we consider the problem of maximizing a monotone submodular function subject to a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access only to
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f7aa48babb7d8f55c1111935d39650db
https://doi.org/10.1007/s00453-019-00628-y
https://doi.org/10.1007/s00453-019-00628-y