論文 - 垣村　尚徳

A Parameterized View to the Robust Recoverable Base Problem of Matroids Under Structural Uncertainty

T Ito, N Kakimura, N Kamiyama, Y Kobayashi, Y Okamoto

Operations Research Letters （Elsevier BV）  50 （ 3 ） 370 - 375 2022年

査読有り,  ISSN  0167-6377

• Access to Document (DOI)

Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi 0001, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

ACM Transactions on Algorithms (TALG) 2022年

研究論文（学術雑誌）, 査読有り

• Access to Document (DOI)

Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

Chien-Chung Huang, Naonori Kakimura, Simon Mauras, and Yuichi Yoshida

SIAM J. Discrete Math. 36 （ 1 ） 355 - 382 2022年

査読有り

Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization

Chien-Chung Huang, Naonori Kakimura

Theory of Computing Systems 66 （ 1 ） 354 - 394 2022年

査読有り

Shortest Reconfiguration of Perfect Matchings via Alternating Cycles.

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

SIAM J. Discrete Math. 36 （ 2 ）  2021年

研究論文（学術雑誌）, 査読有り

Submodular reassignment problem for reallocating agents to tasks with synergy effects

N Kakimura, N Kamiyama, Y Kobayashi, Y Okamoto

Discrete Optimization, 100631 44 （ 1 ）  2021年

研究論文（学術雑誌）, 査読有り

Improved Streaming Algorithms for Maximizing Monotone Submodular Functions Under a Knapsack Constraint.

Chien-Chung Huang, Naonori Kakimura

Algorithmica 83   879 - 902 2021年

査読有り

Market Pricing for Matroid Rank Valuations

K Bérczi, N Kakimura, Y Kobayashi

SIAM J. Discrete Math. 35 （ 4 ） 2662 - 2678 2021年

査読有り

Spectral Aspects of Symmetric Matrix Signings.

Charles Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang, Naonori Kakimura, Alexandra Kolla

Discrete Optimization 37   100582 - 100582 2020年

研究論文（学術雑誌）, 共著, 査読有り

　概要を見る

© Charles Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang, Naonori Kakimura, and Alexandra Kolla. The spectra of signed matrices have played a fundamental role in social sciences, graph theory, and control theory. In this work, we investigate the computational problems of finding symmetric signings of matrices with natural spectral properties. Our results are the following: 1. We characterize matrices that have an invertible signing: a symmetric matrix has an invertible symmetric signing if and only if the support graph of the matrix contains a perfect 2-matching. Further, we present an efficient algorithm to search for an invertible symmetric signing. 2. We use the above-mentioned characterization to give an algorithm to find a minimum increase in the support of a given symmetric matrix so that it has an invertible symmetric signing. 3. We show NP-completeness of the following problems: verifying whether a given matrix has a symmetric signing that is singular or has bounded eigenvalues. However, we also illustrate that the complexity could differ substantially for input matrices that are adjacency matrices of graphs. We use combinatorial techniques in addition to classic results from matching theory.

Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint.

Chien-Chung Huang, Naonori Kakimura, Yuichi Yoshida

Algorithmica 82 （ 4 ） 1006 - 1032 2020年

査読有り

The B-branching problem in digraphs

Kakimura N., Kamiyama N., Takazawa K.

Discrete Applied Mathematics 283   565 - 576 2020年

査読有り

Complexity of the Multi-Service Center Problem.

Takehiro Ito, Naonori Kakimura, Yusuke Kobayashi

Theoretical Computer Science 842 （ 24 ） 18 - 27 2020年

査読有り

Total dual integrality of the linear complementarity problem

Sumita H., Kakimura N., Makino K.

Annals of Operations Research （Annals of Operations Research）  274 （ 1-2 ） 531 - 553 2019年03月

研究論文（学術雑誌）, 共著, 査読有り

　概要を見る

© 2018, Springer Science+Business Media, LLC, part of Springer Nature. In this paper, we introduce total dual integrality of the linear complementarity problem (LCP) by analogy with the linear programming problem. The main idea of defining the notion is to propose the LCP with orientation, a variant of the LCP whose feasible complementary cones are specified by an additional input vector. Then we naturally define the dual problem of the LCP with orientation and total dual integrality of the LCP. We show that if the LCP is totally dual integral, then all basic solutions are integral. If the input matrix is sufficient or rank-symmetric, and the LCP is totally dual integral, then our result implies that the LCP always has an integral solution whenever it has a solution. We also introduce a class of matrices such that any LCP instance having the matrix as a coefficient matrix is totally dual integral. We investigate relationships between matrix classes in the LCP literature such as principally unimodular matrices. Principally unimodular matrices are known that all basic solutions to the LCP are integral for any integral input vector. In addition, we show that it is coNP-hard to decide whether a given LCP instance is totally dual integral.

• Access to Document (DOI)

Minimum-Cost b-Edge Dominating Sets on Trees

Ito T., Kakimura N., Kamiyama N., Kobayashi Y., Okamoto Y.

Algorithmica （Algorithmica）  81 （ 1 ） 343 - 366 2019年01月

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  0302-9743

　概要を見る

© 2018, Springer Science+Business Media, LLC, part of Springer Nature. In this paper, we consider the minimum-cost b-edge dominating set problem. This is a generalization of the edge dominating set problem, but the computational complexity for trees is an astonishing open problem. We make steps toward the resolution of this open problem in the following three directions. (1) We give the first combinatorial polynomial-time algorithm for paths. Prior to our work, the polynomial-time algorithm for paths used linear programming, and it was known that the linear-programming approach could not be extended to trees. Thus, our algorithm would yield an alternative approach to a possible polynomial-time algorithm for trees. (2) We give a fixed-parameter algorithm for trees with the number of leaves as a parameter. Thus, a possible NP-hardness proof for trees should make use of trees with unbounded number of leaves. (3) We give a fully polynomial-time approximation scheme for trees. Prior to our work, the best known approximation factor was two. If the problem is NP-hard, then a possible proof cannot be done via a gap-preserving reduction from any APX-hard problem unless P= NP.

• Access to Document (DOI)

Reconfiguration of maximum-weight b-matchings in a graph

Ito T., Kakimura N., Kamiyama N., Kobayashi Y., Okamoto Y.

Journal of Combinatorial Optimization 37 （ 2 ） 454 - 464 2019年

研究論文（学術雑誌）, 共著, 査読有り

　概要を見る

© 2018, Springer Science+Business Media, LLC, part of Springer Nature. Consider a graph such that each vertex has a nonnegative integer capacity and each edge has a positive integer weight. Then, a b-matching in the graph is a multi-set of edges (represented by an integer vector on edges) such that the total number of edges incident to each vertex is at most the capacity of the vertex. In this paper, we study a reconfiguration variant for maximum-weight b-matchings: For two given maximum-weight b-matchings in a graph, we are asked to determine whether there exists a sequence of maximum-weight b-matchings in the graph between them, with subsequent b-matchings obtained by removing one edge and adding another. We show that this reconfiguration problem is solvable in polynomial time for instances with no integrality gap. Such instances include bipartite graphs with any capacity function on vertices, and 2-matchings in general graphs. Thus, our result implies that the reconfiguration problem for maximum-weight matchings can be solved in polynomial time for bipartite graphs.

Exact and Approximation Algorithms for Weighted Matroid Intersection.

Chien-Chung Huang, Naonori Kakimura, Naoyuki Kamiyama

Mathematical Programming 177 （ 1-2 ） 85 - 112 2019年

査読有り

The Erdős–Pósa property for edge-disjoint immersions in 4-edge-connected graphs

Kakimura N., Kawarabayashi K.

Journal of Combinatorial Theory. Series B （Journal of Combinatorial Theory. Series B）  131   138 - 169 2018年07月

研究論文（学術雑誌）, 共著, 査読有り

　概要を見る

© 2018 Elsevier Inc. A graph H is immersed in a graph G if the vertices of H are mapped to distinct vertices of G, and the edges of H are mapped to paths joining the corresponding pairs of vertices of G, in such a way that the paths are pairwise edge-disjoint. In this paper, we show that the Erdős–Pósa property holds for packing edge-disjoint Kt-immersions in 4-edge-connected graphs. More precisely, for positive integers k and t, there exists a constant f(k,t) such that a 4-edge-connected graph G has either k edge-disjoint Kt-immersions, or an edge subset F of size at most f(k,t) such that G−F has no Kt-immersion. The 4-edge-connectivity in this statement is best possible in the sense that 3-edge-connected graphs do not have the Erdős–Pósa property.

