研究者詳細 - 垣村　尚徳

論文 - 垣村　尚徳

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

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.