Publishing type：Research paper (international conference proceedings)  

DOI： 10.4230/LIPIcs.STACS.2025.59

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/stacs/stacs2025.html#KawaseN25

Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.artint.2025.104406

researchmap

Publisher：Elsevier BV  

DOI： 10.1016/j.geb.2023.12.006

researchmap

Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s00453-023-01175-3

researchmap

Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.geb.2024.07.008

researchmap

Publishing type：Research paper (international conference proceedings)  

DOI： 10.1609/aaai.v38i9.28842

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/aaai/aaai2024.html#KawaseMSTY24

Publishing type：Research paper (scientific journal)   Publisher：The Operations Research Society of Japan  

DOI： 10.15807/jorsj.66.95

researchmap

Publishing type：Research paper (international conference proceedings)  

DOI： 10.1145/3586182.3616692

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/uist/uist2023a.html#KoyamaNTKHK23

Publishing type：Research paper (international conference proceedings)   Publisher：ACM  

Network analysis has played a key role in knowledge discovery and data
mining. In many real-world applications in recent years, we are interested in
mining multilayer networks, where we have a number of edge sets called layers,
which encode different types of connections and/or time-dependent connections
over the same set of vertices. Among many network analysis techniques, dense
subgraph discovery, aiming to find a dense component in a network, is an
essential primitive with a variety of applications in diverse domains. In this
paper, we introduce a novel optimization model for dense subgraph discovery in
multilayer networks. Our model aims to find a stochastic solution, i.e., a
probability distribution over the family of vertex subsets, rather than a
single vertex subset, whereas it can also be used for obtaining a single vertex
subset. For our model, we design an LP-based polynomial-time exact algorithm.
Moreover, to handle large-scale networks, we also devise a simple, scalable
preprocessing algorithm, which often reduces the size of the input networks
significantly and results in a substantial speed-up. Computational experiments
demonstrate the validity of our model and the effectiveness of our algorithms.

DOI： 10.1145/3539597.3570444

arXiv

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/wsdm/wsdm2023.html#KawaseMS23

Publishing type：Research paper (international conference proceedings)  

DOI： 10.24963/ijcai.2023/307

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/ijcai/ijcai2023.html#0001KSS23

Publishing type：Research paper (international conference proceedings)  

DOI： 10.24963/ijcai.2023/311

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/ijcai/ijcai2023.html#KawaseSY23

Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl - Leibniz-Zentrum für Informatik  

DOI： 10.4230/LIPIcs.STACS.2022.32

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/stacs/stacs2022.html#GokoKKMS22

Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

DOI： 10.1007/978-3-031-15714-1_24

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/sagt/sagt2022.html#AmanoIKMO22

Publishing type：Research paper (international conference proceedings)   Publisher：International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)  

researchmap

Other Link： https://dl.acm.org/doi/10.5555/3535850.3535911

Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

We study an online version of the max-min fair allocation problem for
indivisible items. In this problem, items arrive one by one, and each item must
be allocated irrevocably on arrival to one of $n$ agents, who have additive
valuations for the items. Our goal is to make the least happy agent as happy as
possible. In research on the topic of online allocation, this is a fundamental
and natural problem. Our main result is to reveal the asymptotic competitive
ratios of the problem for both the adversarial and i.i.d. input models. We
design a polynomial-time deterministic algorithm that is asymptotically
$1/n$-competitive for the adversarial model, and we show that this guarantee is
optimal. To this end, we present a randomized algorithm with the same
competitive ratio first and then derandomize it. A natural derandomization
fails to achieve the competitive ratio of $1/n$. We instead build the algorithm
by introducing a novel technique. When the items are drawn from an unknown
identical and independent distribution, we construct a simple polynomial-time
deterministic algorithm that outputs a nearly optimal allocation. We analyze
the strict competitive ratio and show almost tight bounds for the solution. We
further mention some implications of our results on variants of the problem.

DOI： 10.1007/978-3-031-15714-1_30

arXiv

J-GLOBAL

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/sagt/sagt2022.html#KawaseS22