• Access to Document (DOI)

Maximum lifetime coverage problem with battery recovery effect

Fu N., Kakimura N., Kimura K., Suppakitpaisarn V.

Sustainable Computing: Informatics and Systems （Sustainable Computing: Informatics and Systems）  18   1 - 13 2018年06月

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  2210-5379

　概要を見る

© 2018 Elsevier Inc. Scheduling sensors to prolong the lifetime of target coverage is one of the central problems faced in wireless sensor networks. This problem, called the maximum lifetime coverage problem (MLCP), can be formulated as a linear program with exponential size and has a polynomial-time approximation scheme (PTAS). In reality, however, sensor batteries are subject to the recovery effect, which means that the deliverable energy in a battery can replenish itself if it is left idle for a sufficient duration. Thanks to this effect, we can obtain much longer sensor lifetime if each sensor is intermittently forced to turn off for some interval. In this study, we introduce two models that extend the MLCP to incorporate the battery recovery effect. The first model, called as duty cycle model, represents the battery recovery effect in a deterministic way. The second one, called as linear recovery model, uses a probabilistic model to imitate this effect. We propose two efficient algorithms that work for both models, adapting greedy and Garg–Könemann-based algorithms for the original MLCP. In our numerical experiments, our greedy algorithm performs best in the duty cycle model, while our Garg–Könemann-based algorithm performs best in the linear recovery model. For each network, we compare the longest lifetime obtained from our algorithms with the longest lifetime obtained from algorithms for the original MLCP. As a result, we found that our lifetime is 10–40% longer.

• Access to Document (DOI)

Optimal cache placement for an academic backbone network

Hau T., Kakimura N., Kawarabayashi K., Kobayashi Y., Matsuoka T., Yokoi Y.

Journal of the Operations Research Society of Japan （Journal of the Operations Research Society of Japan）  61 （ 2 ） 197 - 216 2018年

研究論文（学術雑誌）, 共著, 査読有り

　概要を見る

© The Operations Research Society of Japan. Deploying caches on a network is an effective way to reduce the amount of data transmitted in a network. Recently, in an academic backbone network such as SINET (the Science Information Network) in Japan, the amount of transmitted data has significantly increased. It is desired to design an efficient mechanism to allocate caches in an optimal way. In this paper, we begin by formulating a discrete optimization model to find a cache allocation that minimizes the total transmission cost. We then design two efficient algorithms to solve our proposed model. The first one makes use of the fact that a backbone network has small treewidth. The algorithm runs in polynomial time when the number of items is fixed and a graph has a bounded treewidth. The other one reduces the problem to the minimum-cost flow problem under the practical assumption that each item has at most one copy. This yields a polynomial-time combinatorial algorithm. Our numerical experiments on the real SINET network show that our algorithms can solve the cache placement problem efficiently in practice.

• Access to Document (DOI)

Efficient stabilization of cooperative matching games

Ito T., Kakimura N., Kamiyama N., Kobayashi Y., Okamoto Y.

Theoretical Computer Science 677   69 - 82 2017年05月

研究論文（国際会議プロシーディングス）, 共著, 査読有り,  ISSN  0304-3975

　概要を見る

Copyright © 2016, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved. Cooperative matching games have drawn much interest partly because of the connection with bargaining solutions in the networking environment. However, it is not always guaranteed that a network under investigation gives rise to a stable bargaining outcome. To address this issue, we consider a modification process, called stabilization, that yields a network with stable outcomes, where the modification should be as small as possible. Therefore, the problem is cast to a combinatorial-optimization problem in a graph. Recently, the stabilization by edge removal was shown to be NP-hard. On the contrary, in this paper, we show that other possible ways of stabilization, namely, edge addition, vertex removal and vertex addition, are all polynomial-time solvable. Thus, we obtain a complete complexity-theoretic classification of the natural four variants of the network stabilization problem. We further study weighted variants and prove that the variants for edge addition and vertex removal are NP-hard.

• Access to Document (DOI)