研究者詳細 - 小野　廣隆

論文 - 小野　廣隆

分割表示 236 件中 21 - 40 件目／全件表示 >>

The existence of a pure Nash equilibrium in the two-player competitive diffusion game on graphs having chordality

Fukuzono Naoka, Hanaka Tesshu, Kiya Hironori, Ono Hirotaka

DISCRETE APPLIED MATHEMATICS 321 巻頁： 281 - 294 2022年11月

記述言語：日本語出版者・発行元：Discrete Applied Mathematics

The competitive diffusion game is a game-theoretic model of information spreading on a graph proposed by Alon et al. (2010). It models the diffusion process of information in social networks where several competitive companies want to spread their information, for example. The nature of this game strongly depends on the graph topology, and the relationship is studied from several aspects. In this paper, we investigate the existence of a pure Nash equilibrium of the two-player competitive diffusion game on chordal and its related graphs. We show that a pure Nash equilibrium always exists on split graphs, block graphs, and interval graphs, all of which are well-known subclasses of chordal graphs. On the other hand, we show that a pure Nash equilibrium does not always exist on (strongly) chordal graphs; the boundary of the existence of a pure Nash equilibrium is found.

DOI： 10.1016/j.dam.2022.04.025

Polynomial-Time Equivalences and Refined Algorithms for Longest Common Subsequence Variants

Asahiro Y., Jansson J., Lin G., Miyano E., Ono H., Utashima T.

Leibniz International Proceedings in Informatics, LIPIcs 223 巻 2022年6月

記述言語：日本語出版者・発行元：Leibniz International Proceedings in Informatics, LIPIcs

The problem of computing the longest common subsequence of two sequences (LCS for short) is a classical and fundamental problem in computer science. In this paper, we study four variants of LCS: the Repetition-Bounded Longest Common Subsequence problem (RBLCS) [2], the Multiset-Restricted Common Subsequence problem (MRCS) [11], the Two-Side-Filled Longest Common Subsequence problem (2FLCS), and the One-Side-Filled Longest Common Subsequence problem (1FLCS) [5, 6]. Although the original LCS can be solved in polynomial time, all these four variants are known to be NP-hard. Recently, an exact, O(1.44225n)-time, dynamic programming (DP)-based algorithm for RBLCS was proposed [2], where the two input sequences have lengths n and poly(n). We first establish that each of MRCS, 1FLCS, and 2FLCS is polynomially equivalent to RBLCS. Then, we design a refined DP-based algorithm for RBLCS that runs in O(1.41422n) time, which implies that MRCS, 1FLCS, and 2FLCS can also be solved in O(1.41422n) time. Finally, we give a polynomial-time 2-approximation algorithm for 2FLCS.

DOI： 10.4230/LIPIcs.CPM.2022.15

Capacitated Network Design Games on a Generalized Fair Allocation Model

Hanaka T., Hirose T., Ono H.

Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 3 巻頁： 1616 - 1617 2022年

記述言語：日本語出版者・発行元：Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

The cost-sharing connection game is a variant of routing games on a network. In this model, given a directed graph with edge costs and capacities, each agent wants to construct a path from a source to a sink with low cost. The cost of each edge is shared by the users based on a cost-sharing function. One of simple cost-sharing functions is defined as the cost divided by the number of users. It models an ideal setting, where no overhead arises when people share things, though it might be quite rare in real life. In this paper, we model more realistic scenarios of cost-sharing connection games by generalizing the cost-sharing function. The arguments do not depend on specific cost-sharing functions and are applicable for a class of all natural cost-sharing scenarios, which include equal divisions with any natural functional overheads. We show that many bounds of the Price of Anarchy and the Price of Stability under sum-cost and max-cost criteria inherit the no-overhead case.

Fair Ride Allocation on a Line

Amano Y., Igarashi A., Kawase Y., Makino K., Ono H.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 13584 LNCS 巻頁： 421 - 435 2022年

記述言語：日本語出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Airport problem is a classical and well-known model of fair cost-sharing for a single facility among multiple agents. This paper extends it to the so-called assignment setting, that is, for multiple facilities and agents, each agent chooses a facility to use and shares the cost with the other agents. Such a situation can be often seen in sharing economy, such as sharing fees for office desks among workers, and taxi fare among customers of possibly different destinations on a line. Our model is regarded as a coalition formation game, based on the fair cost-sharing of the airport problem; we call our model a fair ride allocation on a line. As the criteria of solution concepts, we incorporate Nash stability and envy-freeness into our setting. We show that a Nash-stable feasible allocation that minimizes the social cost of agents can be computed efficiently if a feasible allocation exists. For envy-freeness, we provide several structural properties of envy-free allocations. Based on these, we design efficient algorithms for finding an envy-free allocation when either (1) the number of facilities, (2) the number of agent types, or (3) the capacity of facilities, is small. Moreover, we show that a consecutive envy-free allocation can be computed in polynomial time. On the negative front, we show the NP-hardness of determining the existence of an allocation under two relaxed envy-free concepts.

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

Computing L(p, 1)-Labeling with Combined Parameters

Hanaka T., Kawai K., Ono H.

Journal of Graph Algorithms and Applications 26 巻 ( 2 ) 頁： 241 - 255 2022年

記述言語：日本語出版者・発行元：Journal of Graph Algorithms and Applications

Given a graph, an L(p, 1)-labeling of the graph is an assignment f from the vertex set to the set of nonnegative integers such that for any pair of vertices u and v, |f(u) − f(v)| ≥ p if u and v are adjacent, and f(u) ≠ f(v) if u and v are at distance 2. The L(p, 1)-labeling problem is to minimize the span of f (i.e.,maxu∈V (f(u)) − minu∈V (f(u)) + 1). It is known to be NP-hard even for graphs of maximum degree 3 or graphs with tree-width 2, whereas it is fixed-parameter tractable with respect to vertex cover number. Since the vertex cover number is a kind of the strongest parameter, there is a large gap between tractability and intractability from the viewpoint of parameterization. To fill up the gap, in this paper, we propose new fixed-parameter algorithms for L(p, 1)-Labeling by the twin cover number plus the maximum clique size and by the tree-width plus the maximum degree. These algorithms reduce the gap in terms of several combinations of parameters.

DOI： 10.7155/jgaa.00592

Reallocation Problems with Minimum Completion Time

Ishii, T; Kawahara, J; Makino, K; Ono, H

COMPUTING AND COMBINATORICS, COCOON 2022 13595 巻頁： 292 - 304 2022年

掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Reallocation scheduling is one of the most fundamental problems in various areas such as supply chain management, logistics, and transportation science. In this paper, we introduce the reallocation problem that models the scheduling in which products are with fixed cost (e.g., transition time), non-fungible, and reallocated among warehouses in parallel, and comprehensively study the complexity of the problem under various settings of the transition time, product size, and capacities. We show that the problem can be solved in polynomial time for a fundamental setting where the product size and transition time are both uniform. We also show that the feasibility of the problem is NP-complete even for little more general settings, which implies that no polynomial-time algorithm constructs a feasible schedule of the problem unless P = NP. We then consider to solve the problem by relaxing capacity constraints, which we call the capacity augmentation, and derive a reallocation schedule feasible with the augmentation such that the completion time is at most the optimal of the original problem. When the warehouse capacity is sufficiently large, we design constant-factor approximation algorithms. We also show the relationship between the reallocation problem and the bin packing problem when the warehouse and carry-in capacities are sufficiently large.

DOI： 10.1007/978-3-031-22105-7_26

その他リンク： https://dblp.uni-trier.de/db/conf/cocoon/cocoon2022.html#IshiiKMO22

コンピュテーション研究会　近況報告

増澤利光, 小野廣隆, 安藤映, 大下福仁

情報・システムソサイエティ誌 26 巻 ( 2 ) 頁： 10 - 11 2021年8月

Staging of astrocytopathy and complement activation in neuromyelitis optica spectrum disorders Open Access

