研究者詳細 - 垣村　尚徳

論文 - 垣村　尚徳

分割表示 >> ／全件表示 89 件中 1 - 89 件目

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)

Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs.

Naonori Kakimura, Ken-ichi Kawarabayashi, Yusuke Kobayashi

SIAM J. Discrete Math. （SIAM Journal on Discrete Mathematics） 31 （ 2 ） 766 - 782 2017年

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

© 2017 Society for Industrial and Applied Mathematics. In this paper, we show the Erdos-Pósa property for edge-disjoint packing of S-closed walks with parity constraints in 4-edge-connected graphs. More precisely, we prove that for any 4-edge-connected graph G and any vertex subset S, either G has k edge-disjoint elementary closed odd walks, each of which has at least one vertex of S, or G has an edge set F with |F| ≥ f(k) such that G - F has no such walks. The 4-edge-connectivity is the best possible in the sense that 3-edge-connected graphs do not satisfy the statement. Since the proof is constructive, we can design a fixed-parameter algorithm for finding k edge-disjoint walks satisfying the conditions in a 4-edge-connected graph for a parameter k. In addition, this gives a simple fixed-parameter algorithm for the parity edge-disjoint walks problem with k terminal pairs.

Access to Document (DOI)

Parameterized Complexity of Sparse Linear Complementarity Problems

Sumita H., Kakimura N., Makino K.

Algorithmica （Algorithmica） 79 （ 1 ） 42 - 65 2017年

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

© 2016, Springer Science+Business Media New York. In this paper, we study the parameterized complexity of the linear complementarity problem (LCP), which is one of the most fundamental mathematical optimization problems. The parameters we focus on are the sparsities of the input and the output of the LCP: the maximum numbers of nonzero entries per row/column in the coefficient matrix and the number of nonzero entries in a solution. Our main result is to present a fixed-parameter algorithm for the LCP with the combined parameter. We also show that if we drop any of the three parameters, then the LCP is NP-hard or W[1]-hard. In addition, we show the nonexistence of a polynomial kernel for the LCP unless coNP ⊆ NP/poly.

Access to Document (DOI)

Coloring immersion-free graphs.

Naonori Kakimura, Ken-ichi Kawarabayashi

J. Comb. Theory, Ser. B （Journal of Combinatorial Theory. Series B） 121 284 - 307 2016年11月

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

© 2016 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. The notion of an immersion is quite similar to the well-known notion of a minor, as structural approach inspired by the theory of graph minors has been extremely successful in immersions. Hadwiger's conjecture on graph coloring, generalizing the Four Color Theorem, states that every loopless graph without a Kk-minor is (k−1)-colorable, where Kkis the complete graph on k vertices. This is a long standing open problem in graph theory, and it is even unknown whether it is possible to determine ck-colorability of Kk-minor-free graphs in polynomial time for some constant c. In this paper, we address coloring graphs without H-immersion. In contrast to coloring H-minor-free graphs, we show the following: 1. there exists a fixed-parameter algorithm to decide whether or not a given graph G without an immersion of a graph H of maximum degree d is (d−1)-colorable, where the size of H is a parameter. In fact, if G is (d−1)-colorable, the algorithm produces such a coloring, and2. for any positive integer k (k≥6), it is NP-complete to decide whether or not a given graph G without a Kk-immersion is (k−3)-colorable.

Access to Document (DOI)

The Linear Complementarity Problems with a Few Variables per Constraint.

Hanna Sumita, Naonori Kakimura, Kazuhisa Makino

Math. Oper. Res. （Mathematics of Operations Research） 40 （ 4 ） 1015 - 1026 2015年11月

研究論文（学術雑誌）, 共著, 査読有り, ISSN 0364-765X

© 2015 INFORMS. In this paper, we consider the sparse linear complementarity problem, denoted by k-LCP: the coefficient matrices are restricted to have at most k nonzero entries per row. It is known that the 1-LCP is solvable in linear time, and the 3-LCP is strongly NP-hard. We show that the 2-LCP is strongly NP-hard, and it can be solved in polynomial time if it is sign-balanced, i.e., each row of the matrix has at most one positive and one negative entry. Our second result matches the currently best-known complexity bound for the corresponding sparse linear feasibility problem. In addition, we show that an integer variant of the sign-balanced 2-LCP is weakly NP-hard and pseudo-polynomially solvable, and the generalized 1-LCP is strongly NP-hard.

Access to Document (DOI)

Fixed-parameter tractability for subset feedback set problems with parity constraints.

Naonori Kakimura, Ken-ichi Kawarabayashi

Theor. Comput. Sci. （Theoretical Computer Science） 576 （ 1 ） 61 - 76 2015年04月

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

© 2015 Elsevier B.V. The subset feedback set problem, which is a generalization of the well-known feedback vertex set problem, is that we are given an undirected graph G with a vertex subset S and a positive integer k, and the goal is to find a vertex set X of size at most k such that G-. X has no S-cycle, where an S-cycle is a cycle having at least one vertex of S. It was recently shown that this problem is fixed parameter tractable, where k is the parameter. In this paper, we further generalize this problem to one with the parity constraints, and show the fixed parameter tractability:. 1.For a parameter k, there exists a fixed-parameter algorithm that either finds a vertex set X of size k such that G-X has no S-cycle of even length, or concludes that such a vertex set does not exist.2.For a parameter k, there exists a fixed-parameter algorithm that either finds a vertex set X of size k such that G-X has no S-cycle of odd length, or concludes that such a vertex set does not exist.

Access to Document (DOI)

Matching problems with delta-matroid constraints

Kakimura N., Takamatsu M.

SIAM J. Discrete Math. 28 （ 2 ） 942 - 961 2014年

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

Given an undirected graph G = (V, E) and a directed graph D = (V, A), the master/slave matching problem is to find a matching of maximum cardinality in G such that for each arc (u; v) ∈ A with u being matched, v is also matched. This problem is known to be NP-hard in general, but polynomially solvable in a special case where the maximum size of a connected component of D is at most two. This paper investigates the master/slave matching problem in terms of delta-matroids, which is a generalization of matroids. We first observe that the above polynomially solvable constraint can be interpreted as delta-matroids. We then introduce a new class of matching problem with delta-matroid constraints, which can be solved in polynomial time. In addition, we discuss our problem with additional constraints such as capacity constraints. © 2012, Australian Computer Society, Inc.