Publishing type：Research paper (scientific journal)   Publisher：Springer Science and Business Media LLC  

DOI： 10.1007/s00453-021-00797-9

researchmap

Other Link： https://link.springer.com/article/10.1007/s00453-021-00797-9/fulltext.html

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier {BV}  

The modularity is a quality function in community detection, which was
introduced by Newman and Girvan (2004). Community detection in graphs is now
often conducted through modularity maximization: given an undirected graph
$G=(V,E)$, we are asked to find a partition $\mathcal{C}$ of $V$ that maximizes
the modularity. Although numerous algorithms have been developed to date, most
of them have no theoretical approximation guarantee. Recently, to overcome this
issue, the design of modularity maximization algorithms with provable
approximation guarantees has attracted significant attention in the computer
science community.
In this study, we further investigate the approximability of modularity
maximization. More specifically, we propose a polynomial-time
$\left(\cos\left(\frac{3-\sqrt{5 } }{4}\pi\right) -
\frac{1+\sqrt{5 } }{8}\right)$-additive approximation algorithm for the
modularity maximization problem. Note here that
$\cos\left(\frac{3-\sqrt{5 } }{4}\pi\right) - \frac{1+\sqrt{5 } }{8} < 0.42084$
holds. This improves the current best additive approximation error of $0.4672$,
which was recently provided by Dinh, Li, and Thai (2015). Interestingly, our
analysis also demonstrates that the proposed algorithm obtains a nearly-optimal
solution for any instance with a very high modularity value. Moreover, we
propose a polynomial-time $0.16598$-additive approximation algorithm for the
maximum modularity cut problem. It should be noted that this is the first
non-trivial approximability result for the problem. Finally, we demonstrate
that our approximation algorithm can be extended to some related problems.

DOI： 10.1016/j.jcss.2020.11.005

arXiv

researchmap

Other Link： http://arxiv.org/pdf/1601.03316v1

Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s00182-021-00758-0

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.ipl.2020.105991

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

We study a decentralized matching market in which firms sequentially make
offers to potential workers. For each offer, the worker can choose "accept" or
"reject," but the decision is irrevocable. The acceptance of an offer
guarantees her job at the firm, but it may also eliminate chances of better
offers from other firms in the future. We formulate this market as a
perfect-information extensive-form game played by the workers. Each instance of
this game has a unique subgame perfect equilibrium (SPE), which does not
necessarily lead to a stable matching and has some perplexing properties.
We show a dichotomy result that characterizes the complexity of computing the
SPE. The computation is tractable if each firm makes offers to at most two
workers or each worker receives offers from at most two firms. In contrast, it
is PSPACE-hard even if both firms and workers are related to at most three
offers. We also study engineering aspects of this matching market. It is shown
that, for any preference profile, we can design an offering schedule of firms
so that the worker-optimal stable matching is realized in the SPE.

DOI： 10.1145/3373717

arXiv

researchmap

Publishing type：Research paper (international conference proceedings)   Publisher：International Foundation for Autonomous Agents and Multiagent Systems  

researchmap

Other Link： https://www.ifaamas.org/Proceedings/aamas2020/pdfs/p602.pdf

Language：English   Publishing type：Research paper (scientific journal)  

The parity of the length of paths and cycles is a classical and well-studied
topic in graph theory and theoretical computer science. The parity constraints
can be extended to label constraints in a group-labeled graph, which is a
directed graph with each arc labeled by an element of a group. Recently, paths
and cycles in group-labeled graphs have been investigated, such as packing
non-zero paths and cycles, where "non-zero" means that the identity element is
a unique forbidden label.
In this paper, we present a solution to finding an $s$--$t$ path with two
labels forbidden in a group-labeled graph. This also leads to an elementary
solution to finding a zero $s$--$t$ path in a ${\mathbb Z}_3$-labeled graph,
which is the first nontrivial case of finding a zero path. This situation in
fact generalizes the 2-disjoint paths problem in undirected graphs, which also
motivates us to consider that setting. More precisely, we provide a
polynomial-time algorithm for testing whether there are at most two possible
labels of $s$--$t$ paths in a group-labeled graph or not, and finding $s$--$t$
paths attaining at least three distinct labels if exist. The algorithm is based
on a necessary and sufficient condition for a group-labeled graph to have
exactly two possible labels of $s$--$t$ paths, which is the main technical
contribution of this paper.

DOI： 10.1016/j.jctb.2019.12.001

arXiv

researchmap

Publishing type：Research paper (international conference proceedings)   Publisher：ijcai.org  

DOI： 10.24963/ijcai.2020/213

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/ijcai/ijcai2020.html#LiKBK20

Publishing type：Research paper (international conference proceedings)   Publisher：AAAI Press  

DOI： 10.1609/aaai.v34i02.5580

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/aaai/aaai2020.html#KawaseS20

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1137/18M117442

researchmap

Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl - Leibniz-Zentrum für Informatik  

In this paper, we introduce online knapsack problems with a resource buffer.
In the problems, we are given a knapsack with capacity $1$, a buffer with
capacity $R\ge 1$, and items that arrive one by one. Each arriving item has to
be taken into the buffer or discarded on its arrival irrevocably. When every
item has arrived, we transfer a subset of items in the current buffer into the
knapsack. Our goal is to maximize the total value of the items in the knapsack.
We consider four variants depending on whether items in the buffer are
removable (i.e., we can remove items in the buffer) or non-removable, and
proportional (i.e., the value of each item is proportional to its size) or
general. For the general&non-removable case, we observe that no constant
competitive algorithm exists for any $R\ge 1$. For the
proportional&non-removable case, we show that a simple greedy algorithm is
optimal for every $R\ge 1$. For the general&removable and the
proportional&removable cases, we present optimal algorithms for small $R$ and
give asymptotically nearly optimal algorithms for general $R$.

DOI： 10.4230/LIPIcs.ISAAC.2019.28

arXiv

researchmap

Other Link： http://arxiv.org/pdf/1909.10016v1

Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.tcs.2016.06.005

researchmap

Publishing type：Research paper (international conference proceedings)   Publisher：AAAI Press  

DOI： 10.1609/aaai.v33i01.33017876

researchmap

Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.dam.2018.09.032

researchmap

Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.disopt.2019.05.003

researchmap

Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s00224-018-9897-7

researchmap

Publishing type：Research paper (scientific journal)  

DOI： 10.1137/18M1174428

researchmap

Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

Computational advertising has been studied to design efficient marketing
strategies that maximize the number of acquired customers. In an increased
competitive market, however, a market leader (a leader) requires the
acquisition of new customers as well as the retention of her loyal customers
because there often exists a competitor (a follower) who tries to attract
customers away from the market leader. In this paper, we formalize a new model
called the Stackelberg budget allocation game with a bipartite influence model
by extending a budget allocation problem over a bipartite graph to a
Stackelberg game. To find a strong Stackelberg equilibrium, a standard solution
concept of the Stackelberg game, we propose two algorithms: an approximation
algorithm with provable guarantees and an efficient heuristic algorithm. In
addition, for a special case where customers are disjoint, we propose an exact
algorithm based on linear programming. Our experiments using real-world
datasets demonstrate that our algorithms outperform a baseline algorithm even
when the follower is a powerful competitor.

DOI： 10.1007/978-3-030-29908-8_45

arXiv

researchmap

Publishing type：Research paper (international conference proceedings)   Publisher：ijcai.org  

Aggregating responses from crowd workers is a fundamental task in the process
of crowdsourcing. In cases where a few experts are overwhelmed by a large
number of non-experts, most answer aggregation algorithms such as the majority
voting fail to identify the correct answers. Therefore, it is crucial to
extract reliable experts from the crowd workers. In this study, we introduce
the notion of "expert core", which is a set of workers that is very unlikely to
contain a non-expert. We design a graph-mining-based efficient algorithm that
exactly computes the expert core. To answer the aggregation task, we propose
two types of algorithms. The first one incorporates the expert core into
existing answer aggregation algorithms such as the majority voting, whereas the
second one utilizes information provided by the expert core extraction
algorithm pertaining to the reliability of workers. We then give a theoretical
justification for the first type of algorithm. Computational experiments using
synthetic and real-world datasets demonstrate that our proposed answer
aggregation algorithms outperform state-of-the-art algorithms.