Takai Y., Misu T., Suzuki H., Takahashi T., Okada H., Tanaka S., Okita K., Sasou S., Watanabe M., Namatame C., Matsumoto Y., Ono H., Kaneko K., Nishiyama S., Kuroda H., Nakashima I., Lassmann H., Fujihara K., Itoyama Y., Aoki M.

Brain 144 巻 ( 8 ) 頁： 2401 - 2415 2021年8月

出版者・発行元：Brain

Aquaporin 4 (AQP4)-IgG-positive neuromyelitis optica spectrum disorder (AQP4-IgG+NMOSD) is an autoimmune astrocytopathic disease pathologically characterized by the massive destruction and regeneration of astrocytes with diverse types of tissue injury with or without complement deposition. However, it is unknown whether this diversity is derived from differences in pathological processes or temporal changes. Furthermore, unlike for the demyelinating lesions in multiple sclerosis, there has been no staging of astrocytopathy in AQP4-IgG+NMOSD based on astrocyte morphology. Therefore, we classified astrocytopathy of the disease by comparing the characteristic features, such as AQP4 loss, inflammatory cell infiltration, complement deposition and demyelination activity, with the clinical phase. We performed histopathological analyses in eight autopsied cases of AQP4-IgG+NMOSD. Cases comprised six females and two males, with a median age of 56.5 years (range, 46-71 years) and a median disease duration of 62.5 months (range, 0.6-252 months). Astrocytopathy in AQP4-IgG+NMOSD was classified into the following four stages defined by the astrocyte morphology and immunoreactivity for GFAP: (i) astrocyte lysis: extensive loss of astrocytes with fragmented and/or dust-like particles; (ii) progenitor recruitment: loss of astrocytes except small nucleated cells with GFAP-positive fibre-forming foot processes; (iii) protoplasmic gliosis: presence of star-shaped astrocytes with abundant GFAP-reactive cytoplasm; and (iv) fibrous gliosis: lesions composed of densely packed mature astrocytes. The astrocyte lysis and progenitor recruitment stages dominated in clinically acute cases (within 2 months after the last recurrence). Findings common to both stages were the loss of AQP4, a decreased number of oligodendrocytes, the selective loss of myelin-associated glycoprotein and active demyelination with phagocytic macrophages. The infiltration of polymorphonuclear cells and T cells (CD4-dominant) and the deposition of activated complement (C9neo), which reflects the membrane attack complex, a hallmark of acute NMOSD lesions, were selectively observed in the astrocyte lysis stage (98.4% in astrocyte lysis, 1.6% in progenitor recruitment, and 0% in protoplasmic gliosis and fibrous gliosis). Although most of the protoplasmic gliosis and fibrous gliosis lesions were accompanied by inactive demyelinated lesions with a low amount of inflammatory cell infiltration, the deposition of complement degradation product (C3d) was observed in all four stages, even in fibrous gliosis lesions, suggesting the past or chronic occurrence of complement activation, which is a useful finding to distinguish chronic lesions in NMOSD from those in multiple sclerosis. Our staging of astrocytopathy is expected to be useful for understanding the unique temporal pathology of AQP4-IgG+NMOSD.

DOI： 10.1093/brain/awab102

Hedonic seat arrangement problems

Bodlaender H.L., Hanaka T., Jaffke L., Ono H., Otachi Y., van der Zanden T.C.

Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020-May 巻頁： 1777 - 1779 2020年

記述言語：日本語出版者・発行元：Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

In this paper, we study a variant of hedonic games, called Seat Arrangement. The model is defined by a bijection from agents with preferences to vertices in a graph. The utility of an agent depends on the neighbors in the graph. In this paper, we study the price of stability and fairness in Seat Arrangement, and the computational complexity and the parameterized complexity of finding certain “good” seat arrangements, say Maximum Welfare Arrangement, Maximin Utility Arrangement, Stable Arrangement, and Envy-free Arrangement.

Hedonic Seat Arrangement Problems 査読有り国際共著

小野廣隆

Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems - 巻頁： 1777 - 1779 2020年

Fair Ride Allocation on a Line

Amano Y., Igarashi A., Kawase Y., Makino K., Ono H.

ACM Transactions on Economics and Computation 13 巻 ( 1 ) 2025年3月

