研究者詳細 - 垣村　尚徳

論文 - 垣村　尚徳

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

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)

　前のページ - 次のページ　

垣村 尚徳

論文 - 垣村 尚徳

垣村　尚徳

論文 - 垣村　尚徳