6 Search Results for "Gonz�lez-Guill�n, Carlos E."

Document
DOI: 10.4230/LIPIcs.SEA.2018.26
The Steiner Multi Cycle Problem with Applications to a Collaborative Truckload Problem

Authors: Vinicius N. G. Pereira, Mário César San Felice, Pedro Henrique D. B. Hokama, and Eduardo C. Xavier

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract
We introduce a new problem called Steiner Multi Cycle Problem that extends the Steiner Cycle problem in the same way the Steiner Forest extends the Steiner Tree problem. In this problem we are given a complete weighted graph G=(V,E), which respects the triangle inequality, a collection of terminal sets {T_1,..., T_k}, where for each a in [k] we have a subset T_a of V and these terminal sets are pairwise disjoint. The problem is to find a set of disjoint cycles of minimum cost such that for each a in [k], all vertices of T_a belong to a same cycle. Our main interest is in a restricted case where |T_a| = 2, for each a in [k], which models a collaborative less-than-truckload problem with pickup and delivery. In this problem, we have a set of agents where each agent is associated with a set T_a containing a pair of pickup and delivery vertices. This problem arises in the scenario where a company has to periodically exchange goods between two different locations, and different companies can collaborate to create a route that visits all its pairs of locations sharing the total cost of the route. We show that even the restricted problem is NP-Hard, and present some heuristics to solve it. In particular, a constructive heuristic called Refinement Search, which uses geometric properties to determine if agents are close to each other. We performed computational experiments to compare this heuristic to a GRASP based heuristic. The Refinement Search obtained the best solutions in little computational time.
Cite as