DOI： 10.24963/ijcai.2019/177

arXiv

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

A set function is called XOS if it can be represented by the maximum of
additive functions. When such a representation is fixed, the number of additive
functions required to define the XOS function is called the width.
In this paper, we study the problem of maximizing XOS functions in the value
oracle model. The problem is trivial for the XOS functions of width $1$ because
they are just additive, but it is already nontrivial even when the width is
restricted to $2$. We show two types of tight bounds on the polynomial-time
approximability for this problem. First, in general, the approximation bound is
between $O(n)$ and $\Omega(n / \log n)$, and exactly $\Theta(n / \log n)$ if
randomization is allowed, where $n$ is the ground set size. Second, when the
width of the input XOS functions is bounded by a constant $k \geq 2$, the
approximation bound is between $k - 1$ and $k - 1 - \epsilon$ for any $\epsilon
> 0$. In particular, we give a linear-time algorithm to find an exact maximizer
of a given XOS function of width $2$, while we show that any exact algorithm
requires an exponential number of value oracle calls even when the width is
restricted to $3$.

DOI： 10.1287/moor.2020.1088

arXiv

researchmap

Publishing type：Research paper (international conference proceedings)   Publisher：AAAI Press  

DOI： 10.1609/aaai.v32i1.11470

researchmap

Publishing type：Research paper (scientific journal)  

researchmap

Other Link： https://dblp.uni-trier.de/db/journals/corr/corr1811.html#abs-1811-09045

researchmap

Publishing type：Research paper (international conference proceedings)   Publisher：ACM  

DOI： 10.1145/3219166.3219200

researchmap

Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

We consider the maximization problem of monotone submodular functions under
an uncertain knapsack constraint. Specifically, the problem is discussed in the
situation that the knapsack capacity is not given explicitly and can be
accessed only through an oracle that answers whether or not the current
solution is feasible when an item is added to the solution. Assuming that
cancellation of the last item is allowed when it overflows the knapsack
capacity, we discuss the robustness ratios of adaptive policies for this
problem, which are the worst case ratios of the objective values achieved by
the output solutions to the optimal objective values. We present a randomized
policy of robustness ratio $(1-1/e)/2$, and a deterministic policy of
robustness ratio $2(1-1/e)/21$. We also consider a universal policy that
chooses items following a precomputed sequence. We present a randomized
universal policy of robustness ratio $(1-1/\sqrt[4]{e})/2$. When the
cancellation is not allowed, no randomized adaptive policy achieves a constant
robustness ratio. Because of this hardness, we assume that a probability
distribution of the knapsack capacity is given, and consider computing a
sequence of items that maximizes the expected objective value. We present a
polynomial-time randomized algorithm of approximation ratio
$(1-1/\sqrt[4]{e})/4-\epsilon$ for any small constant $\epsilon >0$.

DOI： 10.1007/978-3-319-77404-6_48

arXiv

researchmap

Publishing type：Research paper (scientific journal)  

In the densest subgraph problem, given an edge-weighted undirected graph
$G=(V,E,w)$, we are asked to find $S\subseteq V$ that maximizes the density,
i.e., $w(S)/|S|$, where $w(S)$ is the sum of weights of the edges in the
subgraph induced by $S$. This problem has often been employed in a wide variety
of graph mining applications. However, the problem has a drawback; it may
happen that the obtained subset is too large or too small in comparison with
the size desired in the application at hand. In this study, we address the size
issue of the densest subgraph problem by generalizing the density of
$S\subseteq V$. Specifically, we introduce the $f$-density of $S\subseteq V$,
which is defined as $w(S)/f(|S|)$, where $f:\mathbb{Z}_{\geq 0}\rightarrow
\mathbb{R}_{\geq 0}$ is a monotonically non-decreasing function. In the
$f$-densest subgraph problem ($f$-DS), we aim to find $S\subseteq V$ that
maximizes the $f$-density $w(S)/f(|S|)$. Although $f$-DS does not explicitly
specify the size of the output subset of vertices, we can handle the above size
issue using a convex/concave size function $f$ appropriately. For $f$-DS with
convex function $f$, we propose a nearly-linear-time algorithm with a provable
approximation guarantee. On the other hand, for $f$-DS with concave function
$f$, we propose an LP-based exact algorithm, a flow-based $O(|V|^3)$-time exact
algorithm for unweighted graphs, and a nearly-linear-time approximation
algorithm.

DOI： 10.1007/s00453-017-0400-7

arXiv

researchmap

Other Link： http://arxiv.org/pdf/1703.03603v1

Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s00453-017-0397-y

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

DOI： 10.4230/LIPIcs.ISAAC.2017.51

Scopus

arXiv

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

DOI： 10.4230/LIPIcs.ESA.2017.32

Scopus

researchmap

Publishing type：Research paper (international conference proceedings)   Publisher：ijcai.org  

DOI： 10.24963/ijcai.2017/60

researchmap

Publishing type：Research paper (international conference proceedings)   Publisher：AAAI Press  

DOI： 10.1609/aaai.v31i1.10576

researchmap

Other Link： http://dblp.uni-trier.de/db/conf/aaai/aaai2017.html#conf/aaai/MaeharaKSTK17

Publishing type：Research paper (international conference proceedings)   Publisher：ijcai.org  

We consider the matching with contracts framework of Hatfield and Milgrom
when one side (a firm or hospital) can make monetary transfers (offer wages) to
the other (a worker or doctor). In a standard model, monetary transfers are not
restricted. However, we assume that each hospital has a fixed budget; that is,
the total amount of wages allocated by each hospital to the doctors is
constrained. With this constraint, stable matchings may fail to exist and
checking for the existence is hard. To deal with the nonexistence, we focus on
near-feasible matchings that can exceed each hospital budget by a certain
amount, and We introduce a new concept of compatibility. We show that the
compatibility condition is a sufficient condition for the existence of a
near-feasible stable matching in the matching with contracts framework. Under a
slight restriction on hospitals' preferences, we provide mechanisms that
efficiently return a near-feasible stable matching with respect to the actual
amount of wages allocated by each hospital. By sacrificing strategy-proofness,
the best possible bound of budget excess is achieved.

DOI： 10.24963/ijcai.2017/35

arXiv

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

DOI： 10.4230/LIPIcs.ISAAC.2016.44

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

DOI： 10.4230/LIPIcs.ISAAC.2016.43

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

DOI： 10.4230/LIPIcs.ISAAC.2016.41

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

DOI： 10.4230/LIPIcs.ISAAC.2016.42

Scopus

arXiv

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Association for Computing Machinery  

DOI： 10.1145/2806416.2806555

Scopus

researchmap

Other Link： http://dblp.uni-trier.de/db/conf/cikm/cikm2015.html#conf/cikm/MiyauchiK15

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.ipl.2014.10.005

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.tcs.2014.10.017

Web of Science

researchmap

Other Link： http://orcid.org/0000-0001-5626-779X

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1109/IFIPNetworking.2015.7145331

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/978-3-319-26626-8_59

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/978-3-662-47672-7_65

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/978-3-662-48971-0_12

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s00453-013-9822-z

Web of Science

researchmap

Other Link： http://orcid.org/0000-0001-5626-779X

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.tcs.2013.09.013

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.tcs.2013.02.031

Web of Science

researchmap

Other Link： http://orcid.org/0000-0001-5626-779X

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

DOI： 10.1007/978-3-642-38756-2_9

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/978-3-642-45030-3_41

