2 Search Results for "Mera, Sergio"


Document
Inapproximability of H-Transversal/Packing

Authors: Venkatesan Guruswami and Euiwoong Lee

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)


Abstract
Given an undirected graph G=(V,E) and a fixed pattern graph H with k vertices, we consider the H-Transversal and H-Packing problems. The former asks to find the smallest subset S of vertices such that the subgraph induced by V - S does not have H as a subgraph, and the latter asks to find the maximum number of pairwise disjoint k-subsets S1, ..., Sm such that the subgraph induced by each Si has H as a subgraph. We prove that if H is 2-connected, H-Transversal and H-Packing are almost as hard to approximate as general k-Hypergraph Vertex Cover and k-Set Packing, so it is NP-hard to approximate them within a factor of Omega(k) and Omega(k / polylog(k)) respectively. We also show that there is a 1-connected H where H-Transversal admits an O(log k)-approximation algorithm, so that the connectivity requirement cannot be relaxed from 2 to 1. For a special case of H-Transversal where H is a (family of) cycles, we mention the implication of our result to the related Feedback Vertex Set problem, and give a different hardness proof for directed graphs.

Cite as

Venkatesan Guruswami and Euiwoong Lee. Inapproximability of H-Transversal/Packing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 284-304, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{guruswami_et_al:LIPIcs.APPROX-RANDOM.2015.284,
  author =	{Guruswami, Venkatesan and Lee, Euiwoong},
  title =	{{Inapproximability of H-Transversal/Packing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{284--304},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.284},
  URN =		{urn:nbn:de:0030-drops-53085},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.284},
  annote =	{Keywords: Constraint Satisfaction Problems, Approximation resistance}
}
Document
Computational Models for Normative Multi-Agent Systems

Authors: Natasha Alechina, Nick Bassiliades, Mehdi Dastani, Marina De Vos, Brian Logan, Sergio Mera, Andreasa Morris-Martin, and Fernando Schapachnik

Published in: Dagstuhl Follow-Ups, Volume 4, Normative Multi-Agent Systems (2013)


Abstract
This chapter takes a closer look at computational logic approaches for the design, verification and the implementation of normative multi-agent systems. After a short overview of existing formalisms, architectures and implementation languages, an overview of current research challenges is provided.

Cite as

Natasha Alechina, Nick Bassiliades, Mehdi Dastani, Marina De Vos, Brian Logan, Sergio Mera, Andreasa Morris-Martin, and Fernando Schapachnik. Computational Models for Normative Multi-Agent Systems. In Normative Multi-Agent Systems. Dagstuhl Follow-Ups, Volume 4, pp. 71-92, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InCollection{alechina_et_al:DFU.Vol4.12111.71,
  author =	{Alechina, Natasha and Bassiliades, Nick and Dastani, Mehdi and De Vos, Marina and Logan, Brian and Mera, Sergio and Morris-Martin, Andreasa and Schapachnik, Fernando},
  title =	{{Computational Models for Normative Multi-Agent Systems}},
  booktitle =	{Normative Multi-Agent Systems},
  pages =	{71--92},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-939897-51-4},
  ISSN =	{1868-8977},
  year =	{2013},
  volume =	{4},
  editor =	{Andrighetto, Giulia and Governatori, Guido and Noriega, Pablo and van der Torre, Leendert W. N.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DFU.Vol4.12111.71},
  URN =		{urn:nbn:de:0030-drops-40001},
  doi =		{10.4230/DFU.Vol4.12111.71},
  annote =	{Keywords: Norm verification, Computational Architectures for Normative MAS, Programming Normative Systems}
}
  • Refine by Author
  • 1 Alechina, Natasha
  • 1 Bassiliades, Nick
  • 1 Dastani, Mehdi
  • 1 De Vos, Marina
  • 1 Guruswami, Venkatesan
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Approximation resistance
  • 1 Computational Architectures for Normative MAS
  • 1 Constraint Satisfaction Problems
  • 1 Norm verification
  • 1 Programming Normative Systems

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2013
  • 1 2015

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