Arrow Research search

Author name cluster

Yusuke Kobayashi

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

19 papers
1 author row

Possible papers

19

AAAI Conference 2023 Conference Paper

A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems

  • Tesshu Hanaka
  • Masashi Kiyomi
  • Yasuaki Kobayashi
  • Yusuke Kobayashi
  • Kazuhiro Kurita
  • Yota Otachi

Finding a \emph{single} best solution is the most common objective in combinatorial optimization problems. However, such a single solution may not be applicable to real-world problems as objective functions and constraints are only ``approximately'' formulated for original real-world problems. To solve this issue, finding \emph{multiple} solutions is a natural direction, and diversity of solutions is an important concept in this context. Unfortunately, finding diverse solutions is much harder than finding a single solution. To cope with the difficulty, we investigate the approximability of finding diverse solutions. As a main result, we propose a framework to design approximation algorithms for finding diverse solutions, which yields several outcomes including constant-factor approximation algorithms for finding diverse matchings in graphs and diverse common bases in two matroids and PTASes for finding diverse minimum cuts and interval schedulings.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Reforming an Envy-Free Matching

  • Takehiro Ito
  • Yuni Iwamasa
  • Naonori Kakimura
  • Naoyuki Kamiyama
  • Yusuke Kobayashi
  • Yuta Nozaki
  • Yoshio Okamoto
  • Kenta Ozeki

We consider the problem of reforming an envy-free matching when each agent is assigned a single item. Given an envy-free matching, we consider an operation to exchange the item of an agent with an unassigned item preferred by the agent that results in another envy-free matching. We repeat this operation as long as we can. We prove that the resulting envy-free matching is uniquely determined up to the choice of an initial envy-free matching, and can be found in polynomial time. We call the resulting matching a reformist envy-free matching, and then we study a shortest sequence to obtain the reformist envy-free matching from an initial envy-free matching. We prove that a shortest sequence is computationally hard to obtain even when each agent accepts at most four items and each item is accepted by at most three agents. On the other hand, we give polynomial-time algorithms when each agent accepts at most three items or each item is accepted by at most two agents. Inapproximability and fixed-parameter (in)tractability are also discussed.

PDF Details

AAMAS Conference 2019 Conference Paper

Algorithms for Gerrymandering over Graphs

  • Takehiro Ito
  • Naoyuki Kamiyama
  • Yusuke Kobayashi
  • Yoshio Okamoto

We initiate the systematic algorithmic study for gerrymandering over graphs that was recently introduced by Cohen-Zemach, Lewenberg and Rosenschein. Namely, we study a strategic procedure for a political districting designer to draw electoral district boundaries so that a particular target candidate can win in an election. We focus on the existence of such a strategy under the plurality voting rule, and give interesting contrasts which classify easy and hard instances with respect to polynomial-time solvability. For example, we prove that the problem for trees is strongly NP-complete (thus unlikely to have a pseudo-polynomial-time algorithm), but has a pseudo-polynomial-time algorithm when the number of candidates is constant. Another example is to prove that the problem for complete graphs is NP-complete when the number of electoral districts is two, while is solvable in polynomial time when it is more than two.

PDF