Access to Document (DOI)

Half-integral packing of odd cycles through prescribed vertices.

Naonori Kakimura, Ken-ichi Kawarabayashi

Combinatorica （Combinatorica） 33 （ 5 ） 549 - 572 2013年10月

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

The well-known theorem of Erdo{double acute}s-Pósa says that a graph G has either k disjoint cycles or a vertex set X of order at most f(k) for some function f such that G\X is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimization. In this paper, we discuss packing disjoint S-cycles, i.e., cycles that are required to go through a set S of vertices. For this problem, Kakimura-Kawarabayashi-Marx (2011) and Pontecorvi-Wollan (2010) recently showed the Erdo{double acute}s-Pósa-type result holds. We further try to generalize this result to packing S-cycles of odd length. In contrast to packing S-cycles, the Erdo{double acute}s-Pósa-type result does not hold for packing odd S-cycles. We then relax packing odd S-cycles to half-integral packing, and show the Erdo{double acute}s-Pósa-type result for the half-integral packing of odd S-cycles, which is a generalization of Reed (1999) when S=V. That is, we show that given an integer k and a vertex set S, a graph G has either 2k odd S-cycles so that each vertex is in at most two of these cycles, or a vertex set X of order at most f(k) (for some function f) such that G\X has no odd S-cycle. © 2013 János Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.

Access to Document (DOI)

On the number of matrices to generate a matrix * -algebra over the real field

Aiura D., Kakimura N., Murota K.

Linear Algebra and Its Applications （Linear Algebra and Its Applications） 438 （ 3 ） 1252 - 1266 2013年02月

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

Access to Document (DOI)

Robust independence systems

Kakimura N., Makino K.

SIAM J. Discrete Math. 27 （ 3 ） 1257 - 1273 2013年

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

An independence system is one of the most fundamental combinatorial concepts, which includes a variety of objects in graphs and hypergraphs such as matchings, stable sets, and matroids. We discuss the robustness for independence systems, which is a natural generalization of the greedy property of matroids. For a real number α > 0, a set is said to be α-robust if for any k, it includes an α-approximation of the maximum k-independent set, where a set Y in is called k-independent if the size |Y| is at most k. In this paper, we show that every independence system has a -robust independent set, where denotes the exchangeability of . Our result contains a classical result for matroids and the ones of Hassin and Rubinstein,[12] for matchings and Fujita, Kobayashi, and Makino,[7] for matroid 2-intersections, and provides better bounds for the robustness for many independence systems such as b-matchings, hypergraph matchings, matroid p-intersections, and unions of vertex disjoint paths. Furthermore, we provide bounds of the robustness for nonlinear weight functions such as submodular and convex quadratic functions. We also extend our results to independence systems in the integral lattice with separable concave weight functions. © 2011 Springer-Verlag.

Access to Document (DOI)

Packing cycles through prescribed vertices under modularity constraints

Kakimura N., Kawarabayashi K.

Advances in Applied Mathematics （Advances in Applied Mathematics） 49 （ 2 ） 97 - 110 2012年08月

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

The well-known theorem of Erdos-Pósa says that either a graph G has k disjoint cycles or there is a vertex set X of order at most f(k) for some function f such that G/X is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimization. In this paper, we present a common generalization of the following Erdos-Pósa properties: The Erdos-Pósa property for cycles of length divisible by a fixed integer p (Thomassen, 1988 [19]).The Erdos-Pósa property for S-cycles, i.e., cycles which contain a vertex of a prescribed vertex set S (Kakimura, Kawarabayashi, and Marx, 2011 [10] and Pontecorvi and Wollan, 2010 [13]). Namely, given integers k,p, and a vertex set S (whose size may not depend on k and p), we prove that either a graph G has k disjoint S-cycles, each of which has length divisible by p, or G has a vertex set X of order at most f(k,p) such that G/X has no such a cycle. © 2012 Elsevier Inc.

Access to Document (DOI)

Computing knapsack solutions with cardinality robustness

Kakimura N., Makino K., Seimi K.

Japan Journal of Industrial and Applied Mathematics 29 （ 3 ） 469 - 483 2012年

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

In this paper, we study the robustness over the cardinality variation for the knapsack problem. For the knapsack problem and a positive number α ≤ 1, we say that a feasible solution is α-robust if, for any positive integer k, it includes an α-approximation of the maximum k-knapsack solution, where a k-knapsack solution is a feasible solution that consists of at most k items. In this paper, we show that, for any ε > 0, the problem of deciding whether the knapsack problem admits a (ν + ε)-robust solution is weakly NP-hard, where ν denotes the rank quotient of the corresponding knapsack system. Since the knapsack problem always admits a ν-robust knapsack solution [7], this result provides a sharp border for the complexity of the robust knapsack problem. On the positive side, we show that a max-robust knapsack solution can be computed in pseudo-polynomial time, and present a fully polynomial time approximation scheme (FPTAS) for computing a max-robust knapsack solution. © 2011 Springer-Verlag.

Access to Document (DOI)

Packing Directed Circuits through Prescribed Vertices Bounded Fractionally.

Naonori Kakimura, Ken-ichi Kawarabayashi

SIAM J. Discrete Math. （SIAM Journal on Discrete Mathematics） 26 （ 3 ） 1121 - 1133 2012年

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

A seminal result of Reed et al. [Combinatorica, 16 (1996), pp. 535-554] says that a directed graph has either κ vertex-disjoint directed circuits or a set of at most f(κ) vertices meeting all directed circuits. This paper aims at generalizing their result to packing directed circuits through a prescribed set S of vertices. Such a circuit is called an S-circuit. Even et al. [Algorithmica, 20 (1998), pp. 151-174] showed a fractional version of packing S-circuits. In this paper, we show that the fractionality can be bounded by at most one-fifth: Given an integer κ and a vertex subset S, whose size may not depend on κ, we prove that either G has a 1/5-integral packing of k disjoint S-circuits, i.e., each vertex appears in at most five of these S-circuits, or G has a vertex set X of order at most f(k) (for some function f of κ) such that G - X has no such circuit. We also give a fixed-parameter tractable approximation algorithm for finding a 1/5-integral packing of S-circuits. This algorithm finds a 1/5-integral packing of size approximately κ in polynomial time if it has a 1/5-integral packing of size k for a given directed graph and an integer κ. © 2012 Society for Industrial and Applied Mathematics.