Web of Science

researchmap

Publishing type：Research paper (scientific journal)  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

DOI： 10.1007/978-3-642-28076-4_22

Scopus

researchmap

Other Link： http://orcid.org/0000-0001-5626-779X

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

DOI： 10.1007/978-3-642-32241-9_6

Scopus

researchmap

Other Link： http://orcid.org/0000-0001-5626-779X

Publishing type：Research paper (scientific journal)  

researchmap

J-GLOBAL

researchmap

J-GLOBAL

researchmap

J-GLOBAL

researchmap

J-GLOBAL

researchmap

J-GLOBAL

researchmap

J-GLOBAL

researchmap

In the densest subgraph problem, given an edge-weighted undirected graph<br />
$G=(V,E,w)$, we are asked to find $S\subseteq V$ that maximizes the density,<br />
i.e., $w(S)/|S|$, where $w(S)$ is the sum of weights of the edges in the<br />
subgraph induced by $S$. This problem has often been employed in a wide variety<br />
of graph mining applications. However, the problem has a drawback; it may<br />
happen that the obtained subset is too large or too small in comparison with<br />
the size desired in the application at hand. In this study, we address the size<br />
issue of the densest subgraph problem by generalizing the density of<br />
$S\subseteq V$. Specifically, we introduce the $f$-density of $S\subseteq V$,<br />
which is defined as $w(S)/f(|S|)$, where $f:\mathbb{Z}_{\geq 0}\rightarrow<br />
\mathbb{R}_{\geq 0}$ is a monotonically non-decreasing function. In the<br />
$f$-densest subgraph problem ($f$-DS), we aim to find $S\subseteq V$ that<br />
maximizes the $f$-density $w(S)/f(|S|)$. Although $f$-DS does not explicitly<br />
specify the size of the output subset of vertices, we can handle the above size<br />
issue using a convex/concave size function $f$ appropriately. For $f$-DS with<br />
convex function $f$, we propose a nearly-linear-time algorithm with a provable<br />
approximation guarantee. On the other hand, for $f$-DS with concave function<br />
$f$, we propose an LP-based exact algorithm, a flow-based $O(|V|^3)$-time exact<br />
algorithm for unweighted graphs, and a nearly-linear-time approximation<br />
algorithm.

arXiv

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/corr/corr1703.html#journals/corr/KawaseM17

We explore novel connections between antimatroids and matchings in bipartite
graphs. In particular, we prove that a combinatorial structure induced by
stable matchings or maximum-weight matchings is an antimatroid. Moreover, we
demonstrate that every antimatroid admits such a representation by stable
matchings and maximum-weight matchings.

arXiv

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/corr/corr1705.html#journals/corr/KawaseY17

J-GLOBAL

researchmap

J-GLOBAL

researchmap

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/corr/corr1705.html#journals/corr/KawaseI17

This paper considers two-sided matching with budget constraints where one
side (firm or hospital) can make monetary transfers (offer wages) to the other
(worker or doctor). In a standard model, while multiple doctors can be matched
to a single hospital, a hospital has a maximum quota: the number of doctors
assigned to a hospital cannot exceed a certain limit. In our model, a hospital
instead has a fixed budget: the total amount of wages allocated by each
hospital to doctors is constrained. With budget constraints, stable matchings
may fail to exist and checking for the existence is hard. To deal with the
nonexistence of stable matchings, we extend the "matching with contracts" model
of Hatfield and Milgrom, so that it handles approximately stable matchings
where each of the hospitals' utilities after deviation can increase by factor
up to a certain amount. We then propose two novel mechanisms that efficiently
return such a stable matching that exactly satisfies the budget constraints. In
particular, by sacrificing strategy-proofness, our first mechanism achieves the
best possible bound. Furthermore, we find a special case such that a simple
mechanism is strategy-proof for doctors, keeping the best possible bound of the
general case.

arXiv

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/corr/corr1711.html#journals/corr/abs-1711-07359