Vinicius N. G. Pereira, Mário César San Felice, Pedro Henrique D. B. Hokama, and Eduardo C. Xavier. The Steiner Multi Cycle Problem with Applications to a Collaborative Truckload Problem. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 26:1-26:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{pereira_et_al:LIPIcs.SEA.2018.26,
  author =	{Pereira, Vinicius N. G. and San Felice, M\'{a}rio C\'{e}sar and Hokama, Pedro Henrique D. B. and Xavier, Eduardo C.},
  title =	{{The Steiner Multi Cycle Problem with Applications to a Collaborative Truckload Problem}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{26:1--26:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.26},
  URN =		{urn:nbn:de:0030-drops-89617},
  doi =		{10.4230/LIPIcs.SEA.2018.26},
  annote =	{Keywords: Steiner Cycle, Routing, Pickup-and-Delivery, Less-than-Truckload}
}
Document
DOI: 10.4230/LIPIcs.CPM.2017.31
Synergistic Solutions on MultiSets

Authors: Jérémy Barbay, Carlos Ochoa, and Srinivasa Rao Satti

Published in: LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)

Abstract
Karp et al. (1988) described Deferred Data Structures for Multisets as "lazy" data structures which partially sort data to support online rank and select queries, with the minimum amount of work in the worst case over instances of size n and number of queries q fixed. Barbay et al. (2016) refined this approach to take advantage of the gaps between the positions hit by the queries (i.e., the structure in the queries). We develop new techniques in order to further refine this approach and take advantage all at once of the structure (i.e., the multiplicities of the elements), some notions of local order (i.e., the number and sizes of runs) and global order (i.e., the number and positions of existing pivots) in the input; and of the structure and order in the sequence of queries. Our main result is a synergistic deferred data structure which outperforms all solutions in the comparison model that take advantage of only a subset of these features. As intermediate results, we describe two new synergistic sorting algorithms, which take advantage of some notions of structure and order (local and global) in the input, improving upon previous results which take advantage only of the structure (Munro and Spira 1979) or of the local order (Takaoka 1997) in the input; and one new multiselection algorithm which takes advantage of not only the order and structure in the input, but also of the structure in the queries.
Cite as

Jérémy Barbay, Carlos Ochoa, and Srinivasa Rao Satti. Synergistic Solutions on MultiSets. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{barbay_et_al:LIPIcs.CPM.2017.31,
  author =	{Barbay, J\'{e}r\'{e}my and Ochoa, Carlos and Satti, Srinivasa Rao},
  title =	{{Synergistic Solutions on MultiSets}},
  booktitle =	{28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-039-2},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{78},
  editor =	{K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.31},
  URN =		{urn:nbn:de:0030-drops-73441},
  doi =		{10.4230/LIPIcs.CPM.2017.31},
  annote =	{Keywords: deferred data structure, multivariate analysis, quick sort, select}
}
Document
DOI: 10.4230/OASIcs.CMN.2016.11
Annotating Musical Theatre Plots on Narrative Structure and Emotional Content

Authors: Pablo Gervás, Raquel Hervás, Carlos León, and Catherine V. Gale

Published in: OASIcs, Volume 53, 7th Workshop on Computational Models of Narrative (CMN 2016)

Abstract
Although theoretical models of the structure of narrative arising from systematic analysis of corpora are available for domains such as Russian folk tales, there are no such sources for the plot lines of musical theatre. The present paper reports an effort of knowledge elicitation for features that characterise the narrative structure of plot in the particular domain of musical theatre. The following aspects are covered: identification of a valid vocabulary of abstract units to use in annotating musical theatre plots, development of a procedure for annotation - including a spread-sheet format for annotators to use, and a corresponding set of instructions to guide them through the process - selection of a corpus of musical theatre pieces that would constitute the corpus to be annotated, the annotation process itself and the results of post-processing the annotated corpus in search for insights on the narrative structure of musical theatre plots.
Cite as

Pablo Gervás, Raquel Hervás, Carlos León, and Catherine V. Gale. Annotating Musical Theatre Plots on Narrative Structure and Emotional Content. In 7th Workshop on Computational Models of Narrative (CMN 2016). Open Access Series in Informatics (OASIcs), Volume 53, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{gervas_et_al:OASIcs.CMN.2016.11,
  author =	{Gerv\'{a}s, Pablo and Herv\'{a}s, Raquel and Le\'{o}n, Carlos and Gale, Catherine V.},
  title =	{{Annotating Musical Theatre Plots on Narrative Structure and Emotional Content}},
  booktitle =	{7th Workshop on Computational Models of Narrative (CMN 2016)},
  pages =	{11:1--11:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-020-0},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{53},
  editor =	{Miller, Ben and Lieto, Antonio and Ronfard, R\'{e}mi and Ware, Stephen G. and Finlayson, Mark A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2016.11},
  URN =		{urn:nbn:de:0030-drops-67122},
  doi =		{10.4230/OASIcs.CMN.2016.11},
  annote =	{Keywords: Narrative annotation, conceptual representation of narrative, character functions, narrative schemas, musical theatre}
}
Document
DOI: 10.4230/LIPIcs.TQC.2015.39
How Many Quantum Correlations Are Not Local?

Authors: Carlos E. González-Guillén, C. Hugo Jiménez, Carlos Palazuelos, and Ignacio Villanueva

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
We study how generic is the property of nonlocality among the set of quantum correlations for bipartite dichotomic measurements. To do so, we consider the characterization of these quantum correlations as those of the form gamma = ( < u_i , v_j > )_{i,j=1}^n , where the vectors u_i and v_j are in the unit sphere of a real Hilbert space. The important parameters in this description are the number of vectors n and the dimension of the Hilbert space m. Thus, it is natural to study the probability of a quantum correlation being nonlocal as a function of alpha = m/n , where the previous vectors are independent and uniformly distributed in the unit sphere of R^m. In this situation, our main result shows the existence of two completely different regimes: There exists an alpha_0 > 0 such that if alpha leq alpha_0, then gamma is nonlocal with probability tending to 1 as n rightarrow infty. On the other hand, if alpha geq 2 then gamma is local with probability tending to 1 as n rightarrow infty.
Cite as

Carlos E. González-Guillén, C. Hugo Jiménez, Carlos Palazuelos, and Ignacio Villanueva. How Many Quantum Correlations Are Not Local?. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 39-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{gonzalezguillen_et_al:LIPIcs.TQC.2015.39,
  author =	{Gonz\'{a}lez-Guill\'{e}n, Carlos E. and Jim\'{e}nez, C. Hugo and Palazuelos, Carlos and Villanueva, Ignacio},
  title =	{{How Many Quantum Correlations Are Not Local?}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{39--47},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.39},
  URN =		{urn:nbn:de:0030-drops-55475},
  doi =		{10.4230/LIPIcs.TQC.2015.39},
  annote =	{Keywords: nonlocality, quantum correlations, Bell inequalities, random matrices}
}
Document
DOI: 10.4230/OASIcs.CMN.2015.54
Schemas for Narrative Generation Mined from Existing Descriptions of Plot

Authors: Pablo Gervás, Carlos León, and Gonzalo Méndez

Published in: OASIcs, Volume 45, 6th Workshop on Computational Models of Narrative (CMN 2015)

Abstract
Computational generation of literary artifacts very often resorts to template-like schemas that can be instantiated into complex structures. With this view in mind, the present paper reviews a number of existing attempts to provide an elementary set of patterns for basic plots. An attempt is made to formulate these descriptions of possible plots in terms of character functions, an abstraction of plot-bearing elements of a story originally formulated by Vladimir Propp. These character functions act as the building blocks of the Propper system, an existing framework for computational story generation. The paper explores the set of extensions required to the original set of character functions to allow for a basic representation of the analysed schemata, and a solution for automatic generation of stories based on this formulation of the narrative schemas. This solution uncovers important insights on the relative expressive power of the representation of narrative in terms of character functions, and their impact on the generative potential of the framework is discussed.
Cite as

Pablo Gervás, Carlos León, and Gonzalo Méndez. Schemas for Narrative Generation Mined from Existing Descriptions of Plot. In 6th Workshop on Computational Models of Narrative (CMN 2015). Open Access Series in Informatics (OASIcs), Volume 45, pp. 54-71, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{gervas_et_al:OASIcs.CMN.2015.54,
  author =	{Gerv\'{a}s, Pablo and Le\'{o}n, Carlos and M\'{e}ndez, Gonzalo},
  title =	{{Schemas for Narrative Generation Mined from Existing Descriptions of Plot}},
  booktitle =	{6th Workshop on Computational Models of Narrative (CMN 2015)},
  pages =	{54--71},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-93-4},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{45},
  editor =	{Finlayson, Mark A. and Miller, Ben and Lieto, Antonio and Ronfard, Remi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2015.54},
  URN =		{urn:nbn:de:0030-drops-52812},
  doi =		{10.4230/OASIcs.CMN.2015.54},
  annote =	{Keywords: Narrative generation, conceptual representation of narrative, character functions, plot, narrative schemas}
}
Document
DOI: 10.4230/OASIcs.WCET.2014.63
The Challenge of Time-Predictability in Modern Many-Core Architectures

Authors: Vincent Nélis, Patrick Meumeu Yomsi, Luís Miguel Pinho, José Carlos Fonseca, Marko Bertogna, Eduardo Quiñones, Roberto Vargas, and Andrea Marongiu

Published in: OASIcs, Volume 39, 14th International Workshop on Worst-Case Execution Time Analysis (2014)

Abstract
The recent technological advancements and market trends are causing an interesting phenomenon towards the convergence of High-Performance Computing (HPC) and Embedded Computing (EC) domains. Many recent HPC applications require huge amounts of information to be processed within a bounded amount of time while EC systems are increasingly concerned with providing higher performance in real-time. The convergence of these two domains towards systems requiring both high performance and a predictable time-behavior challenges the capabilities of current hardware architectures. Fortunately, the advent of next-generation many-core embedded platforms has the chance of intercepting this converging need for predictability and high-performance, allowing HPC and EC applications to be executed on efficient and powerful heterogeneous architectures integrating general-purpose processors with many-core computing fabrics. However, addressing this mixed set of requirements is not without its own challenges and it is now of paramount importance to develop new techniques to exploit the massively parallel computation capabilities of many-core platforms in a predictable way.
Cite as

Vincent Nélis, Patrick Meumeu Yomsi, Luís Miguel Pinho, José Carlos Fonseca, Marko Bertogna, Eduardo Quiñones, Roberto Vargas, and Andrea Marongiu. The Challenge of Time-Predictability in Modern Many-Core Architectures. In 14th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 39, pp. 63-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{nelis_et_al:OASIcs.WCET.2014.63,
  author =	{N\'{e}lis, Vincent and Yomsi, Patrick Meumeu and Pinho, Lu{\'\i}s Miguel and Fonseca, Jos\'{e} Carlos and Bertogna, Marko and Qui\~{n}ones, Eduardo and Vargas, Roberto and Marongiu, Andrea},
  title =	{{The Challenge of Time-Predictability in Modern Many-Core Architectures}},
  booktitle =	{14th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{63--72},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-69-9},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{39},
  editor =	{Falk, Heiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2014.63},
  URN =		{urn:nbn:de:0030-drops-46050},
  doi =		{10.4230/OASIcs.WCET.2014.63},
  annote =	{Keywords: Time-Predictability, Many-Cores, Multi-Cores, Timing Analysis}
}
  • Refine by Author
  • 2 Gervás, Pablo
  • 2 León, Carlos
  • 1 Barbay, Jérémy
  • 1 Bertogna, Marko
  • 1 Fonseca, José Carlos
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Transportation
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Routing and network design problems

  • Refine by Keyword
  • 2 character functions
  • 2 conceptual representation of narrative
  • 2 narrative schemas
  • 1 Bell inequalities
  • 1 Less-than-Truckload
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2015
  • 1 2014
  • 1 2016
  • 1 2017
  • 1 2018

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