Access to Document (DOI)

Packing cycles through prescribed vertices.

Naonori Kakimura, Ken-ichi Kawarabayashi, Dániel Marx

J. Comb. Theory, Ser. B （Journal of Combinatorial Theory. Series B） 101 （ 5 ） 378 - 381 2011年09月

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

The well-known theorem of Erdo{double acute accent}s and Pósa says that a graph G has either k vertex-disjoint cycles or a vertex set X of order at most f(k) such that G\X is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimization. In this paper, we generalize Erdo{double acute accent}s-Pósa's result to cycles that are required to go through a set S of vertices. Given an integer k and a vertex subset S (possibly unbounded number of vertices) in a given graph G, we prove that either G has k vertex-disjoint cycles, each of which contains at least one vertex of S, or G has a vertex set X of order at most f(k)=40k2log2k such that G\X has no cycle that intersects S. © 2011 Elsevier Inc.

Access to Document (DOI)

Matching structure of symmetric bipartite graphs and a generalization of Pólya's problem.

Naonori Kakimura

J. Comb. Theory, Ser. B （Journal of Combinatorial Theory. Series B） 100 （ 6 ） 650 - 670 2010年11月

研究論文（学術雑誌）, 単著, 査読有り, ISSN 0095-8956

A bipartite graph is said to be symmetric if it has symmetry of reflecting two vertex sets. This paper investigates matching structure of symmetric bipartite graphs. We first apply the Dulmage-Mendelsohn decomposition to a symmetric bipartite graph. The resulting components, which are matching-covered, turn out to have symmetry. We then decompose a matching-covered bipartite graph via an ear decomposition, which is a sequence of subgraphs obtained by adding an odd-length path repeatedly. We show that, if a matching-covered bipartite graph is symmetric, an ear decomposition can retain symmetry by adding no more than two paths. As an application of these decompositions to combinatorial matrix theory, we present a natural generalization of Pólya's problem. We introduce the problem of deciding whether a rectangular {0,1}-matrix has a signing that is totally sign-nonsingular or not, where a rectangular matrix is totally sign-nonsingular if the sign of the determinant of each submatrix with the entire row set is uniquely determined by the signs of the nonzero entries. We show that this problem can be solved in polynomial time with the aid of the matching structure of symmetric bipartite graphs. In addition, we provide a characterization of this problem in terms of excluded minors. © 2010 Elsevier Inc.

Access to Document (DOI)

A direct proof for the matrix decomposition of chordal-structured positive semidefinite matrices

Naonori Kakimura

Linear Algebra and Its Applications （Linear Algebra and Its Applications） 433 （ 4 ） 819 - 823 2010年10月

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

Agler, Helton, McCullough, and Rodman proved that a graph is chordal if and only if any positive semidefinite (PSD) symmetric matrix, whose nonzero entries are specified by a given graph, can be decomposed as a sum of PSD matrices corresponding to the maximal cliques. This decomposition is recently exploited to solve positive semidefinite programming efficiently. Their proof is based on a characterization for PSD matrix completion of a chordal-structured matrix due to Grone, Johnson, Sá, and Wolkowicz. This note gives a direct and simpler proof for the result of Agler et al., which leads to an alternative proof of Grone et al. © 2010 Elsevier Inc. All rights reserved.

Access to Document (DOI)

Solving linear programs from sign patterns.

Satoru Iwata, Naonori Kakimura

Mathematical Programming （Mathematical Programming） 114 （ 2 ） 393 - 418 2008年08月

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

This paper is an attempt to provide a connection between qualitative matrix theory and linear programming. A linear program cx | Ax=b, x ≥ 0 is said to be sign-solvable if the set of sign patterns of the optimal solutions is uniquely determined by the sign patterns of A, b, and c. It turns out to be NP-hard to decide whether a given linear program is sign-solvable or not. We then introduce a class of sign-solvable linear programs in terms of totally sign-nonsingular matrices, which can be recognized in polynomial time. For a linear program in this class, we devise an efficient combinatorial algorithm to obtain the sign pattern of an optimal solution from the sign patterns of A, b, and c. The algorithm runs in O(mγ) time, where m is the number of rows of A and γ is the number of all nonzero entries in A, b, and c. © 2007 Springer-Verlag.

Access to Document (DOI)

Sign-solvable linear complementarity problems

Naonori Kakimura

Linear Algebra and Its Applications 429 （ 2-3 ） 606 - 616 2008年07月

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

This paper presents a connection between qualitative matrix theory and linear complementarity problems (LCPs). An LCP is said to be sign-solvable if the set of the sign patterns of the solutions is uniquely determined by the sign patterns of the given coefficients. We provide a characterization for sign-solvable LCPs such that the coefficient matrix has nonzero diagonals, which can be tested in polynomial time. This characterization leads to an efficient combinatorial algorithm to find the sign pattern of a solution for these LCPs. The algorithm runs in O(γ) time, where γ is the number of the nonzero coefficients. © Springer-Verlag Berlin Heidelberg 2007.

Access to Document (DOI)

Computing the inertia from sign patterns

Naonori Kakimura, Satoru Iwata

Mathematical Programming （Springer） 110 （ 1 ） 229 - 244 2007年06月

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

A symmetric matrix A is said to be sign-nonsingular if every symmetric matrix with the same sign pattern as A is nonsingular. Hall, Li and Wang showed that the inertia of a sign-nonsingular symmetric matrix is determined uniquely by its sign pattern. The purpose of this paper is to present an efficient algorithm for computing the inertia of such matrices. The algorithm runs in O(nm) time for a symmetric matrix of order n with m nonzero entries. The correctness of the algorithm provides an alternative proof of the result by Hall et al. In addition, for a symmetric matrix in general, it is shown to be NP-complete to decide whether the inertia of the matrix is not determined by the sign pattern. © Springer-Verlag Berlin Heidelberg 2005.

Access to Document (DOI)

On Reachable Assignments Under Dichotomous Preferences

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

PRIMA 2022: Principles and Practice of Multi-Agent Systems （Springer International Publishing） 650 - 658 2023年

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