In this paper, we study twelve stochastic input models for online problems
and reveal the relationships among the competitive ratios for the models. The
competitive ratio is defined as the worst ratio between the expected optimal
value and the expected profit of the solution obtained by the online algorithm
where the input distribution is restricted according to the model. To handle a
broad class of online problems, we use a framework called request-answer games
that is introduced by Ben-David et al. The stochastic input models consist of
two types: known distribution and unknown distribution. For each type, we
consider six classes of distributions: dependent distributions, deterministic
input, independent distributions, identical independent distribution, random
order of a deterministic input, and random order of independent distributions.
As an application of the models, we consider two basic online problems, which
are variants of the secretary problem and the prophet inequality problem, under
the twelve stochastic input models. We see the difference of the competitive
ratios through these problems.

arXiv

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/corr/corr1709.html#journals/corr/abs-1709-07601

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/corr/corr1710.html#journals/corr/abs-1710-00950

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

CiNii Books

J-GLOBAL

researchmap

J-GLOBAL

researchmap

The optimal pricing problem is a fundamental problem that arises in
combinatorial auctions. Suppose that there is one seller who has indivisible
items and multiple buyers who want to purchase a combination of the items. The
seller wants to sell his items for the highest possible prices, and each buyer
wants to maximize his utility (i.e., valuation minus payment) as long as his
payment does not exceed his budget. The optimal pricing problem seeks a price
of each item and an assignment of items to buyers such that every buyer
achieves the maximum utility under the prices. The goal of the problem is to
maximize the total payment from buyers. In this paper, we consider the case
that the valuations are submodular. We show that the problem is computationally
hard even if there exists only one buyer. Then we propose approximation
algorithms for the unlimited budget case. We also extend the algorithm for the
limited budget case when there exists one buyer and multiple buyers collaborate
with each other.

arXiv

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/corr/corr1611.html#journals/corr/MaeharaKSTK16

J-GLOBAL

researchmap

J-GLOBAL

researchmap

J-GLOBAL

researchmap

Language：Japanese   Publisher：Forum on Information Technology  

CiNii Books

J-GLOBAL

researchmap

Language：Japanese   Publisher：公益社団法人日本オペレーションズ・リサーチ学会  

ゲーム理論の非協力ゲームと呼ばれる分野では,「均衡」に関する研究が盛んに行われている.この均衡は,社会的に最適な状況とは限らない.このような均衡の非効率性を測る定量的な指標として,「無秩序の代償」と「安定性の代償」が提案されている,本稿では,これら2つの非効率性の指標を,ネットワークデザインゲームを通して紹介する.

CiNii Books

J-GLOBAL

researchmap

Language：English   Publisher：Kyoto University  

CiNii Books

researchmap

Identifying community structure in networks is an issue of particular
interest in network science. The modularity introduced by Newman and Girvan
[Phys. Rev. E 69, 026113 (2004)] is the most popular quality function for
community detection in networks. In this study, we identify a problem in the
concept of modularity and suggest a solution to overcome this problem.
Specifically, we obtain a new quality function for community detection. We
refer to the function as Z-modularity because it measures the Z-score of a
given division with respect to the fraction of the number of edges within
communities. Our theoretical analysis shows that Z-modularity mitigates the
resolution limit of the original modularity in certain cases. Computational
experiments using both artificial networks and well-known real-world networks
demonstrate the validity and reliability of the proposed quality function.

DOI： 10.1371/journal.pone.0147805

arXiv

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/corr/corr1501.html#journals/corr/MiyauchiK15

Language：Japanese   Publisher：一般社団法人情報処理学会  

