論文 - 垣村　尚徳

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

　概要を見る

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)

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年

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