125 Search Results for "Portier, Natacha"

Volume

LIPIcs, Volume 25

31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

STACS 2014, March 5-8, 2014, Lyon, France

Editors: Ernst W. Mayr and Natacha Portier

Volume

LIPIcs, Volume 20

30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

STACS 2013, February 27 to March 2, 2013, Kiel, Germany

Editors: Natacha Portier and Thomas Wilke

Document
Complete Volume
DOI: 10.4230/LIPIcs.STACS.2014
LIPIcs, Volume 25, STACS'14, Complete Volume

Authors: Ernst W. Mayr and Natacha Portier

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

Abstract
LIPIcs, Volume 25, STACS'14, Complete Volume
Cite as

31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Proceedings{mayr_et_al:LIPIcs.STACS.2014,
  title =	{{LIPIcs, Volume 25, STACS'14, Complete Volume}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  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},
  URN =		{urn:nbn:de:0030-drops-45104},
  doi =		{10.4230/LIPIcs.STACS.2014},
  annote =	{Keywords: Models of Computation, Nonnumerical Algorithms and Problems, Mathematical Logic, Formal Languages, Combinatorics, Graph Theory}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.STACS.2014.i
Frontmatter, Table of Contents, Preface, Conference Organization

Authors: Ernst W. Mayr and Natacha Portier

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

Abstract
Frontmatter, Table of Contents, Preface, Conference Organization
Cite as

31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. i-xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{mayr_et_al:LIPIcs.STACS.2014.i,
  author =	{Mayr, Ernst W. and Portier, Natacha},
  title =	{{Frontmatter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{i--xvi},
  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.i},
  URN =		{urn:nbn:de:0030-drops-44435},
  doi =		{10.4230/LIPIcs.STACS.2014.i},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2014.1
Keeping a Crowd Safe: On the Complexity of Parameterized Verification (Invited Talk)

Authors: Javier Esparza

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

Abstract
We survey some results on the automatic verification of parameterized programs without identities. These are systems composed of arbitrarily many components, all of them running exactly the same finite-state program. We discuss the complexity of deciding that no component reaches an unsafe state. The note is addressed at theoretical computer scientists in general.
Cite as

Javier Esparza. Keeping a Crowd Safe: On the Complexity of Parameterized Verification (Invited Talk). In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{esparza:LIPIcs.STACS.2014.1,
  author =	{Esparza, Javier},
  title =	{{Keeping a Crowd Safe: On the Complexity of Parameterized Verification}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{1--10},
  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.1},
  URN =		{urn:nbn:de:0030-drops-44985},
  doi =		{10.4230/LIPIcs.STACS.2014.1},
  annote =	{Keywords: Parameterized verification, automata theory}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2014.11
Semi-algebraic geometry in computational game theory - a consumer's perspective (Invited Talk)

Authors: Peter Bro Miltersen

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

Abstract
We survey recent applications of real algebraic and semi-algebraic geometry in (computational) game theory.
Cite as

Peter Bro Miltersen. Semi-algebraic geometry in computational game theory - a consumer's perspective (Invited Talk). In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 11-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{miltersen:LIPIcs.STACS.2014.11,
  author =	{Miltersen, Peter Bro},
  title =	{{Semi-algebraic geometry in computational game theory - a consumer's perspective}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{11--12},
  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.11},
  URN =		{urn:nbn:de:0030-drops-44994},
  doi =		{10.4230/LIPIcs.STACS.2014.11},
  annote =	{Keywords: Real Algebraic Geometry, Computational Game Theory}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2014.13
A glimpse on constant delay enumeration (Invited Talk)

Authors: Luc Segoufin

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

Abstract
We survey some of the recent results about enumerating the answers to queries over a database. We focus on the case where the enumeration is performed with a constant delay between any two consecutive solutions, after a linear time preprocessing. This cannot be always achieved. It requires restricting either the class of queries or the class of databases. We describe here several scenarios when this is possible.
Cite as

Luc Segoufin. A glimpse on constant delay enumeration (Invited Talk). In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 13-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{segoufin:LIPIcs.STACS.2014.13,
  author =	{Segoufin, Luc},
  title =	{{A glimpse on constant delay enumeration}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{13--27},
  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.13},
  URN =		{urn:nbn:de:0030-drops-45001},
  doi =		{10.4230/LIPIcs.STACS.2014.13},
  annote =	{Keywords: Enumeration, constant delay, logic}
}
Document
Tutorial
DOI: 10.4230/LIPIcs.STACS.2014.28
Arithmetic Circuit Complexity (Tutorial)

Authors: Neeraj Kayal

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

Abstract
Arithmetic Circuits compute polynomial functions over their inputs via a sequence of arithmetic operations (additions, subtractions, multiplications, divisions, etc.). This tutorial will give an overview of arithmetic circuit complexity, focusing on the problem of proving lower bounds for arithmetic circuits. In the first part, we begin with a few nontrivial upper bounds - matrix multiplication and the computation of symmetric polynomials. We then motivate some open problems we deal with in arithmetic circuit complexity. We will look at the problem of polynomial identity testing - motivating it by its application to bipartite matching, the problem of learning arithmetic circuits or circuit reconstruction and the problem of proving lower bounds for arithmetic circuits (motivating it via the problem of computing the permanent and the Hamiltonian polynomials). We will also see depth reduction for circuits - the tradeoffs involved (with respect to size) in squashing a circuit into one with smaller depth. In the second part, we will see some classical lower bounds. In particular, we will see lower bounds for monotone arithmetic circuits and multilinear formulas. We then give a very quick overview of approaches being investigated (including geometric complexity theory and tau-conjecture) aiming to prove lower bounds. In the third part, we begin with a warm-up by proving lower bounds for homogeneous depth three circuits. We will then see recent lower bounds for homogeneous depth four circuits and its consequences.
Cite as

Neeraj Kayal. Arithmetic Circuit Complexity (Tutorial). In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, p. 28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{kayal:LIPIcs.STACS.2014.28,
  author =	{Kayal, Neeraj},
  title =	{{Arithmetic Circuit Complexity}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{28--28},
  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.28},
  URN =		{urn:nbn:de:0030-drops-45012},
  doi =		{10.4230/LIPIcs.STACS.2014.28},
  annote =	{Keywords: Circuit complexity, arithmetic circuits, lower bounds, polynomial identity testing}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.29
Submodular Stochastic Probing on Matroids

Authors: Marek Adamczyk, Maxim Sviridenko, and Justin Ward

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

Abstract
In a stochastic probing problem we are given a universe E, where each element e in E is active independently with probability p in [0,1], and only a probe of e can tell us whether it is active or not. On this universe we execute a process that one by one probes elements - if a probed element is active, then we have to include it in the solution, which we gradually construct. Throughout the process we need to obey inner constraints on the set of elements taken into the solution, and outer constraints on the set of all probed elements. This abstract model was presented in [Gupta and Nagaraja, IPCO 2013], and provides a unified view of a number of problems. Thus far all the results in this general framework pertain only to the case in which we are maximizing a linear objective function of the successfully probed elements. In this paper we generalize the stochastic probing problem by considering a monotone submodular objective function. We give a (1-1/e)/(k_in+k_out+1)-approximation algorithm for the case in which we are given k_in greater than 0 matroids as inner constraints and k_out greater than 1 matroids as outer constraints. There are two main ingredients behind this result. First is a previously unpublished stronger bound on the continuous greedy algorithm due to Vondrak. Second is a rounding procedure that also allows us to obtain an improved 1/(k_in+k_out)-approximation for linear objective functions.
Cite as

Marek Adamczyk, Maxim Sviridenko, and Justin Ward. Submodular Stochastic Probing on Matroids. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 29-40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{adamczyk_et_al:LIPIcs.STACS.2014.29,
  author =	{Adamczyk, Marek and Sviridenko, Maxim and Ward, Justin},
  title =	{{Submodular Stochastic Probing on Matroids}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{29--40},
  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.29},
  URN =		{urn:nbn:de:0030-drops-44445},
  doi =		{10.4230/LIPIcs.STACS.2014.29},
  annote =	{Keywords: approximation algorithms, stochastic optimization, submodular optimization, matroids, iterative rounding}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.41
On Symmetric Circuits and Fixed-Point Logics

Authors: Matthew Anderson and Anuj Dawar

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

Abstract
We study properties of relational structures such as graphs that are decided by families of Boolean circuits. Circuits that decide such properties are necessarily invariant to permutations of the elements of the input structures. We focus on families of circuits that are symmetric, i.e., circuits whose invariance is witnessed by automorphisms of the circuit induced by the permutation of the input structure. We show that the expressive power of such families is closely tied to definability in logic. In particular, we show that the queries defined on structures by uniform families of symmetric Boolean circuits with majority gates are exactly those definable in fixed-point logic with counting. This shows that inexpressibility results in the latter logic lead to lower bounds against polynomial-size families of symmetric circuits.
Cite as

Matthew Anderson and Anuj Dawar. On Symmetric Circuits and Fixed-Point Logics. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 41-52, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{anderson_et_al:LIPIcs.STACS.2014.41,
  author =	{Anderson, Matthew and Dawar, Anuj},
  title =	{{On Symmetric Circuits and Fixed-Point Logics}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{41--52},
  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.41},
  URN =		{urn:nbn:de:0030-drops-44455},
  doi =		{10.4230/LIPIcs.STACS.2014.41},
  annote =	{Keywords: symmetric circuit, fixed-point logic, majority, counting, uniformity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.53
Throughput Maximization in the Speed-Scaling Setting

Authors: Eric Angel, Evripidis Bampis, and Vincent Chau

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

Abstract
We are given a set of n jobs and a single processor that can vary its speed dynamically. Each job J_j is characterized by its processing requirement (work) p_j, its release date r_j and its deadline d_j. We are also given a budget of energy E and we study the scheduling problem of maximizing the throughput (i.e. the number of jobs that are completed on time). While the preemptive energy minimization problem has been solved in polynomial time [Yao et al., FOCS'95], the complexity of the problem of maximizing the throughput remained open until now. We answer partially this question by providing a dynamic programming algorithm that solves the problem in pseudo-polynomial time. While our result shows that the problem is not strongly NP-hard, the question of whether the problem can be solved in polynomial time remains a challenging open question. Our algorithm can also be adapted for solving the weighted version of the problem where every job is associated with a weight w_j and the objective is the maximization of the sum of the weights of the jobs that are completed on time.
Cite as

Eric Angel, Evripidis Bampis, and Vincent Chau. Throughput Maximization in the Speed-Scaling Setting. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 53-62, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{angel_et_al:LIPIcs.STACS.2014.53,
  author =	{Angel, Eric and Bampis, Evripidis and Chau, Vincent},
  title =	{{Throughput Maximization in the Speed-Scaling Setting}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{53--62},
  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.53},
  URN =		{urn:nbn:de:0030-drops-44469},
  doi =		{10.4230/LIPIcs.STACS.2014.53},
  annote =	{Keywords: energy efficiency, dynamic speed scaling, offline algorithm, throughput, dynamic programming}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.63
Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules

Authors: Antonios Antoniadis, Neal Barcelo, Mario Consuegra, Peter Kling, Michael Nugent, Kirk Pruhs, and Michele Scquizzato

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

Abstract
We give a polynomial time algorithm to compute an optimal energy and fractional weighted flow trade-off schedule for a speed-scalable processor with discrete speeds. Our algorithm uses a geometric approach that is based on structural properties obtained from a primal-dual formulation of the problem.
Cite as

Antonios Antoniadis, Neal Barcelo, Mario Consuegra, Peter Kling, Michael Nugent, Kirk Pruhs, and Michele Scquizzato. Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 63-74, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.STACS.2014.63,
  author =	{Antoniadis, Antonios and Barcelo, Neal and Consuegra, Mario and Kling, Peter and Nugent, Michael and Pruhs, Kirk and Scquizzato, Michele},
  title =	{{Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{63--74},
  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.63},
  URN =		{urn:nbn:de:0030-drops-44474},
  doi =		{10.4230/LIPIcs.STACS.2014.63},
  annote =	{Keywords: scheduling, flow time, energy efficiency, speed scaling, primal-dual}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.75
Weighted Coloring in Trees

Authors: Julio Araujo, Nicolas Nisse, and Stéphane Pérennes

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

Abstract
A proper coloring of a graph is a partition of its vertex set into stable sets, where each part corresponds to a color. For a vertex-weighted graph, the weight of a color is the maximum weight of its vertices. The weight of a coloring is the sum of the weights of its colors. Guan and Zhu (1997) defined the weighted chromatic number of a vertex-weighted graph G as the smallest weight of a proper coloring of G. If vertices of a graph have weight 1, its weighted chromatic number coincides with its chromatic number. Thus, the problem of computing the weighted chromatic number, a.k.a. Max Coloring Problem, is NP-hard in general graphs. It remains NP-hard in some graph classes as bipartite graphs. Approximation algorithms have been designed in several graph classes, in particular, there exists a PTAS for trees. Surprisingly, the time-complexity of computing this parameter in trees is still open. The Exponential Time Hypothesis (ETH) states that 3-SAT cannot be solved in sub-exponential time. We show that, assuming ETH, the best algorithm to compute the weighted chromatic number of n-node trees has time-complexity n O(log(n)). Our result mainly relies on proving that, when computing an optimal proper weighted coloring of a graph G, it is hard to combine colorings of its connected components.
Cite as

Julio Araujo, Nicolas Nisse, and Stéphane Pérennes. Weighted Coloring in Trees. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 75-86, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{araujo_et_al:LIPIcs.STACS.2014.75,
  author =	{Araujo, Julio and Nisse, Nicolas and P\'{e}rennes, St\'{e}phane},
  title =	{{Weighted Coloring in Trees}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{75--86},
  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.75},
  URN =		{urn:nbn:de:0030-drops-44484},
  doi =		{10.4230/LIPIcs.STACS.2014.75},
  annote =	{Keywords: Weighted Coloring, Max Coloring, Exponential Time Hypothesis, 3-SAT}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.87
Generalized Reordering Buffer Management

Authors: Yossi Azar, Matthias Englert, Iftah Gamzu, and Eytan Kidron

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

Abstract
An instance of the generalized reordering buffer management problem consists of a service station that has k servers, each configured with a color, and a buffer of size b. The station needs to serve an online stream of colored items. Whenever an item arrives, it is stored in the buffer. At any point in time, a currently pending item can be served by switching a server to its color. The objective is to serve all items in a way that minimizes the number of servers color switches. This problem generalizes two well-studied online problems: the paging problem, which is the special case when b=1, and the reordering buffer problem, which is the special case when k=1. In this paper, we develop a randomized online algorithm that obtains a competitive ratio of O(sqrt(b).ln(k)). Note that this result beats the easy deterministic lower bound of k whenever b < k^(2-e). We complement our randomized approach by presenting a deterministic algorithm that attains a competitive ratio of O(min{k^2.ln(b),k.b}). We further demonstrate that if our deterministic algorithm can employ k/(1-d) servers where d is in (0,1), then it achieves a competitive ratio of O(min{ln(b/d^2),b/d}) against an optimal offline adversary that employs k servers.
Cite as

Yossi Azar, Matthias Englert, Iftah Gamzu, and Eytan Kidron. Generalized Reordering Buffer Management. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 87-98, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{azar_et_al:LIPIcs.STACS.2014.87,
  author =	{Azar, Yossi and Englert, Matthias and Gamzu, Iftah and Kidron, Eytan},
  title =	{{Generalized Reordering Buffer Management}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{87--98},
  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.87},
  URN =		{urn:nbn:de:0030-drops-44498},
  doi =		{10.4230/LIPIcs.STACS.2014.87},
  annote =	{Keywords: online algorithms, paging, reordering buffer}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.99
Shapley meets Shapley

Authors: Haris Aziz and Bart de Keijzer

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

Abstract
This paper concerns the analysis of the Shapley value in matching games. Matching games constitute a fundamental class of cooperative games which help understand and model auctions and assignments. In a matching game, the value of a coalition of vertices is the weight of the maximum size matching in the subgraph induced by the coalition. The Shapley value is one of the most important solution concepts in cooperative game theory. After establishing some general insights, we show that the Shapley value of matching games can be computed in polynomial time for some special cases: graphs with maximum degree two, and graphs that have a small modular decomposition into cliques or cocliques (complete k-partite graphs are a notable special case of this). The latter result extends to various other well-known classes of graph-based cooperative games. We continue by showing that computing the Shapley value of unweighted matching games is #P-complete in general. Finally, a fully polynomial-time randomized approximation scheme (FPRAS) is presented. This FPRAS can be considered the best positive result conceivable, in view of the #P-completeness result.
Cite as

Haris Aziz and Bart de Keijzer. Shapley meets Shapley. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 99-111, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{aziz_et_al:LIPIcs.STACS.2014.99,
  author =	{Aziz, Haris and de Keijzer, Bart},
  title =	{{Shapley meets Shapley}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{99--111},
  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.99},
  URN =		{urn:nbn:de:0030-drops-44504},
  doi =		{10.4230/LIPIcs.STACS.2014.99},
  annote =	{Keywords: matching games, Shapley, counting complexity}
}
  • Refine by Author
  • 7 Portier, Natacha
  • 5 Pilipczuk, Michal
  • 4 Fomin, Fedor V.
  • 3 Marx, Dániel
  • 3 Villanger, Yngve
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 4 Pattern matching
  • 4 approximation algorithms
  • 4 parameterized complexity
  • 3 Approximation Algorithms
  • 3 automata theory
  • Show More...

  • Refine by Type
  • 123 document
  • 2 volume

  • Refine by Publication Year
  • 62 2013
  • 61 2014
  • 2 2011

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