3 Search Results for "Seddighin, Masoud"

Document

DOI: 10.4230/LIPIcs.ITCS.2022.115

3+ε Approximation of Tree Edit Distance in Truly Subquadratic Time

Authors: Masoud Seddighin and Saeed Seddighin

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract

Tree edit distance is a well-known generalization of the edit distance problem to rooted trees. In this problem, the goal is to transform a rooted tree into another rooted tree via (i) node addition, (ii) node deletion, and (iii) node relabel. In this work, we give a truly subquadratic time algorithm that approximates tree edit distance within a factor 3+ε. Our result is obtained through a novel extension of a 3-step framework that approximates edit distance in truly subquadratic time. This framework has also been previously used to approximate longest common subsequence in subquadratic time.

Cite as

Masoud Seddighin and Saeed Seddighin. 3+ε Approximation of Tree Edit Distance in Truly Subquadratic Time. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 115:1-115:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{seddighin_et_al:LIPIcs.ITCS.2022.115,
  author =	{Seddighin, Masoud and Seddighin, Saeed},
  title =	{{3+\epsilon Approximation of Tree Edit Distance in Truly Subquadratic Time}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{115:1--115:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.115},
  URN =		{urn:nbn:de:0030-drops-157116},
  doi =		{10.4230/LIPIcs.ITCS.2022.115},
  annote =	{Keywords: tree edit distance, approximation, subquadratic, edit distance}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2021.68

Simple Envy-Free and Truthful Mechanisms for Cake Cutting with a Small Number of Cuts

Authors: Takao Asano

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract

For the cake-cutting problem, Alijani, et al. [Reza Alijani et al., 2017; Masoud Seddighin et al., 2019] and Asano and Umeda [Takao Asano and Hiroyuki Umeda, 2020; Takao Asano and Hiroyuki Umeda, 2020] gave envy-free and truthful mechanisms with a small number of cuts, where the desired part of each player’s valuation function is a single interval on a given cake. In this paper, we give envy-free and truthful mechanisms with a small number of cuts, which are much simpler than those proposed by Alijani, et al. [Reza Alijani et al., 2017; Masoud Seddighin et al., 2019] and Asano and Umeda [Takao Asano and Hiroyuki Umeda, 2020; Takao Asano and Hiroyuki Umeda, 2020]. Furthermore, we show that this approach can be applied to the envy-free and truthful mechanism proposed by Chen, et al. [Yiling Chen et al., 2013], where the valuation function of each player is more general and piecewise uniform. Thus, we can obtain an envy-free and truthful mechanism with a small number of cuts even if the valuation function of each player is piecewise uniform, which solves the future problem posed by Alijani, et al. [Reza Alijani et al., 2017; Masoud Seddighin et al., 2019].

Cite as

Takao Asano. Simple Envy-Free and Truthful Mechanisms for Cake Cutting with a Small Number of Cuts. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 68:1-68:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{asano:LIPIcs.ISAAC.2021.68,
  author =	{Asano, Takao},
  title =	{{Simple Envy-Free and Truthful Mechanisms for Cake Cutting with a Small Number of Cuts}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{68:1--68:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.68},
  URN =		{urn:nbn:de:0030-drops-155011},
  doi =		{10.4230/LIPIcs.ISAAC.2021.68},
  annote =	{Keywords: cake-cutting problem, envy-freeness, fairness, truthfulness, mechanism design}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2020.15

Cake Cutting: An Envy-Free and Truthful Mechanism with a Small Number of Cuts

Authors: Takao Asano and Hiroyuki Umeda

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract

The mechanism for the cake-cutting problem based on the expansion process with unlocking proposed by Alijani, Farhadi, Ghodsi, Seddighin, and Tajik [Reza Alijani et al., 2017; Masoud Seddighin et al., 2019] uses a small number of cuts, but is not actually envy-free and truthful, although they claimed that it is envy-free and truthful. In this paper, we consider the same cake-cutting problem and give a new envy-free and truthful mechanism with a small number of cuts, which is not based on their expansion process with unlocking.

Cite as

Takao Asano and Hiroyuki Umeda. Cake Cutting: An Envy-Free and Truthful Mechanism with a Small Number of Cuts. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{asano_et_al:LIPIcs.ISAAC.2020.15,
  author =	{Asano, Takao and Umeda, Hiroyuki},
  title =	{{Cake Cutting: An Envy-Free and Truthful Mechanism with a Small Number of Cuts}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.15},
  URN =		{urn:nbn:de:0030-drops-133599},
  doi =		{10.4230/LIPIcs.ISAAC.2020.15},
  annote =	{Keywords: cake-cutting problem, envy-freeness, fairness, truthfulness, mechanism design}
}

Refine by Author
2 Asano, Takao
1 Seddighin, Masoud
1 Seddighin, Saeed
1 Umeda, Hiroyuki

Refine by Classification
2 Theory of computation → Algorithmic game theory and mechanism design
1 Theory of computation → Design and analysis of algorithms

Refine by Keyword
2 cake-cutting problem
2 envy-freeness
2 fairness
2 mechanism design
2 truthfulness
Show More...

Refine by Type
3 document

Refine by Publication Year
1 2020
1 2021
1 2022