掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.4230/LIPIcs.STACS.2025.59

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/stacs/stacs2025.html#KawaseN25

掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.artint.2025.104406

researchmap

出版者・発行元：Elsevier BV  

DOI： 10.1016/j.geb.2023.12.006

researchmap

掲載種別：研究論文（学術雑誌）  

DOI： 10.1007/s00453-023-01175-3

researchmap

掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.geb.2024.07.008

researchmap

掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1609/aaai.v38i9.28842

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/aaai/aaai2024.html#KawaseMSTY24

掲載種別：研究論文（学術雑誌）   出版者・発行元：The Operations Research Society of Japan  

DOI： 10.15807/jorsj.66.95

researchmap

掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1145/3586182.3616692

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/uist/uist2023a.html#KoyamaNTKHK23

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：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

その他リンク： https://dblp.uni-trier.de/db/conf/wsdm/wsdm2023.html#KawaseMS23

掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.24963/ijcai.2023/307

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/ijcai/ijcai2023.html#0001KSS23

掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.24963/ijcai.2023/311

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/ijcai/ijcai2023.html#KawaseSY23

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Schloss Dagstuhl - Leibniz-Zentrum für Informatik  

DOI： 10.4230/LIPIcs.STACS.2022.32

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/stacs/stacs2022.html#GokoKKMS22

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Springer  

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

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/sagt/sagt2022.html#AmanoIKMO22

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)  

researchmap

その他リンク： https://dl.acm.org/doi/10.5555/3535850.3535911

掲載種別：研究論文（国際会議プロシーディングス）  

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

arXiv

J-GLOBAL

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/sagt/sagt2022.html#KawaseS22

掲載種別：研究論文（学術雑誌）   出版者・発行元：Springer Science and Business Media LLC  

DOI： 10.1007/s00453-021-00797-9

researchmap

その他リンク： https://link.springer.com/article/10.1007/s00453-021-00797-9/fulltext.html

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

その他リンク： http://arxiv.org/pdf/1601.03316v1

掲載種別：研究論文（学術雑誌）  

DOI： 10.1007/s00182-021-00758-0

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.ipl.2020.105991

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1145/3373717

arXiv

researchmap

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：International Foundation for Autonomous Agents and Multiagent Systems  

researchmap

その他リンク： https://www.ifaamas.org/Proceedings/aamas2020/pdfs/p602.pdf

記述言語：英語   掲載種別：研究論文（学術雑誌）  

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

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：ijcai.org  

DOI： 10.24963/ijcai.2020/213

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/ijcai/ijcai2020.html#LiKBK20

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：AAAI Press  

DOI： 10.1609/aaai.v34i02.5580

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/aaai/aaai2020.html#KawaseS20

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1137/18M117442

researchmap

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：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

その他リンク： http://arxiv.org/pdf/1909.10016v1

掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.tcs.2016.06.005

researchmap

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：AAAI Press  

DOI： 10.1609/aaai.v33i01.33017876

researchmap

掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.dam.2018.09.032

researchmap

掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.disopt.2019.05.003

researchmap

掲載種別：研究論文（学術雑誌）  

DOI： 10.1007/s00224-018-9897-7

researchmap

掲載種別：研究論文（学術雑誌）  

DOI： 10.1137/18M1174428

researchmap

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：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

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：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

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1287/moor.2020.1088

arXiv

researchmap

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：AAAI Press  

DOI： 10.1609/aaai.v32i1.11470

researchmap

掲載種別：研究論文（学術雑誌）  

researchmap

その他リンク： https://dblp.uni-trier.de/db/journals/corr/corr1811.html#abs-1811-09045

researchmap

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：ACM  

DOI： 10.1145/3219166.3219200

researchmap

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Springer  

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

arXiv

researchmap

掲載種別：研究論文（学術雑誌）  

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

その他リンク： http://arxiv.org/pdf/1703.03603v1

掲載種別：研究論文（学術雑誌）  

DOI： 10.1007/s00453-017-0397-y

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

DOI： 10.4230/LIPIcs.ISAAC.2017.51

Scopus

arXiv

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

DOI： 10.4230/LIPIcs.ESA.2017.32

Scopus

researchmap

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：ijcai.org  

DOI： 10.24963/ijcai.2017/60

researchmap

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：AAAI Press  

DOI： 10.1609/aaai.v31i1.10576

researchmap

その他リンク： http://dblp.uni-trier.de/db/conf/aaai/aaai2017.html#conf/aaai/MaeharaKSTK17

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：ijcai.org  

DOI： 10.24963/ijcai.2017/35

