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

DOI： 10.1016/j.tcs.2025.115435

researchmap

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

DOI： 10.1145/3708491

researchmap

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

DOI： 10.1016/j.dam.2022.11.001

researchmap

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

DOI： 10.1007/978-3-031-20350-3_19

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/tamc/tamc2022.html#AmanoM22

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

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

researchmap

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

researchmap

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

researchmap

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

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

researchmap

researchmap

researchmap

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap