4 Search Results for "Morales, José F."


Document
Track A: Algorithms, Complexity and Games
A Water-Filling Primal-Dual Algorithm for Approximating Non-Linear Covering Problems

Authors: Andrés Fielbaum, Ignacio Morales, and José Verschae

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)


Abstract
Obtaining strong linear relaxations of capacitated covering problems constitute a significant technical challenge even for simple settings. For one of the most basic cases, the Knapsack-Cover (Min-Knapsack) problem, the relaxation based on knapsack-cover inequalities has an integrality gap of 2. These inequalities are exploited in more general problems, many of which admit primal-dual approximation algorithms. Inspired by problems from power and transport systems, we introduce a general setting in which items can be taken fractionally to cover a given demand. The cost incurred by an item is given by an arbitrary non-decreasing function of the chosen fraction. We generalize the knapsack-cover inequalities to this setting an use them to obtain a (2+ε)-approximate primal-dual algorithm. Our procedure has a natural interpretation as a bucket-filling algorithm which effectively overcomes the difficulties implied by having different slopes in the cost functions. More precisely, when some superior segment of an item presents a low slope, it helps to increase the priority of inferior segments. We also present a rounding algorithm with an approximation guarantee of 2. We generalize our algorithm to the Unsplittable Flow-Cover problem on a line, also for the setting of fractional items with non-linear costs. For this problem we obtain a (4+ε)-approximation algorithm in polynomial time, almost matching the 4-approximation algorithm known for the classical setting.

Cite as

Andrés Fielbaum, Ignacio Morales, and José Verschae. A Water-Filling Primal-Dual Algorithm for Approximating Non-Linear Covering Problems. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{fielbaum_et_al:LIPIcs.ICALP.2020.46,
  author =	{Fielbaum, Andr\'{e}s and Morales, Ignacio and Verschae, Jos\'{e}},
  title =	{{A Water-Filling Primal-Dual Algorithm for Approximating Non-Linear Covering Problems}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{46:1--46:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.46},
  URN =		{urn:nbn:de:0030-drops-124531},
  doi =		{10.4230/LIPIcs.ICALP.2020.46},
  annote =	{Keywords: Knapsack-Cover Inequalities, Non-Linear Knapsack-Cover, Primal-Dual, Water-Filling Algorithm}
}
Document
Towards Incremental and Modular Context-Sensitive Analysis

Authors: Isabel Garcia-Contreras, José F. Morales, and Manuel V. Hermenegildo

Published in: OASIcs, Volume 64, Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018)


Abstract
This is an extended abstract of [I. Garcia-Contreras et al., 2018].

Cite as

Isabel Garcia-Contreras, José F. Morales, and Manuel V. Hermenegildo. Towards Incremental and Modular Context-Sensitive Analysis. In Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018). Open Access Series in Informatics (OASIcs), Volume 64, pp. 7:1-7:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{garciacontreras_et_al:OASIcs.ICLP.2018.7,
  author =	{Garcia-Contreras, Isabel and Morales, Jos\'{e} F. and Hermenegildo, Manuel V.},
  title =	{{Towards Incremental and Modular Context-Sensitive Analysis}},
  booktitle =	{Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018)},
  pages =	{7:1--7:2},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-090-3},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{64},
  editor =	{Dal Palu', Alessandro and Tarau, Paul and Saeedloei, Neda and Fodor, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICLP.2018.7},
  URN =		{urn:nbn:de:0030-drops-98735},
  doi =		{10.4230/OASIcs.ICLP.2018.7},
  annote =	{Keywords: Program Analysis, (Constraint) Logic Programming, Abstract Interpretation, Fixpoint Algorithms, Incremental Analysis, Modular Analysis}
}
Document
Towards Static Performance Guarantees for Programs with Run-Time Checks

Authors: Maximiliano Klemen, Nataliia Stulova, Pedro Lopez-Garcia, José F. Morales, and Manuel V. Hermenegildo

Published in: OASIcs, Volume 64, Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018)


Abstract
This document is an extended abstract of the Technical Report CLIP-1/2018.0.

Cite as

Maximiliano Klemen, Nataliia Stulova, Pedro Lopez-Garcia, José F. Morales, and Manuel V. Hermenegildo. Towards Static Performance Guarantees for Programs with Run-Time Checks. In Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018). Open Access Series in Informatics (OASIcs), Volume 64, pp. 10:1-10:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{klemen_et_al:OASIcs.ICLP.2018.10,
  author =	{Klemen, Maximiliano and Stulova, Nataliia and Lopez-Garcia, Pedro and Morales, Jos\'{e} F. and Hermenegildo, Manuel V.},
  title =	{{Towards Static Performance Guarantees for Programs with Run-Time Checks}},
  booktitle =	{Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018)},
  pages =	{10:1--10:2},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-090-3},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{64},
  editor =	{Dal Palu', Alessandro and Tarau, Paul and Saeedloei, Neda and Fodor, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICLP.2018.10},
  URN =		{urn:nbn:de:0030-drops-98765},
  doi =		{10.4230/OASIcs.ICLP.2018.10},
  annote =	{Keywords: Run-time Checks, Assertions, Abstract Interpretation, Resource Usage Analysis}
}
Document
Towards Run-time Checks Simplification via Term Hiding

Authors: Nataliia Stulova, Jose F. Morales, and Manuel V. Hermenegildo

Published in: OASIcs, Volume 58, Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)


Abstract
One of the most attractive features of untyped languages for programmers is the flexibility in term creation and manipulation. However, with such power comes the responsibility of ensuring correctness of operations. A solution is adding run-time checks to the program via assertions, but this can introduce overheads that are in many cases impractical. While such overheads can be greatly reduced with static analysis, the gains depend strongly on the quality of the information inferred. Reusable libraries, i.e., library modules that are pre-compiled independently of the client, pose special challenges in this context. We propose a relaxed form of atom-based module system (which hides only a selected set of functor symbols but still provides a strict mechanism to prevent breaking visibility rules across modules) that can enrich significantly the shape information that can be inferred in reusable modular programs. We also propose an improved run-time checking approach that takes advantage of the proposed mechanisms to achieve large reductions in overhead, closer to those of static languages even in the reusable-library context. While the approach is general and system-independent, we present it for concreteness in the context of the Ciao assertion language and combined static/dynamic checking framework. Our method maintains full expressiveness of the checks in this context. Contrary to other approaches it does not introduce the need to switch the language to (static) type systems, which is known to change the semantics in languages like Prolog. We also study the approach experimentally and evaluate the overhead reduction achieved in the run-time checks.

Cite as

Nataliia Stulova, Jose F. Morales, and Manuel V. Hermenegildo. Towards Run-time Checks Simplification via Term Hiding. In Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017). Open Access Series in Informatics (OASIcs), Volume 58, pp. 9:1-9:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{stulova_et_al:OASIcs.ICLP.2017.9,
  author =	{Stulova, Nataliia and Morales, Jose F. and Hermenegildo, Manuel V.},
  title =	{{Towards Run-time Checks Simplification via Term Hiding}},
  booktitle =	{Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)},
  pages =	{9:1--9:3},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-058-3},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{58},
  editor =	{Rocha, Ricardo and Son, Tran Cao and Mears, Christopher and Saeedloei, Neda},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICLP.2017.9},
  URN =		{urn:nbn:de:0030-drops-84601},
  doi =		{10.4230/OASIcs.ICLP.2017.9},
  annote =	{Keywords: Module Systems, Implementation, Run-time Checking, Assertion-based Debugging and Validation, Static Analysis}
}
  • Refine by Author
  • 3 Hermenegildo, Manuel V.
  • 2 Morales, José F.
  • 2 Stulova, Nataliia
  • 1 Fielbaum, Andrés
  • 1 Garcia-Contreras, Isabel
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Invariants
  • 2 Theory of computation → Pre- and post-conditions
  • 2 Theory of computation → Program analysis
  • 2 Theory of computation → Program semantics
  • 1 Mathematics of computing → Discrete optimization
  • Show More...

  • Refine by Keyword
  • 2 Abstract Interpretation
  • 1 (Constraint) Logic Programming
  • 1 Assertion-based Debugging and Validation
  • 1 Assertions
  • 1 Fixpoint Algorithms
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 3 2018
  • 1 2020

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