掲載種別：研究論文（学術雑誌）出版者・発行元：ACM Transactions on Economics and Computation

The airport problem is a classical and well-known model of fair cost-sharing for a single facility among multiple agents. This article extends it to a more general setting involving multiple facilities. Specifically, in our model, each agent selects a facility and shares the cost with the other agents using the same facility. This scenario frequently occurs in sharing economies, such as sharing subscription costs for a multi-user license or taxi fares among customers traveling to potentially different destinations along a route. Our model can be viewed as a coalition formation game with size constraints, based on the fair cost-sharing of the airport problem. We refer to our model as a fair ride allocation on a line. We incorporate Nash stability and envy-freeness as criteria for solution concepts in our setting. We show that if a feasible allocation exists, a Nash stable feasible allocation that minimizes the social cost of agents exists and can be computed efficiently. Regarding envy-freeness, we provide several structural properties of envy-free allocations. Based on these properties, we design efficient algorithms for finding an envy-free allocation when either (1) the number of facilities, (2) the number of agent types, or (3) the capacity of facilities, is small. Moreover, we show that a consecutive envy-free allocation can be computed in polynomial time. On the negative front, we show NP-completeness of determining the existence of an allocation under two relaxed envy-free concepts.

DOI： 10.1145/3708491

Fair Ride Allocation on a Line 査読有り

Yuki Amano, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hirotaka Ono

ACM Transactions on Economics and Computation 2025年2月

Computational complexity of <sc>Turning Tiles</sc>

Hanaka, T; Kiya, H; Ono, H; Suetsugu, K; Yoshiwatari, K

INTERNATIONAL JOURNAL OF GAME THEORY 53 巻 ( 4 ) 頁： 1211 - 1222 2024年12月

掲載種別：研究論文（学術雑誌）出版者・発行元：International Journal of Game Theory

In combinatorial game theory, the winning player for a position in normal play is analyzed and characterized via algebraic operations. Such analyses define a value for each position, called a game value. A game (ruleset) is called universal if any game value is achievable in some position in a play of the game. Although the universality of a game implies that the ruleset is rich enough (i.e., sufficiently complex), it does not immediately imply that the game is intractable in the sense of computational complexity. This paper proves that the universal game Turning Tiles is PSPACE-complete. We also give other positive and negative results on the computational complexity of Turning Tiles.

DOI： 10.1007/s00182-024-00908-0

その他リンク： https://link.springer.com/article/10.1007/s00182-024-00908-0/fulltext.html

Safe sets and in-dominating sets in digraphs

Bai, YD; Bang-Jensen, J; Fujita, S; Ono, H; Yeo, AD

DISCRETE APPLIED MATHEMATICS 346 巻頁： 215 - 227 2024年3月

掲載種別：研究論文（学術雑誌）出版者・発行元：Discrete Applied Mathematics

A non-empty subset S of the vertices of a digraph D is a safe set if (i) for every strongly connected component M of D−S, there exists a strongly connected component N of D[S] such that there exists an arc from M to N; and (ii) for every strongly connected component M of D−S and every strongly connected component N of D[S], we have |M|≤|N| whenever there exists an arc from M to N. In the case of acyclic digraphs a set X of vertices is a safe set precisely when X is an in-dominating set, that is, every vertex not in X has at least one arc to X. We prove that, even for acyclic digraphs which are traceable (have a hamiltonian path) it is NP-hard to find a minimum cardinality safe (in-dominating) set. Then we show that the problem is also NP-hard for tournaments and give, for every positive constant c, a polynomial algorithm for finding a minimum cardinality safe set in a tournament on n vertices in which no strong component has size more than clog(n). Under the so called Exponential Time Hypothesis (ETH) this is close to best possible in the following sense: If ETH holds, then, for every ϵ>0 there is no polynomial time algorithm for finding a minimum cardinality safe set for the class of tournaments in which the largest strong component has size at most log1+ϵ(n). We also discuss bounds on the cardinality of safe sets in tournaments.

DOI： 10.1016/j.dam.2023.12.012