パスや閉路の長さの偶奇に関する問題は，グラフ理論や理論計算機科学の分野において，古典的でよく研究されてきた話題である．この種の基本的な問題として，たとえば，無向グラフにおいて指定された 2 点 s,t 間を結ぶ奇数長 （または偶数長） のパスを見つける問題が挙げられる．この問題は多項式時間で容易に解けるが，一方で，有向グラフにおける同じ問題は NP 困難であることも知られている．本稿では，この種の問題の一般化として，群ラベル付きグラフにおいて指定されたラベルの s-t パスを見つける問題を考える．ここで，群ラベル付きグラフとは，各枝が群の要素によってラベル付けされている有向グラフを指す．無向グラフにおいて奇数長 （または偶数長） のパスを見つける問題は，Z2 ラベル付きグラフにおいてラベルが 1 （または 0） のパスを見つける問題として定式化できる．近年，群ラベル付きグラフにおいて，ある条件を満たすラベル非零のパスや閉路を見つけるいくつかの問題に対し，効率的なアルゴリズムが提案されている．一方で，指定したラベルのパスを見つける問題の難しさは，ラベルに用いられる群に強く依存する．たとえば，群が Z の場合，指定したラベルの s-t パスの存在判定問題は NP 完全であるが，群が Z2 の場合は極めて簡単に解ける．したがって，位数を固定した有限群の場合の計算複雑性は興味深い話題であり，Z3 が最初の非自明な場合である．また，群が Z3 の場合には，指定したラベルの s-t パスを見つける問題は無向グラフにおける 2 点素パス問題の一般化になっており，この問題が多項式時間で解けるという事実も本研究の動機の一端を担っている．本稿では，2 点 s,t を指定した Z3 ラベル付きグラフが，指定したラベルの s-t パスを持つ必要十分条件を与える．また，その特徴付けに基づき，s-t パスの取り得るラベルを計算し，各ラベルを持つ s-t パスを求める多項式時間アルゴリズムを提案する．

CiNii Books

J-GLOBAL

researchmap

Language：Japanese   Publisher：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

J-GLOBAL

researchmap

Language：Japanese   Publisher：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

J-GLOBAL

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

CiNii Books

researchmap

J-GLOBAL

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

In this paper, we study online knapsack problems. The input is a sequence of items e_1, e_2, ..., e_n, each of which has a size and a value. Given the ith item e_i, we either put e_i into the knapsack or reject it. In the removable setting, when e_i is put into the knapsack, some items in the knapsack are removed with no cost if the sum of the size of e_i and the total size in the current knapsack exceeds the capacity of the knapsack. Our goal is to maximize the profit, i.e., the sum of the values of items in the last knapsack. We present a simple randomized 2-competitive algorithm for the unweighted non-removable case and show that it is the best possible, where knapsack problem is called unweighted if the value of each item is equal to its size. For the removable case, we propose a randomized 2-competitive algorithm despite there is no constant competitive deterministic algorithm. We also provide a lower bound 1+1/e&asymp;1.368 for the competitive ratio. For the unweighted removable case, we propose a 10/7-competitive algorithm and provide a lower bound 1.25 for the competitive ratio.

CiNii Books

researchmap

Language：English   Publisher：Information Processing Society of Japan (IPSJ)  

In this paper, we study online knapsack problems. The input is a sequence of items e1, e2,..., en, each of which has a size and a value. Given the ith item ei, we either put ei into the knapsack or reject it. In the removable setting, when ei is put into the knapsack, some items in the knapsack are removed with no cost if the sum of the size of ei and the total size in the current knapsack exceeds the capacity of the knapsack. Our goal is to maximize the profit, i.e., the sum of the values of items in the last knapsack. We present a simple randomized 2-competitive algorithm for the unweighted non-removable case and show that it is the best possible, where knapsack problem is called unweighted if the value of each item is equal to its size. For the removable case, we propose a randomized 2-competitive algorithm despite there is no constant competitive deterministic algorithm. We also provide a lower bound 1+1/e ≒ 1.368 for the competitive ratio. For the unweighted removable case, we propose a 10/7-competitive algorithm and provide a lower bound 1.25 for the competitive ratio.

CiNii Books

researchmap

Language：Japanese   Publisher：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

J-GLOBAL

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

CiNii Books

J-GLOBAL

researchmap

Language：Japanese   Publisher：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

J-GLOBAL

researchmap

Language：Japanese   Publisher：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

researchmap