arXiv

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

DOI： 10.4230/LIPIcs.ISAAC.2016.44

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

DOI： 10.4230/LIPIcs.ISAAC.2016.43

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

DOI： 10.4230/LIPIcs.ISAAC.2016.41

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

DOI： 10.4230/LIPIcs.ISAAC.2016.42

Scopus

arXiv

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Association for Computing Machinery  

DOI： 10.1145/2806416.2806555

Scopus

researchmap

その他リンク： http://dblp.uni-trier.de/db/conf/cikm/cikm2015.html#conf/cikm/MiyauchiK15

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.ipl.2014.10.005

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.tcs.2014.10.017

Web of Science

researchmap

その他リンク： http://orcid.org/0000-0001-5626-779X

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1109/IFIPNetworking.2015.7145331

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

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

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

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

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

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

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1007/s00453-013-9822-z

Web of Science

researchmap

その他リンク： http://orcid.org/0000-0001-5626-779X

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.tcs.2013.09.013

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.tcs.2013.02.031

Web of Science

researchmap

その他リンク： http://orcid.org/0000-0001-5626-779X

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Springer  

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

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

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

Web of Science

researchmap

掲載種別：研究論文（学術雑誌）  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Springer  

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

Scopus

researchmap

その他リンク： http://orcid.org/0000-0001-5626-779X

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Springer  

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

Scopus

researchmap

その他リンク： http://orcid.org/0000-0001-5626-779X

掲載種別：研究論文（学術雑誌）  

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

その他リンク： http://dblp.uni-trier.de/db/journals/corr/corr1703.html#journals/corr/KawaseM17

arXiv

researchmap

その他リンク： http://dblp.uni-trier.de/db/journals/corr/corr1705.html#journals/corr/KawaseY17

J-GLOBAL

researchmap

J-GLOBAL

researchmap

researchmap

その他リンク： http://dblp.uni-trier.de/db/journals/corr/corr1705.html#journals/corr/KawaseI17

arXiv

researchmap

その他リンク： http://dblp.uni-trier.de/db/journals/corr/corr1711.html#journals/corr/abs-1711-07359

arXiv

researchmap

その他リンク： http://dblp.uni-trier.de/db/journals/corr/corr1709.html#journals/corr/abs-1709-07601

researchmap

その他リンク： http://dblp.uni-trier.de/db/journals/corr/corr1710.html#journals/corr/abs-1710-00950

記述言語：日本語   出版者・発行元：一般社団法人電子情報通信学会  

CiNii Books

J-GLOBAL

researchmap

J-GLOBAL

researchmap

arXiv

researchmap

その他リンク： http://dblp.uni-trier.de/db/journals/corr/corr1611.html#journals/corr/MaeharaKSTK16

J-GLOBAL

researchmap

J-GLOBAL

researchmap

J-GLOBAL

researchmap

記述言語：日本語   出版者・発行元：FIT(電子情報通信学会・情報処理学会)運営委員会  

CiNii Books

J-GLOBAL

researchmap

記述言語：日本語   出版者・発行元：公益社団法人日本オペレーションズ・リサーチ学会  

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

CiNii Books

J-GLOBAL

researchmap

記述言語：英語   出版者・発行元：京都大学  

CiNii Books

researchmap

DOI： 10.1371/journal.pone.0147805

arXiv

researchmap

その他リンク： http://dblp.uni-trier.de/db/journals/corr/corr1501.html#journals/corr/MiyauchiK15

記述言語：日本語   出版者・発行元：一般社団法人情報処理学会  

パスや閉路の長さの偶奇に関する問題は，グラフ理論や理論計算機科学の分野において，古典的でよく研究されてきた話題である．この種の基本的な問題として，たとえば，無向グラフにおいて指定された 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

記述言語：日本語   出版者・発行元：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

J-GLOBAL

researchmap

記述言語：日本語   出版者・発行元：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

J-GLOBAL

researchmap

記述言語：日本語   出版者・発行元：一般社団法人電子情報通信学会  

CiNii Books

researchmap

J-GLOBAL

researchmap

記述言語：英語   出版者・発行元：一般社団法人電子情報通信学会  

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

記述言語：英語   出版者・発行元：一般社団法人情報処理学会  

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.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

記述言語：日本語   出版者・発行元：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

J-GLOBAL

researchmap

記述言語：日本語   出版者・発行元：一般社団法人電子情報通信学会  

CiNii Books

J-GLOBAL

researchmap

記述言語：日本語   出版者・発行元：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

J-GLOBAL

researchmap

記述言語：日本語   出版者・発行元：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

researchmap