We consider the problem of determining whether a target item assignment can
be reached from an initial item assignment by a sequence of pairwise exchanges
of items between agents. In particular, we consider the situation where each
agent has a dichotomous preference over the items, that is, each agent
evaluates each item as acceptable or unacceptable. Furthermore, we assume that
communication between agents is limited, and the relationship is represented by
an undirected graph. Then, a pair of agents can exchange their items only if
they are connected by an edge and the involved items are acceptable. We prove
that this problem is PSPACE-complete even when the communication graph is
complete (that is, every pair of agents can exchange their items), and this
problem can be solved in polynomial time if an input graph is a tree.

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

Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms(SODA) 1342 - 1355 2022年

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

Reforming an Envy-Free Matching

T Ito, Y Iwamasa, N Kakimura, N Kamiyama, Y Kobayashi, Y Nozaki, ...

Proceedings of the AAAI Conference on Artificial Intelligence 36 (5), 5084-5091 （Association for the Advancement of Artificial Intelligence (AAAI)） 36 （ 5 ） 5084 - 5091 2022年

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

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 in another envy-free matching. We repeat this operation as long as
we can. We prove that the resulting envy-free matching is uniquely determined
up to the choice of an initial envy-free matching, and can be found in
polynomial time. We call the resulting matching a reformist envy-free matching,
and then we study a shortest sequence to obtain the reformist envy-free
matching from an initial envy-free matching. We prove that a shortest sequence
is computationally hard to obtain even when each agent accepts at most four
items and each item is accepted by at most three agents. On the other hand, we
give polynomial-time algorithms when each agent accepts at most three items or
each item is accepted by at most two agents. Inapproximability and
fixed-parameter (in)tractability are also discussed.

Access to Document (DOI)

Online Task Assignment Problems with Reusable Resources

H Sumita, S Ito, K Takemura, D Hatano, T Fukunaga, N Kakimura, ...

AAAI 2022 5199 - 5207 2022年

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

A Parameter-Free Algorithm for Misspecified Linear Contextual Bandits

K Takemura, S Ito, D Hatano, H Sumita, T Fukunaga, N Kakimura, ...

International Conference on Artificial Intelligence and Statistics, 3367-3375 2021年

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

Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions

K Takemura, S Ito, D Hatano, H Sumita, T Fukunaga, N Kakimura, ...

AAAI 2021 9791 - 9798 2021年

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

Dynamic Bipartite Matching Market with Arrivals and Departures

N Kakimura, D Zhu

WINE 2021 544 2021年

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

Delay and cooperation in nonstochastic linear bandits

S Ito, D Hatano, H Sumita, K Takemura, T Fukunaga, N Kakimura, ...

Advances in Neural Information Processing Systems 4872 - 4883 2020年

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

Market Pricing for Matroid Rank Valuations

K Bérczi, N Kakimura, Y Kobayashi

ISAAC 2020 39 1 - 15 2020年

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

Shortest reconfiguration of perfect matchings via alternating cycles

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

The 27th Annual European Symposium on Algorithms (ESA) （Leibniz International Proceedings in Informatics, LIPIcs） 61 1 - 15 2019年09月

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

© Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto. 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 matching to another given perfect matching such that the symmetric difference of each pair of consecutive perfect matchings is a single cycle. The problem is equivalent to the combinatorial shortest path problem in perfect matching polytopes. We prove that the problem is NP-hard even when a given graph is planar or bipartite, but it can be solved in polynomial time when the graph is outerplanar.

Access to Document (DOI)

Novel Dense Subgraph Discovery Primitives: Risk Aversion and Exclusion Queries.

Charalampos E. Tsourakakis, Tianyi Chen, Naonori Kakimura, Jakub Pachocki

The European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD2019) （Springer） abs/1904.08178 378 - 394 2019年

研究論文（国際会議プロシーディングス）, 共著

Access to Document (DOI)

Improved Regret Bounds for Bandit Combinatorial Optimization.

Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi

NeurIPS （Advances in Neural Information Processing Systems） 32 12027 - 12036 2019年

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

© 2019 Neural information processing systems foundation. All rights reserved. Bandit combinatorial optimization is a bandit framework in which a player chooses an action within a given finite set A ? {0, 1}d and incurs a loss that is the inner product of the chosen action and an unobservable loss vector in Rd in each round. In this paper, we aim to reveal the property, which makes the bandit combinatorial optimization hard. Recently, Cohen et al. [8] obtained a lower bound ?(pdk3T/log T) of the regret, where k is the maximum `1-norm of action vectors, and T is the number of rounds. This lower bound was achieved by considering a continuous strongly-correlated distribution of losses. Our main contribution is that we managed to improve this bound by ?(vdk3T) through applying a factor of vlog T, which can be done by means of strongly-correlated losses with binary values. The bound derives better regret bounds for three specific examples of the bandit combinatorial optimization: the multitask bandit, the bandit ranking and the multiple-play bandit. In particular, the bound obtained for the bandit ranking in the present study addresses an open problem raised in [8]. In addition, we demonstrate that the problem becomes easier without considering correlations among entries of loss vectors. In fact, if each entry of loss vectors is an independent random variable, then, one can achieve a regret of Õ(vdk2T), which is vk times smaller than the lower bound shown above. The observed results indicated that correlation among losses is the reason for observing a large regret.

Oracle-Efficient Algorithms for Online Linear Optimization with Bandit Feedback.

Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi

NeurIPS （Advances in Neural Information Processing Systems） 32 10589 - 10598 2019年

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

© 2019 Neural information processing systems foundation. All rights reserved. We propose computationally efficient algorithms for online linear optimization with bandit feedback, in which a player chooses an action vector from a given (possibly infinite) set A ? Rd, and then suffers a loss that can be expressed as a linear function in action vectors. Although existing algorithms achieve an optimal regret bound of Õ(vT) for T rounds (ignoring factors of poly(d, log T)), computationally efficient ways of implementing them have not yet been specified, in particular when |A| is not bounded by a polynomial size in d. A standard way to pursue computational efficiency is to assume that we have an efficient algorithm referred to as oracle that solves (offline) linear optimization problems over A. Under this assumption, the computational efficiency of a bandit algorithm can then be measured in terms of oracle complexity, i.e., the number of oracle calls. Our contribution is to propose algorithms that offer optimal regret bounds of Õ(vT) as well as low oracle complexity for both non-stochastic settings and stochastic settings. Our algorithm for non-stochastic settings has an oracle complexity of Õ(T) and is the first algorithm that achieves both a regret bound of Õ(vT) and an oracle complexity of Õ(poly(T)), given only linear optimization oracles. Our algorithm for stochastic settings calls the oracle only O(poly(d, log T)) times, which is smaller than the current best oracle complexity of O(T) if T is sufficiently large.

Non-zero-sum Stackelberg Budget Allocation Game for Computational Advertising.

Daisuke Hatano, Yuko Kuroki, Yasushi Kawase, Hanna Sumita, Naonori Kakimura, Ken-ichi Kawarabayashi

PRICAI (1) 568 - 582 2019年

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

Access to Document (DOI)

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

Chien-Chung Huang, Naonori Kakimura

WADS （Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)） 11646 LNCS （ 4 ） 438 - 451 2019年

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

© Springer Nature Switzerland AG 2019. 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 a small fraction of the data stored in primary memory. For this problem, we propose a (0.4 - ε) -approximation algorithm requiring only a single pass through the data. This improves on the currently best (0.363 - ε) -approximation algorithm. The required memory space depends only on the size of the knapsack capacity and ε.

Access to Document (DOI)

Spectral Aspects of Symmetric Matrix Signings.

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

MFCS 2019 81 1 - 13 2019年

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

The B-branching problem in digraphs

Kakimura N., Kamiyama N., Takazawa K.

Leibniz International Proceedings in Informatics, LIPIcs （Leibniz International Proceedings in Informatics, LIPIcs） 117 12:1-12:15 - 12:15 2018年08月

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

© N. Kakimura, N. Kamiyama, and K. Takazawa. 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, and a b-branching is defined as a common independent set of two matroids defined by b: an arc set is a b-branching if it has at most b(v) arcs sharing the terminal vertex v, and it is an independent set of a certain sparsity matroid defined by b. We demonstrate that b-branchings yield an appropriate generalization of branchings by extending several classical results on branchings. We first present a multi-phase greedy algorithm for finding a maximum-weight b-branching. We then prove a packing theorem extending Edmonds’ disjoint branchings theorem, and provide a strongly polynomial algorithm for finding optimal disjoint b-branchings. As a consequence of the packing theorem, we prove the integer decomposition property of the bbranching polytope. Finally, we deal with a further generalization in which a matroid constraint is imposed on the b(v) arcs sharing the terminal vertex v.

Access to Document (DOI)

Tight approximability of the server allocation problem for real-time applications

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

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) （Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)） 10739 41 - 55 2018年

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

© Springer International Publishing AG 2018. The server allocation problem is a facility location problem for a distributed processing scheme on a real-time network. In this problem, we are given a set of users and a set of servers. Then, we consider the following communication process between users and servers. First a user sends his/her request to the nearest server. After receiving all the requests from users, the servers share the requests. A user will then receive the data processed from the nearest server. The goal of this problem is to choose a subset of servers so that the total delay of the above process is minimized. In this paper, we prove the following approximability and inapproximability results. We first show that the server allocation problem has no polynomial-time approximation algorithm unless P = NP. However, assuming that the delays satisfy the triangle inequality, we design a polynomial-time 3/2-approximation algorithm. When we assume the triangle inequality only among servers, we propose a polynomial-time 2-approximation algorithm. Both of the algorithms are tight in the sense that we cannot obtain better polynomial-time approximation algorithms unless P = NP. Furthermore, we evaluate the practical performance of our algorithms through computational experiments, and show that our algorithms scale better and produce comparable solutions than the previously proposed method based on integer linear programming.

Access to Document (DOI)

Boosting PageRank Scores by Optimizing Internal Link Structure

Ohsaka N., Sonobe T., Kakimura N., Fukunaga T., Fujita S., Kawarabayashi K.

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

© 2018, Springer Nature Switzerland AG. We consider and formulate problems of PageRank score boosting motivated by applications such as effective web advertising. More precisely, given a graph and target vertices, one is required to find a fixed-size set of missing edges that maximizes the minimum PageRank score among the targets. We provide theoretical analyses to show that all of them are NP-hard. To overcome the hardness, we develop heuristic-based algorithms for them. We finally perform experiments on several real-world networks to verify the effectiveness of the proposed algorithms compared to baselines. Specifically, our algorithm achieves 100 times improvements of the minimum PageRank score among selected 100 vertices by adding only dozens of edges.

Access to Document (DOI)

Regret bounds for online portfolio selection with a cardinality constraint

Ito S., Hatano D., Sumita H., Yabe A., Fukunaga T., Kakimura N., Kawarabayashi K.

Advances in Neural Information Processing Systems （Advances in Neural Information Processing Systems） 2018-December 10588 - 10597 2018年

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

© 2018 Curran Associates Inc.All rights reserved. Online portfolio selection is a sequential decision-making problem in which a learner repetitively selects a portfolio over a set of assets, aiming to maximize long-term return. In this paper, we study the problem with the cardinality constraint that the number of assets in a portfolio is restricted to be at most k, and consider two scenarios: (i) in the full-feedback setting, the learner can observe price relatives (rates of return to cost) for all assets, and (ii) in the bandit-feedback setting, the learner can observe price relatives only for invested assets. We propose efficient algorithms for these scenarios, which achieve sublinear regrets. We also provide regret (statistical) lower bounds for both scenarios which nearly match the upper bounds when k is a constant. In addition, we give a computational lower bound, which implies that no algorithm maintains both computational efficiency, as well as a small regret upper bound.

Causal bandits with propagating inference

Yabe A., Hatano D., Sumita H., Ito S., Kakimura N., Fukunaga T., Kawarabayashi K.

35th International Conference on Machine Learning, ICML 2018 （35th International Conference on Machine Learning, ICML 2018） 12 8761 - 8781 2018年

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

© 35th International Conference on Machine Learning, ICML 2018.All Rights Reserved. Bandit is a framework for designing sequential experiments, where a learner selects an arm A ϵ A and obtains an observation corresponding to A in each experiment. Theoretically, the tight regret lower-bound for the general bandit is polynomial with respect to the number of arms |A|, and thus, to overcome this bound, the bandit problem with side-information is often considered. Recently, a bandit framework over a causal graph was introduced, where the structure of the causal graph is available as side-information and the arms are identified with interventions on the causal graph. Existing algorithms for causal bandit overcame the Ω(√\A\/T) simple-regret lower-bound; however, their algorithms work only when the interventions A are localized around a single node (i.e., an intervention propagates only to its neighbors). We then propose a novel causal bandit algorithm for an arbitrary set of interventions, which can propagate throughout the causal graph. We also show that it achieves O(√γ∗ log(|A|T)/T) regret bound, where γ∗ is determined by using a causal graph structure. In particular, if the maximum in-degree of the causal graph is a constant, then γ∗ = O(N2), where N is the number of nodes.

Finding a Dense Subgraph with Sparse Cut.

Atsushi Miyauchi, Naonori Kakimura

CIKM （ACM） 547 - 556 2018年

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

© 2018 Association for Computing Machinery. Community detection is one of the fundamental tasks in graph mining, which has many real-world applications in diverse domains. In this study, we propose an optimization model for finding a community that is densely connected internally but sparsely connected to the rest of the graph. The model extends the densest subgraph problem, in which we maximize the density while minimizing the average cut size. We first show that our proposed model can be solved efficiently. Then we design two polynomial-time exact algorithms based on linear programming and a maximum flow algorithm, respectively. Moreover, to deal with larger-sized graphs in practice, we present a scalable greedy algorithm that runs in almost linear time with theoretical performance guarantee of the output. In addition, as our model is closely related to a quality function called the modularity density, we show that our algorithms can also be used to find global community structure in a graph. With thorough experiments using well-known real-world graphs, we demonstrate that our algorithms are highly effective in finding a suitable community in a graph. For example, for web-Google, our algorithm finds a solution with more than 99.1% density and less than 3.1% cut size, compared with a solution obtained by a baseline algorithm for the densest subgraph problem.

Access to Document (DOI)

Online Regression with Partial Information: Generalization and Linear Projection.

Shinji Ito, Daisuke Hatano, Hanna Sumita, Akihiro Yabe, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi

AISTATS （PMLR） 1599 - 1607 2018年

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

Copyright 2018 by the author(s). We investigate an online regression problem in which the learner makes predictions sequentially while only the limited information on features is observable. In this paper, we propose a general setting for the limitation of the available information, where the observed information is determined by a function chosen from a given set of observation functions. Our problem setting is a generalization of the online sparse linear regression problem, which has been actively studied. For our general problem, we present an algorithm by combining multi-armed bandit algorithms and online learning methods. This algorithm admits a sublinear regret bound when the number of observation functions is constant. We also show that the dependency on the number of observation functions is inevitable unless additional assumptions are adopted. To mitigate this inefficiency, we focus on a special case of practical importance, in which the observed information is expressed through linear combinations of the original features. We propose efficient algorithms for this special case. Finally, we also demonstrate the efficiency of the proposed algorithms by simulation studies using both artificial and real data.

Complexity of the Multi-Service Center Problem.

Takehiro Ito, Naonori Kakimura, Yusuke Kobayashi

ISAAC （Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik） 92 （ 48 ） 1 - 12 2017年12月

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

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 sum of the weighted distances to the p facilities. The aim of the problem is to minimize the maximum cost among all vertices. This problem is known to be NP-hard for general graphs, while it is solvable in polynomial time when p is a fixed constant. In this paper, we give sharp analyses for the complexity of the problem from the viewpoint of graph classes and weights on vertices. We first propose a polynomial-Time algorithm for trees when p is a part of input. In contrast, we prove that the problem becomes strongly NP-hard even for cycles. We also show that when vertices are allowed to have negative weights, the problem becomes NP-hard for paths of only three vertices and strongly NP-hard for stars.

Access to Document (DOI)

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

Chien-Chung Huang, Naonori Kakimura, Yuichi Yoshida

APPROX-RANDOM （Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik） 81 （ 11 ） 1 - 14 2017年08月

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

© Chien-Chung Huang, Naonori Kakimura, and Yuichi Yoshida. 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 a small fraction of the data stored in primary memory. For this problem, we propose a (0.363-ϵ)-approximation algorithm, requiring only a single pass through the data; moreover, we propose a (0.4 - ϵ)-approximation algorithm requiring a constant number of passes through the data. The required memory space of both algorithms depends only on the size of the knapsack capacity and ϵ.

Access to Document (DOI)

Efficient Sublinear-Regret Algorithms for Online Sparse Linear Regression with Limited Observation.

Shinji Ito, Daisuke Hatano, Hanna Sumita, Akihiro Yabe, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi

NIPS （Advances in Neural Information Processing Systems） 2017-December 4102 - 4111 2017年

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

© 2017 Neural information processing systems foundation. All rights reserved. Online sparse linear regression is the task of applying linear regression analysis to examples arriving sequentially subject to a resource constraint that a limited number of features of examples can be observed. Despite its importance in many practical applications, it has been recently shown that there is no polynomialtime sublinear-regret algorithm unless NP ⊆ BPP, and only an exponential-time sublinear-regret algorithm has been found. In this paper, we introduce mild assumptions to solve the problem. Under these assumptions, we present polynomialtime sublinear-regret algorithms for the online sparse linear regression. In addition, thorough experiments with publicly available data demonstrate that our algorithms outperform other known algorithms.

An Improved Approximation Algorithm for the Subpath Planning Problem and Its Generalization.

Hanna Sumita, Yuma Yonebayashi, Naonori Kakimura, Ken-ichi Kawarabayashi

IJCAI （ijcai.org） 0 4412 - 4418 2017年

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

This paper focuses on a generalization of the traveling salesman problem (TSP), called the subpath planning problem (SPP). Given 2n vertices and n independent edges on a metric space, we aim to find a shortest tour that contains all the edges. SPP is one of the fundamental problems in both artificial intelligence and robotics. Our main result is to design a 1.5-approximation algorithm that runs in polynomial time, improving the currently best approximation algorithm. The idea is direct use of techniques developed for TSP. In addition, we propose a generalization of SPP called the subgroup planning problem (SGPP). In this problem, we are given a set of disjoint groups of vertices, and we aim to find a shortest tour such that all the vertices in each group are traversed sequentially. We propose a 3-approximation algorithm for SGPP. We also conduct numerical experiments. Compared with previous algorithms, our algorithms improve the solution quality by more than 10% for large instances with more than 10,000 vertices.

Access to Document (DOI)

Reducing Recovery Error in Compressive Sensing with Limited Number of Base Stations

Pakawanwong P., Suppakitpaisarn V., Xu L., Kakimura N.

2017 IEEE Global Communications Conference, GLOBECOM 2017 - Proceedings （2017 IEEE Global Communications Conference, GLOBECOM 2017 - Proceedings） 2018-January 1 - 7 2017年

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

© 2017 IEEE. We aim to decrease a communication cost of a network that uses compressive sensing, a technique that allows us to recover global information of sparse data by using only a small set of samples. Despite efficiency of the technique, collecting information from all samples is usually costly. Because the samples from previous works usually spread around the network, setting up a number of base stations does not help reducing the cost. In this paper, we propose a method that can utilize the base stations, while aiming to minimize the recovery error of compressive sensing. Based on theorem by Xu et al., which is for cost-aware compressive sensing, we derive a mathematical program that aims to maximize the preciseness in the setting. Then, we approximate the program by a convex quadratic program and prove that the approximation ratio is 0.63. Our simulation results show that, by using the coverage, the sampling error is decreased by at most thirty times.

Access to Document (DOI)

Reconfiguration of maximum-weight b-matchings in a graph

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

COCOON 2017 10392 287 - 296 2017年

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

Efficient stabilization of cooperative matching games

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

AAMAS 41 - 49 2016年

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

Access to Document (DOI)

Exact and Approximation Algorithms for Weighted Matroid Intersection.

Chien-Chung Huang, Naonori Kakimura, Naoyuki Kamiyama

SODA （SIAM） 1 （ 1-2 ） 430 - 444 2016年

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

In this paper, we propose new exact and approximation algorithms for the weighted matroid intersection problem. Our exact algorithm is faster than previous algorithms when the largest weight is relatively small. Our approximation algorithm delivers a (1 - ϵ)-approximate solution with a running time significantly faster than known exact algorithms. The core of our algorithms is a decomposition technique: we decompose an instance of the weighted matroid intersection problem into a set of instances of the unweighted matroid intersection problem. The computational advantage of this approach is that we can make use of fast unweighted matroid intersection algorithms as a black box for designing algorithms. Precisely speaking, we prove that we can solve the weighted matroid intersection problem via solving W instances of the unweighted matroid intersection problem, where W is the largest given weight. Furthermore, we can find a (1 - ϵ)-approximate solution via solving O(ϵ-1log r) instances of the unweighted matroid intersection problem, where r is the smallest rank of the given two matroids. Our algorithms are simple and flexible: they can be adapted to special cases of the weighted matroid intersection problem, using specialized unweighted matroid intersection algorithms. In this paper, we will show the following results. 1. Given two general matroids, using Cunningham's algorithm, we can solve the weighted matroid intersection problem exactly in O(τWnr1.5) time and (1 - ϵ)-approximately in O(τϵ-1nr1.5logr) time, where n is the size of the ground set and r is the time complexity of an independence oracle call. 2. Given two graphic matroids, using the algorithm of Gabow and Xu, we can solve the weighted matroid intersection problem exactly in O(W√rn log r) time and (1 - ϵ)-approximately in O(ϵ-1√rn log2r) time. 3. Given two linear matroids (in the form of two r-by-n matrices), using the algorithm of Cheung, Kwok, and Lau, we can solve the weighted matroid intersection problem exactly in O(nr log r∗ + Wnrω∗-1) time and (1 - ϵ)-approximately in O(nr logr∗ + ϵ-1nrω∗-1logr∗) time, where ω is the exponent of the matrix multiplication time and r∗ is the maximum size of a common independent set. Finally, we give a further application of our decomposition technique. We use our technique to solve efficiently the rankmaximal matroid intersection problem, a problem motivated by matching problems under preferences.

Access to Document (DOI)

Maximizing Time-Decaying Influence in Social Networks.

Naoto Ohsaka, Yutaro Yamaguchi, Naonori Kakimura, Ken-ichi Kawarabayashi

ECML/PKDD (1) （Springer） 9851 LNAI 132 - 147 2016年

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

© Springer International Publishing AG 2016. Influence maximization is a well-studied problem of finding a small set of highly influential individuals in a social network such that the spread of influence under a certain diffusion model is maximized. We propose new diffusion models that incorporate the time-decaying phenomenon by which the power of influence decreases with elapsed time. In standard diffusion models such as the independent cascade and linear threshold models, each edge in a network has a fixed power of influence over time. However, in practical settings, such as rumor spreading, it is natural for the power of influence to depend on the time influenced. We generalize the independent cascade and linear threshold models with time-decaying effects. Moreover, we show that by using an analysis framework based on submodular functions, a natural greedy strategy obtains a solution that is provably within (1 − 1/e) of optimal. In addition, we propose theoretically and practically fast algorithms for the proposed models. Experimental results show that the proposed algorithms are scalable to graphs with millions of edges and outperform baseline algorithms based on a state-of-the-art algorithm.

Access to Document (DOI)

Threshold Influence Model for Allocating Advertising Budgets.

Atsushi Miyauchi, Yuni Iwamasa, Takuro Fukunaga, Naonori Kakimura

ICML （JMLR.org） 2 1395 - 1404 2015年

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

Copyright © 2015 by the author(s). We propose a new influence model for allocating budgets to advertising channels. Our model captures customer's sensitivity to advertisements as a threshold behavior; a customer is expected to be influenced if the influence he receives exceeds his threshold. Over the threshold model, we discuss two optimization problems. The first one is the budget-constrained influence maximization. We propose two greedy algorithms based on different strategies, and analyze the performance when the influence is submodular. We then introduce a new characteristic to measure the cost-effectiveness of a marketing campaign, that is, the proportion of the resulting influence to the cost spent. We design an almost linear-time approximation algorithm to maximize the cost-effectiveness. Furthermore, we design a better-approximation algorithm based on linear programming for a special case. We conduct thorough experiments to confirm that our algorithms outperform baseline algorithms.

Parameterized Complexity of Sparse Linear Complementarity Problems

Sumita H., Kakimura N., Makino K.

IPEC 2015 355 - 364 2015年

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

Maximum lifetime coverage problems with battery recovery effects.

Norie Fu, Vorapong Suppakitpaisarn, Kei Kimura, Naonori Kakimura

GLOBECOM （IEEE） 118 - 124 2014年

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

© 2014 IEEE. Scheduling sensors to prolong the lifetime of covering targets in the field is one of the central problems in wireless sensor networks. This problem, called the maximum lifetime coverage problem (MLCP), can be formulated as a linear programming problem with exponential size, and has a constant-factor approximation algorithm. In reality, however, batteries of sensors have recovery effects, which is a phenomenon that the deliverable energy in batteries can be replenished by itself if it is left idling for sufficient duration. Thanks to that effects, we can obtain much longer lifetime of sensors if each sensor is forced to take a sleep at some interval. In this paper, we introduce two models that extend the MLCP, incorporating battery recovery effects. The first model represents battery recovery effects in a deterministic way, while the second one uses a probabilistic model to imitate the effects. We then propose efficient algorithms that work for both models by extending approximation algorithms for the original MLCP. Numerical experiments show that the lifetime of our schedule is 10-40% longer than one without battery recovery effects.

Access to Document (DOI)

Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm.

Tasuku Soma, Naonori Kakimura, Kazuhiro Inaba, Ken-ichi Kawarabayashi

ICML （JMLR.org） 1 351 - 359 2014年

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

2014 We consider the budget allocation problem over bipartite influence model proposed by Alon et al. (Alon et al., 2012). This problem can be viewed as the well-known influence maximization problem with budget constraints. We first show that this problem and its much more general form fall into a general setting; namely the monotone submodular function maximization over integer lattice subject to a knapsack constraint. Our framework includes Alon et al.'s model, even with a competitor and with cost. We then give a (1 - 1/e)-approximation algorithm for this more general problem. Furthermore, when influence probabilities are nonincreasing, we obtain a faster (1 - 1/e)-approximation algorithm, which runs essentially in linear time in the number of nodes. This allows us to implement our algorithm up to almost 10M edges (indeed, our experiments tell us that we can implement our algorithm up to 1 billion edges. It would approximately take us only 500 seconds.).

Minimum-Cost b-Edge Dominating Sets on Trees

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

ISAAC 2014 8889 195 - 207 2014年

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

Sparse Linear Complementarity Problems.

Hanna Sumita, Naonori Kakimura, Kazuhisa Makino

CIAC 2013 7878 358 - 369 2013年

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

Erdös-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing.

Naonori Kakimura, Ken-ichi Kawarabayashi, Yusuke Kobayashi

SODA （SIAM） 1726 - 1736 2012年

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

Access to Document (DOI)

Matching problems with delta-matroid constraints

Kakimura N., Takamatsu M.

CATS 2012 （CRPIT） 128 83 - 92 2012年

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

Set Covering with Ordered Replacement: Additive and Multiplicative Gaps.

Friedrich Eisenbrand, Naonori Kakimura, Thomas Rothvoß, Laura Sanità

IPCO （Springer） 6655 LNCS 170 - 182 2011年

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

We consider set covering problems where the underlying set system satisfies a particular replacement property w.r.t. a given partial order on the elements: Whenever a set is in the set system then a set stemming from it via the replacement of an element by a smaller element is also in the set system. Many variants of Bin Packing that have appeared in the literature are such set covering problems with ordered replacement. We provide a rigorous account on the additive and multiplicative integrality gap and approximability of set covering with replacement. In particular we provide a polylogarithmic upper bound on the additive integrality gap that also yields a polynomial time additive approximation algorithm if the linear programming relaxation can be efficiently solved. We furthermore present an extensive list of covering problems that fall into our framework and consequently have polylogarithmic additive gaps as well. © 2011 Springer-Verlag.

Access to Document (DOI)

Robust independence systems

Kakimura N., Makino K.

ICALP 2011 6755 367 - 378 2011年

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

Computing knapsack solutions with cardinality robustness

Kakimura N., Makino K., Seimi K.

ISAAC 2011 7074 693 - 702 2011年

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

Sign-solvable linear complementarity problems

Naonori Kakimura

IPCO2007 4513 397 - 409 2007年

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

Computing the inertia from sign patterns

Naonori Kakimura, Satoru Iwata

IPCO 2005 3509 236 - 248 2005年

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

Dynamic Bipartite Matching Market with Arrivals and Departures

N Kakimura, D Zhu

arXiv preprint arXiv:2110.10824 （Springer） abs/2110.10824 544 - 544 2021年

In this paper, we study a matching market model on a bipartite network where
agents on each side arrive and depart stochastically by a Poisson process. For
such a dynamic model, we design a mechanism that decides not only which agents
to match, but also when to match them, to minimize the expected number of
unmatched agents. The main contribution of this paper is to achieve theoretical
bounds on the performance of local mechanisms with different timing properties.
We show that an algorithm that waits to thicken the market, called the
$\textit{Patient}$ algorithm, is exponentially better than the
$\textit{Greedy}$ algorithm, i.e., an algorithm that matches agents greedily.
This means that waiting has substantial benefits on maximizing a matching over
a bipartite network. We remark that the Patient algorithm requires the planner
to identify agents who are about to leave the market, and, under the
requirement, the Patient algorithm is shown to be an optimal algorithm. We also
show that, without the requirement, the Greedy algorithm is almost optimal. In
addition, we consider the $\textit{1-sided algorithms}$ where only an agent on
one side can attempt to match. This models a practical matching market such as
a freight exchange market and a labor market where only agents on one side can
make a decision. For this setting, we prove that the Greedy and Patient
algorithms admit the same performance, that is, waiting to thicken the market
is not valuable. This conclusion is in contrast to the case where agents on
both sides can make a decision and the non-bipartite case by [Akbarpour et
al.,$~\textit{Journal of Political Economy}$, 2020].

Online Spectral Approximation in Random Order Streams.

Masataka Gohda, Naonori Kakimura

arXiv preprint arXiv:1911.08800 abs/1911.08800 2019年

共著

This paper studies spectral approximation for a positive semidefinite matrix
in the online setting. It is known in [Cohen et al. APPROX 2016] that we can
construct a spectral approximation of a given $n \times d$ matrix in the online
setting if an additive error is allowed. In this paper, we propose an online
algorithm that avoids an additive error with the same time and space
complexities as the algorithm of Cohen et al., and provides a better upper
bound on the approximation size when a given matrix has small rank. In
addition, we consider the online random order setting where a row of a given
matrix arrives uniformly at random. In this setting, we propose time and space
efficient algorithms to find a spectral approximation. Moreover, we reveal that
a lower bound on the approximation size in the online random order setting is
$\Omega (d \epsilon^{-2} \log n)$, which is larger than the one in the offline
setting by an $\mathrm{O}\left( \log n \right)$ factor.