2 Search Results for "C�sar, Eduardo"


Document
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
Development and Tuning Framework of Master/Worker Applications

Authors: Paola Caymes-Scutari, Anna Morajko, Eduardo César, Genaro Costa, José G. Mesa, Tomàs Margalef, Joan Sorribes, and Emilio Luque

Published in: Dagstuhl Seminar Proceedings, Volume 5501, Automatic Performance Analysis (2006)


Abstract
Parallel/distributed programming is a complex task that requires a high degree of expertise to fulfill the expectations of high performance computation. The Master/Worker paradigm is one of the most commonly used because it is easy to understand and there is a wide range of applications that match this paradigm. However, there are certain features, such as data distribution and the number of workers that must be tuned properly to obtain adequate performance. In most cases such features cannot be tuned statically since they depend on the particular conditions of each execution. In this paper, we show a dynamic tuning environment that is based on a theoretical model of Master/Worker behavior and allows for the adaptation of such applications to the dynamic conditions of execution. The environment includes a pattern based application development framework that allows the user to concentrate on the design phase and makes it easier to overcome performance bottlenecks.

Cite as

Paola Caymes-Scutari, Anna Morajko, Eduardo César, Genaro Costa, José G. Mesa, Tomàs Margalef, Joan Sorribes, and Emilio Luque. Development and Tuning Framework of Master/Worker Applications. In Automatic Performance Analysis. Dagstuhl Seminar Proceedings, Volume 5501, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{caymesscutari_et_al:DagSemProc.05501.3,
  author =	{Caymes-Scutari, Paola and Morajko, Anna and C\'{e}sar, Eduardo and Costa, Genaro and Mesa, Jos\'{e} G. and Margalef, Tom\`{a}s and Sorribes, Joan and Luque, Emilio},
  title =	{{Development and Tuning Framework of Master/Worker Applications}},
  booktitle =	{Automatic Performance Analysis},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5501},
  editor =	{Hans Michael Gerndt and Allen Malony and Barton P. Miller and Wolfgang Nagel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05501.3},
  URN =		{urn:nbn:de:0030-drops-5057},
  doi =		{10.4230/DagSemProc.05501.3},
  annote =	{Keywords: Dynamic tuning, performance analysis, performance model}
}
  • Refine by Author
  • 1 Caymes-Scutari, Paola
  • 1 Costa, Genaro
  • 1 César, Eduardo
  • 1 Hokama, Pedro Henrique D. B.
  • 1 Luque, Emilio
  • 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
  • 1 Dynamic tuning
  • 1 Less-than-Truckload
  • 1 Pickup-and-Delivery
  • 1 Routing
  • 1 Steiner Cycle
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2006
  • 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