4 Search Results for "Seddighin, Masoud"

Document
Short Paper
DOI: 10.4230/LIPIcs.CP.2024.37
Computing Small Rainbow Cycle Numbers with SAT Modulo Symmetries (Short Paper)

Authors: Markus Kirchweger and Stefan Szeider

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
Envy-freeness up to any good (EFX) is a key concept in Computational Social Choice for the fair division of indivisible goods, where no agent envies another’s allocation after removing any single item. A deeper understanding of EFX allocations is facilitated by exploring the rainbow cycle number (R_f(d)), the largest number of independent sets in a certain class of directed graphs. Upper bounds on R_f(d) provide guarantees to the feasibility of EFX allocations (Chaudhury et al., EC 2021). In this work, we precisely compute the numbers R_f(d) for small values of d, employing the SAT modulo Symmetries framework (Kirchweger and Szeider, CP 2021). SAT modulo Symmetries is tailored specifically for the constraint-based isomorph-free generation of combinatorial structures. We provide an efficient encoding for the rainbow cycle number, comparing eager and lazy approaches. To cope with the huge search space, we extend the encoding with invariant pruning, a new method that significantly speeds up computation.
Cite as

Markus Kirchweger and Stefan Szeider. Computing Small Rainbow Cycle Numbers with SAT Modulo Symmetries (Short Paper). In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 37:1-37:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kirchweger_et_al:LIPIcs.CP.2024.37,
  author =	{Kirchweger, Markus and Szeider, Stefan},
  title =	{{Computing Small Rainbow Cycle Numbers with SAT Modulo Symmetries}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{37:1--37:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.37},
  URN =		{urn:nbn:de:0030-drops-207221},
  doi =		{10.4230/LIPIcs.CP.2024.37},
  annote =	{Keywords: EFX, rainbow cycle number, SAT modulo Symmetries, combinatorial search}
}
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 Kirchweger, Markus
  • 1 Seddighin, Masoud
  • 1 Seddighin, Saeed
  • 1 Szeider, Stefan
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Algorithmic game theory and mechanism design
  • 1 Hardware → Theorem proving and SAT solving
  • 1 Mathematics of computing → Extremal graph theory
  • 1 Mathematics of computing → Graph enumeration
  • 1 Software and its engineering → Constraint and logic languages
  • Show More...

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

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2020
  • 1 2021
  • 1 2022
  • 1 2024

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact