DROPS

Document

DOI: 10.4230/LIPIcs.CP.2022.33

Large Neighborhood Search for Robust Solutions for Constraint Satisfaction Problems with Ordered Domains

Authors: Jheisson López, Alejandro Arbelaez, and Laura Climent

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract

Often, real-world Constraint Satisfaction Problems (CSPs) are subject to uncertainty/dynamism not known in advance. Some techniques in the literature offer robust solutions for CSPs. Here, we analyze a previous exact/complete approach from the state-of-the-art that focuses on CSPs with ordered domains and dynamic bounds. However, this approach has low performance in large-scale CSPs. For this reason, in this paper, we present an inexact/incomplete approach that is faster at finding robust solutions for large-scale CSPs. It is useful when the computation time available for finding a solution is limited and/or in situations where a new one must be re-computed online because the dynamism invalidated the original one. Specifically, we present a Large Neighbourhood Search (LNS) algorithm combined with Constraint Programming (CP) and Branch-and-bound (B&B) that searches for robust solutions. We also present a robust-value selection heuristic that guides the search toward more promising branches. We evaluate our approach with large-scale CSPs instances, including the case study of scheduling problems. The evaluation shows a considerable improvement in the robustness of the solutions achieved by our algorithm for large-scale CSPs.

Cite as

Jheisson López, Alejandro Arbelaez, and Laura Climent. Large Neighborhood Search for Robust Solutions for Constraint Satisfaction Problems with Ordered Domains. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lopez_et_al:LIPIcs.CP.2022.33,
  author =	{L\'{o}pez, Jheisson and Arbelaez, Alejandro and Climent, Laura},
  title =	{{Large Neighborhood Search for Robust Solutions for Constraint Satisfaction Problems with Ordered Domains}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.33},
  URN =		{urn:nbn:de:0030-drops-166625},
  doi =		{10.4230/LIPIcs.CP.2022.33},
  annote =	{Keywords: Constraint Programming, Large Neighbourhood Search, Robust Solutions}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2022.30

A Structural Investigation of the Approximability of Polynomial-Time Problems

Authors: Karl Bringmann, Alejandro Cassis, Nick Fischer, and Marvin Künnemann

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract

An extensive research effort targets optimal (in)approximability results for various NP-hard optimization problems. Notably, the works of (Creignou'95) as well as (Khanna, Sudan, Trevisan, Williamson'00) establish a tight characterization of a large subclass of MaxSNP, namely Boolean MaxCSPs and further variants, in terms of their polynomial-time approximability. Can we obtain similarly encompassing characterizations for classes of polynomial-time optimization problems? To this end, we initiate the systematic study of a recently introduced polynomial-time analogue of MaxSNP, which includes a large number of well-studied problems (including Nearest and Furthest Neighbor in the Hamming metric, Maximum Inner Product, optimization variants of k-XOR and Maximum k-Cover). Specifically, for each k, MaxSP_k denotes the class of O(m^k)-time problems of the form max_{x_1,… , x_k} #{y : ϕ(x_1,… ,x_k,y)} where ϕ is a quantifier-free first-order property and m denotes the size of the relational structure. Assuming central hypotheses about clique detection in hypergraphs and exact Max-3-SAT}, we show that for any MaxSP_k problem definable by a quantifier-free m-edge graph formula φ, the best possible approximation guarantee in faster-than-exhaustive-search time O(m^{k-δ})falls into one of four categories: - optimizable to exactness in time O(m^{k-δ}), - an (inefficient) approximation scheme, i.e., a (1+ε)-approximation in time O(m^{k-f(ε)}), - a (fixed) constant-factor approximation in time O(m^{k-δ}), or - a nm^ε-approximation in time O(m^{k-f(ε)}). We obtain an almost complete characterization of these regimes, for MaxSP_k as well as for an analogously defined minimization class MinSP_k. As our main technical contribution, we show how to rule out the existence of approximation schemes for a large class of problems admitting constant-factor approximations, under a hypothesis for exact Sparse Max-3-SAT algorithms posed by (Alman, Vassilevska Williams'20). As general trends for the problems we consider, we observe: (1) Exact optimizability has a simple algebraic characterization, (2) only few maximization problems do not admit a constant-factor approximation; these do not even have a subpolynomial-factor approximation, and (3) constant-factor approximation of minimization problems is equivalent to deciding whether the optimum is equal to 0.

Cite as

Karl Bringmann, Alejandro Cassis, Nick Fischer, and Marvin Künnemann. A Structural Investigation of the Approximability of Polynomial-Time Problems. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 30:1-30:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.ICALP.2022.30,
  author =	{Bringmann, Karl and Cassis, Alejandro and Fischer, Nick and K\"{u}nnemann, Marvin},
  title =	{{A Structural Investigation of the Approximability of Polynomial-Time Problems}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{30:1--30:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.30},
  URN =		{urn:nbn:de:0030-drops-163713},
  doi =		{10.4230/LIPIcs.ICALP.2022.30},
  annote =	{Keywords: Classification Theorems, Hardness of Approximation in P, Fine-grained Complexity Theory}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2022.31

Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution

Authors: Karl Bringmann and Alejandro Cassis

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract

We present new exact and approximation algorithms for 0-1-Knapsack and Unbounded Knapsack: - Exact Algorithm for 0-1-Knapsack: 0-1-Knapsack has known algorithms running in time Õ(n + min{n ⋅ OPT, n ⋅ W, OPT², W²}) [Bellman '57], where n is the number of items, W is the weight budget, and OPT is the optimal profit. We present an algorithm running in time Õ(n + (W + OPT)^{1.5}). This improves the running time in case n,W,OPT are roughly equal. - Exact Algorithm for Unbounded Knapsack: Unbounded Knapsack has known algorithms running in time Õ(n + min{n ⋅ p_max, n ⋅ w_max, p_max², w_max²}) [Axiotis, Tzamos '19, Jansen, Rohwedder '19, Chan, He '22], where n is the number of items, w_{max} is the largest weight of any item, and p_max is the largest profit of any item. We present an algorithm running in time Õ(n + (p_max + w_max)^{1.5}), giving a similar improvement as for 0-1-Knapsack. - Approximating Unbounded Knapsack with Resource Augmentation: Unbounded Knapsack has a known FPTAS with running time Õ(min{n/ε, n + 1/ε²}) [Jansen, Kraft '18]. We study weak approximation algorithms, which approximate the optimal profit but are allowed to overshoot the weight constraint (i.e. resource augmentation). We present the first approximation scheme for Unbounded Knapsack in this setting, achieving running time Õ(n + 1/ε^{1.5}). Along the way, we also give a simpler FPTAS with lower order improvement in the standard setting. For all of these problem settings the previously known results had matching conditional lower bounds. We avoid these lower bounds in the approximation setting by allowing resource augmentation, and in the exact setting by analyzing the time complexity in terms of weight and profit parameters (instead of only weight or only profit parameters). Our algorithms can be seen as reductions to Min-Plus-Convolution on monotone sequences with bounded entries. These structured instances of Min-Plus-Convolution can be solved in time O(n^1.5) [Chi, Duan, Xie, Zhang '22] (in contrast to the conjectured n^{2-o(1)} lower bound for the general case). We complement our results by showing reductions in the opposite direction, that is, we show that achieving our results with the constant 1.5 replaced by any constant < 2 implies subquadratic algorithms for Min-Plus-Convolution on monotone sequences with bounded entries.

Cite as

Karl Bringmann and Alejandro Cassis. Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 31:1-31:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.ICALP.2022.31,
  author =	{Bringmann, Karl and Cassis, Alejandro},
  title =	{{Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{31:1--31:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.31},
  URN =		{urn:nbn:de:0030-drops-163727},
  doi =		{10.4230/LIPIcs.ICALP.2022.31},
  annote =	{Keywords: Knapsack, Approximation Schemes, Fine-Grained Complexity, Min-Plus Convolution}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2022.32

Improved Sublinear-Time Edit Distance for Preprocessed Strings

Authors: Karl Bringmann, Alejandro Cassis, Nick Fischer, and Vasileios Nakos

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract

We study the problem of approximating the edit distance of two strings in sublinear time, in a setting where one or both string(s) are preprocessed, as initiated by Goldenberg, Rubinstein, Saha (STOC '20). Specifically, in the (k, K)-gap edit distance problem, the goal is to distinguish whether the edit distance of two strings is at most k or at least K. We obtain the following results: - After preprocessing one string in time n^{1+o(1)}, we can solve (k, k ⋅ n^o(1))-gap-gap edit distance in time (n/k + k) ⋅ n^o(1). - After preprocessing both strings separately in time n^{1+o(1)}, we can solve (k, k ⋅ n^o(1))-gap edit distance in time kn^o(1). Both results improve upon some previously best known result, with respect to either the gap or the query time or the preprocessing time. Our algorithms build on the framework by Andoni, Krauthgamer and Onak (FOCS '10) and the recent sublinear-time algorithm by Bringmann, Cassis, Fischer and Nakos (STOC '22). We replace many complicated parts in their algorithm by faster and simpler solutions which exploit the preprocessing.

Cite as

Karl Bringmann, Alejandro Cassis, Nick Fischer, and Vasileios Nakos. Improved Sublinear-Time Edit Distance for Preprocessed Strings. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 32:1-32:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.ICALP.2022.32,
  author =	{Bringmann, Karl and Cassis, Alejandro and Fischer, Nick and Nakos, Vasileios},
  title =	{{Improved Sublinear-Time Edit Distance for Preprocessed Strings}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{32:1--32:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.32},
  URN =		{urn:nbn:de:0030-drops-163734},
  doi =		{10.4230/LIPIcs.ICALP.2022.32},
  annote =	{Keywords: Edit Distance, Property Testing, Preprocessing, Precision Sampling}
}

Document

DOI: 10.4230/LIPIcs.IPEC.2021.20

Dynamic Data Structures for Timed Automata Acceptance

Authors: Alejandro Grez, Filip Mazowiecki, Michał Pilipczuk, Gabriele Puppis, and Cristian Riveros

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract

We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so through the lenses of parameterized dynamic data structures: we assume that the automaton is fixed and its size is the parameter, while the input word is revealed as in a stream, one symbol at a time following the natural order on positions. The goal is to design a dynamic data structure that can be efficiently updated upon revealing the next symbol, while maintaining the answer to the query on whether the word consisting of symbols revealed so far is accepted by the automaton. We provide complexity bounds for this dynamic acceptance problem for timed automata that process symbols interleaved with time spans. The main contribution is a dynamic data structure that maintains acceptance of a fixed one-clock timed automaton 𝒜 with amortized update time 2^{𝒪(|𝒜|)} per input symbol.

Cite as

Alejandro Grez, Filip Mazowiecki, Michał Pilipczuk, Gabriele Puppis, and Cristian Riveros. Dynamic Data Structures for Timed Automata Acceptance. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{grez_et_al:LIPIcs.IPEC.2021.20,
  author =	{Grez, Alejandro and Mazowiecki, Filip and Pilipczuk, Micha{\l} and Puppis, Gabriele and Riveros, Cristian},
  title =	{{Dynamic Data Structures for Timed Automata Acceptance}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.20},
  URN =		{urn:nbn:de:0030-drops-154037},
  doi =		{10.4230/LIPIcs.IPEC.2021.20},
  annote =	{Keywords: timed automata, data stream, dynamic data structure}
}

Document

DOI: 10.4230/DagRep.6.3.1

Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 16101)

Authors: Alejandro Lopez-Ortiz, Ulrich Carsten Meyer, Markus E. Nebel, and Robert Sedgewick

Published in: Dagstuhl Reports, Volume 6, Issue 3 (2016)

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 16101 "Data Structures and Advanced Models of Computation on Big Data". In today's computing environment vast amounts of data are processed, exchanged and analyzed. The manner in which information is stored profoundly influences the efficiency of these operations over the data. In spite of the maturity of the field many data structuring problems are still open, while new ones arise due to technological advances. The seminar covered both recent advances in the "classical" data structuring topics as well as new models of computation adapted to modern architectures, scientific studies that reveal the need for such models, applications where large data sets play a central role, modern computing platforms for very large data, and new data structures for large data in modern architectures. The extended abstracts included in this report contain both recent state of the art advances and lay the foundation for new directions within data structures research.

Cite as

Alejandro Lopez-Ortiz, Ulrich Carsten Meyer, Markus E. Nebel, and Robert Sedgewick. Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 16101). In Dagstuhl Reports, Volume 6, Issue 3, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{lopezortiz_et_al:DagRep.6.3.1,
  author =	{Lopez-Ortiz, Alejandro and Meyer, Ulrich Carsten and Nebel, Markus E. and Sedgewick, Robert},
  title =	{{Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 16101)}},
  pages =	{1--23},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{3},
  editor =	{Lopez-Ortiz, Alejandro and Meyer, Ulrich Carsten and Nebel, Markus E. and Sedgewick, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.3.1},
  URN =		{urn:nbn:de:0030-drops-61457},
  doi =		{10.4230/DagRep.6.3.1},
  annote =	{Keywords: algorithms, big data, cloud services, data structures, external memory methods, information theory, large data sets, streaming, web-scale}
}

Document

DOI: 10.4230/LIPIcs.STACS.2015.636

Paid Exchanges are Worth the Price

Authors: Alejandro López-Ortiz, Marc P. Renault, and Adi Rosén

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract

We consider the list update problem as defined in the seminal work on competitive analysis by Sleator and Tarjan [12]. In this problem, a sequence of requests, consisting of items to access in a linked list, is given. After an item is accessed it can be moved to any position forward in the list at no cost (free exchange), and, at any time, any two adjacent items can be swapped at a cost of 1 (paid exchange). The cost to access an item is its current position in the list. The goal is to dynamically rearrange the list so as to minimize the total cost (accrued from accesses and exchanges) over the request sequence. We show a lower bound of 12/11 on the worst-case ratio between the performance of an (offline) optimal algorithm that can only perform free exchanges and that of an (offline) optimal algorithm that can perform both paid and free exchanges. This answers an outstanding question that has been open since 1996 [10].

Cite as

Alejandro López-Ortiz, Marc P. Renault, and Adi Rosén. Paid Exchanges are Worth the Price. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 636-648, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{lopezortiz_et_al:LIPIcs.STACS.2015.636,
  author =	{L\'{o}pez-Ortiz, Alejandro and Renault, Marc P. and Ros\'{e}n, Adi},
  title =	{{Paid Exchanges are Worth the Price}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{636--648},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.636},
  URN =		{urn:nbn:de:0030-drops-49476},
  doi =		{10.4230/LIPIcs.STACS.2015.636},
  annote =	{Keywords: list update problem, online computation, online algorithms, competitive analysis, lower bounds}
}

Document

DOI: 10.4230/DagRep.4.2.129

Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 14091)

Authors: Alejandro López-Ortiz, Ulrich Carsten Meyer, and Robert Sedgewick

Published in: Dagstuhl Reports, Volume 4, Issue 2 (2014)

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 14091 "Data Structures and Advanced Models of Computation on Big Data". In today's computing environment vast amounts of data are processed, exchanged and analyzed. The manner in which information is stored profoundly influences the efficiency of these operations over the data. In spite of the maturity of the field many data structuring problems are still open, while new ones arise due to technological advances. The seminar covered both recent advances in the "classical" data structuring topics as well as new models of computation adapted to modern architectures, scientific studies that reveal the need for such models, applications where large data sets play a central role, modern computing platforms for very large data, and new data structures for large data in modern architectures. The extended abstracts included in this report contain both recent state of the art advances and lay the foundation for new directions within data structures research.

Cite as

Alejandro López-Ortiz, Ulrich Carsten Meyer, and Robert Sedgewick. Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 14091). In Dagstuhl Reports, Volume 4, Issue 2, pp. 129-149, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{lopezortiz_et_al:DagRep.4.2.129,
  author =	{L\'{o}pez-Ortiz, Alejandro and Meyer, Ulrich Carsten and Sedgewick, Robert},
  title =	{{Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 14091)}},
  pages =	{129--149},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{2},
  editor =	{L\'{o}pez-Ortiz, Alejandro and Meyer, Ulrich Carsten and Sedgewick, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.2.129},
  URN =		{urn:nbn:de:0030-drops-45489},
  doi =		{10.4230/DagRep.4.2.129},
  annote =	{Keywords: data structures, big data, models of computation, I/O Model, sorting, quicksort, graph algorithms, hashing, compression, succinct data structures, trajectories, text search, GPU algorithms, MapReduce}
}

Document

DOI: 10.4230/LIPIcs.STACS.2014.174

Online Bin Packing with Advice

Authors: Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract

We consider the online bin packing problem under the advice complexity model where the "online constraint" is relaxed and an algorithm receives partial information about the future requests. We provide tight upper and lower bounds for the amount of advice an algorithm needs to achieve an optimal packing. We also introduce an algorithm that, when provided with log(n)+o(log(n)) bits of advice, achieves a competitive ratio of 3/2 for the general problem. This algorithm is simple and is expected to find real-world applications. We introduce another algorithm that receives 2n+o(n) bits of advice and achieves a competitive ratio of 4/3+e. Finally, we provide a lower bound argument that implies that advice of linear size is required for an algorithm to achieve a competitive ratio better than 9/8.

Cite as

Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz. Online Bin Packing with Advice. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 174-186, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{boyar_et_al:LIPIcs.STACS.2014.174,
  author =	{Boyar, Joan and Kamali, Shahin and Larsen, Kim S. and L\'{o}pez-Ortiz, Alejandro},
  title =	{{Online Bin Packing with Advice}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{174--186},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.174},
  URN =		{urn:nbn:de:0030-drops-44565},
  doi =		{10.4230/LIPIcs.STACS.2014.174},
  annote =	{Keywords: online algorithms, advice complexity, bin packing}
}

Document

DOI: 10.4230/LIPIcs.STACS.2011.380

A Fast Algorithm for Multi-Machine Scheduling Problems with Jobs of Equal Processing Times

Authors: Alejandro Lopez-Ortiz and Claude-Guy Quimper

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract

Consider the problem of scheduling a set of tasks of length p without preemption on $m$ identical machines with given release and deadline times. We present a new algorithm for computing the schedule with minimal completion times and makespan. The algorithm has time complexity O(min(1,p/m)n^2) which improves substantially over the best known algorithm with complexity O(mn^2).

Cite as

Alejandro Lopez-Ortiz and Claude-Guy Quimper. A Fast Algorithm for Multi-Machine Scheduling Problems with Jobs of Equal Processing Times. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 380-391, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{lopezortiz_et_al:LIPIcs.STACS.2011.380,
  author =	{Lopez-Ortiz, Alejandro and Quimper, Claude-Guy},
  title =	{{A Fast Algorithm for Multi-Machine Scheduling Problems with Jobs of Equal Processing Times}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{380--391},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.380},
  URN =		{urn:nbn:de:0030-drops-30282},
  doi =		{10.4230/LIPIcs.STACS.2011.380},
  annote =	{Keywords: Scheduling}
}

Document

DOI: 10.4230/DagSemProc.09171.1

09171 Abstracts Collection – Adaptive, Output Sensitive, Online and Parameterized Algorithms

Authors: Jérémy Barbay, Rolf Klein, Alejandro López-Ortiz, and Rolf Niedermeier

Published in: Dagstuhl Seminar Proceedings, Volume 9171, Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)

Abstract

From 19.01. to 24.04.2009, the Dagstuhl Seminar 09171 ``Adaptive, Output Sensitive, Online and Parameterized Algorithms '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Jérémy Barbay, Rolf Klein, Alejandro López-Ortiz, and Rolf Niedermeier. 09171 Abstracts Collection – Adaptive, Output Sensitive, Online and Parameterized Algorithms. In Adaptive, Output Sensitive, Online and Parameterized Algorithms. Dagstuhl Seminar Proceedings, Volume 9171, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{barbay_et_al:DagSemProc.09171.1,
  author =	{Barbay, J\'{e}r\'{e}my and Klein, Rolf and L\'{o}pez-Ortiz, Alejandro and Niedermeier, Rolf},
  title =	{{09171 Abstracts Collection  – Adaptive, Output Sensitive, Online and Parameterized Algorithms}},
  booktitle =	{Adaptive, Output Sensitive, Online and Parameterized Algorithms},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9171},
  editor =	{J\'{e}r\'{e}my Barbay and Rolf Klein and Alejandro Ortiz-L\'{o}pez and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09171.1},
  URN =		{urn:nbn:de:0030-drops-21228},
  doi =		{10.4230/DagSemProc.09171.1},
  annote =	{Keywords: Adaptive analysis, instance optimal algoritms, fixed parameter tractable, output sensitive algorithms}
}

Document

DOI: 10.4230/DagSemProc.09171.2

09171 Executive Summary – Adaptive, Output Sensitive, Online and Parameterized Algorithms

Authors: Jérémy Barbay, Rolf Klein, Alejandro López-Ortiz, and Rolf Niedermeier

Published in: Dagstuhl Seminar Proceedings, Volume 9171, Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)

Abstract

Traditionally the analysis of algorithms measures the complexity of a problem or algorithm in terms of the worst-case behavior over all inputs of a given size. However, in certain cases an improved algorithm can be obtained by considering a finer partition of the input space. As this idea has been independently rediscovered in many areas, the workshop gathered participants from different fields in order to explore the impact and the limits of this technique, in the hope to spring new collaboration and to seed the unification of the technique.

Cite as

Jérémy Barbay, Rolf Klein, Alejandro López-Ortiz, and Rolf Niedermeier. 09171 Executive Summary – Adaptive, Output Sensitive, Online and Parameterized Algorithms. In Adaptive, Output Sensitive, Online and Parameterized Algorithms. Dagstuhl Seminar Proceedings, Volume 9171, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{barbay_et_al:DagSemProc.09171.2,
  author =	{Barbay, J\'{e}r\'{e}my and Klein, Rolf and L\'{o}pez-Ortiz, Alejandro and Niedermeier, Rolf},
  title =	{{09171 Executive Summary – Adaptive, Output Sensitive, Online and Parameterized Algorithms}},
  booktitle =	{Adaptive, Output Sensitive, Online and Parameterized Algorithms},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9171},
  editor =	{J\'{e}r\'{e}my Barbay and Rolf Klein and Alejandro Ortiz-L\'{o}pez and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09171.2},
  URN =		{urn:nbn:de:0030-drops-21207},
  doi =		{10.4230/DagSemProc.09171.2},
  annote =	{Keywords: Adaptive analysis, instance optimal algorithms, fixed parameter tractable, output sensitive algorithms}
}

Document

DOI: 10.4230/DagSemProc.09171.3

Parameterized Analysis of Online Steiner Tree Problems

Authors: Spyros Angelopoulos

Published in: Dagstuhl Seminar Proceedings, Volume 9171, Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)

Abstract

Steiner tree problems occupy a central place in both areas of approximation and on-line algorithms. Many variants have been studied from the point of view of competitive analysis, and for several of these variants tight bounds are known. However, in several cases, worst-case analysis is overly pessimistic, which fails to explain the relative performance of algorithms. We show how adaptive analysis can help resolve this problem. As case studies, we consider the Steiner tree problem in directed graphs, and the Priority Steiner tree problem.

Cite as

Spyros Angelopoulos. Parameterized Analysis of Online Steiner Tree Problems. In Adaptive, Output Sensitive, Online and Parameterized Algorithms. Dagstuhl Seminar Proceedings, Volume 9171, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{angelopoulos:DagSemProc.09171.3,
  author =	{Angelopoulos, Spyros},
  title =	{{Parameterized Analysis of Online Steiner Tree Problems}},
  booktitle =	{Adaptive, Output Sensitive, Online and Parameterized Algorithms},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9171},
  editor =	{J\'{e}r\'{e}my Barbay and Rolf Klein and Alejandro Ortiz-L\'{o}pez and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09171.3},
  URN =		{urn:nbn:de:0030-drops-21210},
  doi =		{10.4230/DagSemProc.09171.3},
  annote =	{Keywords: Online algorithms, Steiner tree problems, adaptive and parameteried analysis}
}

Document

DOI: 10.4230/DagSemProc.08081.3

Optimal Speedup on a Low-Degree Multi-Core Parallel Architecture (LoPRAM)

Authors: Alejandro Lopez-Ortiz, Reza Dorrigiv, and Alejandro Salinger

Published in: Dagstuhl Seminar Proceedings, Volume 8081, Data Structures (2008)

Abstract

We propose a new model with small degreee of parallelism that reflects current and future multicore architectures in practice. The model is based on the PRAM architecture and hence it inherits many of its interesting theoretical properties. The key observations and differences are that the degree of parallelism (i.e. number of processors or cores) is bounded by O(log n), the synchronization model is looser and the use of parallelism is at a higher level unless explicitly specified otherwise. Surprisingly, these three rather minor variants result in a model in which obtaining work optimal algorithms is significantly easier than for the PRAM. The new model is called Low-degree PRAM or LoPRAM for short. Lastly we observe that there are thresholds in complexity of programming at p=O(log n) and p=O(sqrt(n)) and provide references for specific problems for which this threshold has been formally proven.

Cite as

Alejandro Lopez-Ortiz, Reza Dorrigiv, and Alejandro Salinger. Optimal Speedup on a Low-Degree Multi-Core Parallel Architecture (LoPRAM). In Data Structures. Dagstuhl Seminar Proceedings, Volume 8081, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{lopezortiz_et_al:DagSemProc.08081.3,
  author =	{Lopez-Ortiz, Alejandro and Dorrigiv, Reza and Salinger, Alejandro},
  title =	{{Optimal Speedup on a Low-Degree Multi-Core Parallel Architecture (LoPRAM)}},
  booktitle =	{Data Structures},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8081},
  editor =	{Lars Arge and Robert Sedgewick and Raimund Seidel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08081.3},
  URN =		{urn:nbn:de:0030-drops-15315},
  doi =		{10.4230/DagSemProc.08081.3},
  annote =	{Keywords: PRAM, multicore architectures, parallelism, algorithms, dynamic programming, divide and conquer}
}

Document

DOI: 10.4230/DagSemProc.06421.1

06421 Abstracts Collection – Robot Navigation

Authors: Sándor Fekete, Rudolf Fleischer, Rolf Klein, and Alejandro Lopez-Ortiz

Published in: Dagstuhl Seminar Proceedings, Volume 6421, Robot Navigation (2007)

Abstract

From 15.10.06 to 20.10.06, the Dagstuhl Seminar 06421 ``Robot Navigation''generate automatically was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Sándor Fekete, Rudolf Fleischer, Rolf Klein, and Alejandro Lopez-Ortiz. 06421 Abstracts Collection – Robot Navigation. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.06421.1,
  author =	{Fekete, S\'{a}ndor and Fleischer, Rudolf and Klein, Rolf and Lopez-Ortiz, Alejandro},
  title =	{{06421 Abstracts Collection – Robot Navigation}},
  booktitle =	{Robot Navigation},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.1},
  URN =		{urn:nbn:de:0030-drops-8890},
  doi =		{10.4230/DagSemProc.06421.1},
  annote =	{Keywords: Motion planning, robotics, computational geometry, online algorithms}
}

22 Search Results for "L�pez-Ortiz, Alejandro"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message