2025/10/21 更新

写真a

アマノ ユウキ
天野 雄樹
AMANO Yuki
所属
理工学部 助教C
連絡先
メールによる問い合わせは《こちら》から
外部リンク

学位

  • 博士(理学) ( 京都大学 )

  • 修士(理学) ( 京都大学 )

学歴

  • 2023年3月
     

    京都大学   理学研究科   数学・数理解析専攻数理解析系   博士後期   修了

  • 2020年3月
     

    京都大学   理学研究科   数学・数理解析専攻数理解析系   修士   修了

  • 2018年3月
     

    京都大学   理学部   理学科   卒業

経歴

  • 2023年4月 - 現在

    中央大学   理工学部   助教C

所属学協会

  • 2021年5月 - 現在

    一般社団法人情報処理学会

  • 2021年1月 - 現在

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

研究分野

  • 情報通信 / 情報学基礎論

論文

MISC

  • グラフ上で局所的に定義される独立性システム

    研究報告アルゴリズム(AL)   2023-AL-191 ( 5 )   1 - 8   2023年1月

     詳細を見る

  • Locally Defined Independence Systems on Graphs

    Yuki Amano

    CoRR   abs/2208.10003   2022年8月

     詳細を見る

    The maximization for the independence systems defined on graphs is a
    generalization of combinatorial optimization problems such as the maximum
    $b$-matching, the unweighted MAX-SAT, the matchoid, and the maximum timed
    matching problems. In this paper, we consider the problem under the local
    oracle model to investigate the global approximability of the problem by using
    the local approximability. We first analyze two simple algorithms FixedOrder
    and Greedy for the maximization under the model, which shows that they have no
    constant approximation ratio. Here algorithms FixedOrder and Greedy apply local
    oracles with fixed and greedy orders of vertices, respectively. We then propose
    two approximation algorithms for the $k$-degenerate graphs, whose approximation
    ratios are $\alpha +2k -2$ and $\alpha k$, where $\alpha$ is the approximation
    ratio of local oracles. The second one can be generalized to the hypergraph
    setting. We also propose an $(\alpha + k)$-approximation algorithm for
    bipartite graphs, in which the local independence systems in the one-side of
    vertices are $k$-systems with independence oracles.

    DOI: 10.48550/arXiv.2208.10003

    arXiv

    researchmap

  • 巡回セールスマン問題に対する多項式時間3/4-偏差近似アルゴリズム

    研究報告アルゴリズム(AL)   2021-AL-182, ( 12 )   1 - 7   2021年3月

     詳細を見る

  • A 3/4 Differential Approximation Algorithm for Traveling Salesman Problem

    Yuki Amano, Kazuhisa Makino

    CoRR   abs/2012.14079   2020年12月

     詳細を見る

    In this paper, we consider differential approximability of the traveling
    salesman problem (TSP). We show that TSP is $3/4$-differential approximable,
    which improves the currently best known bound $3/4 -O(1/n)$ due to Escoffier
    and Monnot in 2008, where $n$ denotes the number of vertices in the given
    graph.

    arXiv

    researchmap

    その他リンク: https://dblp.uni-trier.de/db/journals/corr/corr2012.html#abs-2012-14079

  • Fair Ride Allocation on a Line

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

    CoRR   abs/2007.08045   2020年7月

     詳細を見る

    The airport game 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, taxis among customers of possibly different destinations
    on a line, and so on. Our model is regarded as a coalition formation game based
    on the fair cost-sharing of the airport game; we call our model \emph{a fair
    ride allocation on a line}. As 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 at least
    one of (1) the number of facilities, (2) the capacity of facilities, and (3)
    the number of agent types, 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.

    arXiv

    researchmap

    その他リンク: https://dblp.uni-trier.de/db/journals/corr/corr2007.html#abs-2007-08045

講演・口頭発表等

  • Fair Ride Allocation on a Line

    日本OR学会研究部会:最適化の理論とアルゴリズム(RAOTA)第 8 回研究会  2025年1月 

     詳細を見る

  • A 3/4 Differential Approximation Algorithm for Traveling Salesman Problem

    Yuki Amano, Kazuhisa Makino

    The 17th Annual Conference on Theory and Applications of Models of Computation  2022年9月 

     詳細を見る

  • グラフ上で局所的に定義される独立性システム

    天野雄樹

    Japanese Conference on Combinatorics and its Applications 2022 組合せ最適化 ミニシンポジウム  2022年8月 

     詳細を見る

  • Locally Defined Independence Systems on Graphs

    天野雄樹

    最適化手法とアルゴリズム ─未来を担う若手研究者の集い 2022─  2022年6月 

     詳細を見る

  • 巡回セールスマン問題に対する多項式時間3/4-偏差近似アルゴリズム

    天野雄樹, 牧野和久

    情報処理学会第182回アルゴリズム研究会  2020年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

受賞

  • 2021年度コンピュータサイエンス領域奨励賞

    2021年11月   一般社団法人情報処理学会