Collecting Balls on a Line by Robots with Limited Energy Open Access

Hanaka, T; Droguett, NH; Kurita, K; Ono, H; Otachi, Y

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E107.D 巻 ( 3 ) 頁： 325 - 327 2024年3月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：一般社団法人電子情報通信学会

In this paper, we study Ball Collecting with Limited Energy, which is a problem of scheduling robots with limited energy confined to a line to catch moving balls that eventually cross the line. For this problem, we show the NP-completeness of the general case and some algorithmic results for some cases with a small number of robots.

DOI： 10.1587/transinf.2023fcl0003

On a Spectral Lower Bound of Treewidth Open Access

Gima, T; Hanaka, T; Noro, K; Ono, H; Otachi, Y

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E107.D 巻 ( 3 ) 頁： 328 - 330 2024年3月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：一般社団法人電子情報通信学会

In this letter, we present a new lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. Our bound slightly improves the lower bound given by Chandran and Subramanian [Inf. Process. Lett., 87 (2003)].

DOI： 10.1587/transinf.2023fcl0002

On the Computational Complexity of Generalized Common Shape Puzzles

Banbara, M; Minato, S; Ono, H; Uehara, R

SOFSEM 2024: THEORY AND PRACTICE OF COMPUTER SCIENCE 14519 巻頁： 55 - 68 2024年

掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

In this study, we investigate the computational complexity of some variants of generalized puzzles. We are provided with two sets S1 and S2 of polyominoes. The first puzzle asks us to form the same shape using polyominoes in S1 and S2. We demonstrate that this is polynomial-time solvable if S1 and S2 have constant numbers of polyominoes, and it is strongly NP-complete in general. The second puzzle allows us to make copies of the pieces in S1 and S2. That is, a polyomino in S1 can be used multiple times to form a shape. This is a generalized version of the classical puzzle known as the common multiple shape puzzle. For two polyominoes P and Q, the common multiple shape is a shape that can be formed by many copies of P and many copies of Q. We show that the second puzzle is undecidable in general. The undecidability is demonstrated by a reduction from a new type of undecidable puzzle based on tiling. Nevertheless, certain concrete instances of the common multiple shape can be solved in a practical time. We present a method for determining the common multiple shape for provided tuples of polyominoes and outline concrete results, which improve on the previously known results in the puzzle community.

DOI： 10.1007/978-3-031-52113-3_4

その他リンク： https://dblp.uni-trier.de/db/conf/sofsem/sofsem2024.html#BanbaraMOU24

Shortest Longest-Path Graph Orientations

Asahiro Y., Jansson J., Melkman A.A., Miyano E., Ono H., Xue Q., Zakov S.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 14422 LNCS 巻頁： 141 - 154 2024年

掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

We consider a graph orientation problem that can be viewed as a generalization of Minimum Graph Coloring. Our problem takes as input an undirected graph G= (V, E) in which every edge { u, v} ∈ E has two (potentially different and not necessarily positive) weights representing the lengths of its two possible directions (u, v) and (v, u), and asks for an orientation, i.e., an assignment of a direction to each edge of G, such that the length of a longest simple directed path in the resulting directed graph is minimized. A longest path in a graph is not always a maximal path when some edges have negative lengths, so the problem has two variants depending on whether all simple directed paths or maximal simple directed paths only are taken into account in the definition. We prove that the problems are NP-hard to approximate even if restricted to subcubic planar graphs, and develop fast polynomial-time algorithms for both problem variants for three classes of graphs: path graphs, cycle graphs, and star graphs.

DOI： 10.1007/978-3-031-49190-0_10

Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints

Kobayashi, Y; Kurita, K; Matsui, Y; Ono, H

COMBINATORIAL ALGORITHMS, IWOCA 2024 14764 巻頁： 232 - 246 2024年

An improved spectral lower bound of treewidth.

Tatsuya Gima, Tesshu Hanaka, Kohei Noro, Hirotaka Ono 0001, Yota Otachi

CoRR abs/2404.08520 巻 2024年

　前のページ - 次のページ　

1
2
3
4
5
6
7
8
9
10
11
12