17 Search Results for "Larsen, Kim S."

Document
DOI: 10.4230/LIPIcs.SWAT.2022.20
Online Unit Profit Knapsack with Untrusted Predictions

Authors: Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
A variant of the online knapsack problem is considered in the settings of trusted and untrusted predictions. In Unit Profit Knapsack, the items have unit profit, and it is easy to find an optimal solution offline: Pack as many of the smallest items as possible into the knapsack. For Online Unit Profit Knapsack, the competitive ratio is unbounded. In contrast, previous work on online algorithms with untrusted predictions generally studied problems where an online algorithm with a constant competitive ratio is known. The prediction, possibly obtained from a machine learning source, that our algorithm uses is the average size of those smallest items that fit in the knapsack. For the prediction error in this hard online problem, we use the ratio r = a/â where a is the actual value for this average size and â is the prediction. The algorithm presented achieves a competitive ratio of 1/(2r) for r ≥ 1 and r/2 for r ≤ 1. Using an adversary technique, we show that this is optimal in some sense, giving a trade-off in the competitive ratio attainable for different values of r. Note that the result for accurate advice, r = 1, is only 1/2, but we show that no deterministic algorithm knowing the value a can achieve a competitive ratio better than (e-1)/e ≈ 0.6321 and present an algorithm with a matching upper bound. We also show that this latter algorithm attains a competitive ratio of r (e-1)/e for r ≤ 1 and (e-r)/e for 1 ≤ r < e, and no deterministic algorithm can be better for both r < 1 and 1 < r < e.
Cite as

Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen. Online Unit Profit Knapsack with Untrusted Predictions. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{boyar_et_al:LIPIcs.SWAT.2022.20,
  author =	{Boyar, Joan and Favrholdt, Lene M. and Larsen, Kim S.},
  title =	{{Online Unit Profit Knapsack with Untrusted Predictions}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.20},
  URN =		{urn:nbn:de:0030-drops-161800},
  doi =		{10.4230/LIPIcs.SWAT.2022.20},
  annote =	{Keywords: online algorithms, untrusted predictions, knapsack problem, competitive analysis}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.13
Communication Complexity of Pairs of Graph Families with Applications

Authors: Sudeshna Kolay, Fahad Panolan, and Saket Saurabh

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Given a graph G and a pair (\mathcal{F}_1,\mathcal{F}_2) of graph families, the function {\sf GDISJ}_{G,{\cal F}_1,{\cal F}_2} takes as input, two induced subgraphs G_1 and G_2 of G, such that G_1 \in \mathcal{F}_1 and G_2 \in \mathcal{F}_2 and returns 1 if V(G_1)\cap V(G_2)=\emptyset and 0 otherwise. We study the communication complexity of this problem in the two-party model. In particular, we look at pairs of hereditary graph families. We show that the communication complexity of this function, when the two graph families are hereditary, is sublinear if and only if there are finitely many graphs in the intersection of these two families. Then, using concepts from parameterized complexity, we obtain nuanced upper bounds on the communication complexity of GDISJ_G,\cal F_1,\cal F_2. A concept related to communication protocols is that of a (\mathcal{F}_1,\mathcal{F}_2)-separating family of a graph G. A collection \mathcal{F} of subsets of V(G) is called a (\mathcal{F}_1,\mathcal{F}_2)-separating family} for G, if for any two vertex disjoint induced subgraphs G_1\in \mathcal{F}_1,G_2\in \mathcal{F}_2, there is a set F \in \mathcal{F} with V(G_1) \subseteq F and V(G_2) \cap F = \emptyset. Given a graph G on n vertices, for any pair (\mathcal{F}_1,\mathcal{F}_2) of hereditary graph families with sublinear communication complexity for GDISJ_G,\cal F_1,\cal F_2, we give an enumeration algorithm that finds a subexponential sized (\mathcal{F}_1,\mathcal{F}_2)-separating family. In fact, we give an enumeration algorithm that finds a 2^{o(k)}n^{\Oh(1)} sized (\mathcal{F}_1,\mathcal{F}_2)-separating family; where k denotes the size of a minimum sized set S of vertices such that V(G)\setminus S has a bipartition (V_1,V_2) with G[V_1] \in {\cal F}_1 and G[V_2]\in {\cal F}_2. We exhibit a wide range of applications for these separating families, to obtain combinatorial bounds, enumeration algorithms as well as exact and FPT algorithms for several problems.
Cite as

Sudeshna Kolay, Fahad Panolan, and Saket Saurabh. Communication Complexity of Pairs of Graph Families with Applications. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kolay_et_al:LIPIcs.MFCS.2017.13,
  author =	{Kolay, Sudeshna and Panolan, Fahad and Saurabh, Saket},
  title =	{{Communication Complexity of Pairs of Graph Families with Applications}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.13},
  URN =		{urn:nbn:de:0030-drops-80849},
  doi =		{10.4230/LIPIcs.MFCS.2017.13},
  annote =	{Keywords: Communication Complexity, Separating Family, FPT algorithms}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.19
Comparison of Max-Plus Automata and Joint Spectral Radius of Tropical Matrices

Authors: Laure Daviaud, Pierre Guillon, and Glenn Merlet

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Weighted automata over the tropical semiring Zmax are closely related to finitely generated semigroups of matrices over Zmax. In this paper, we use results in automata theory to study two quantities associated with sets of matrices: the joint spectral radius and the ultimate rank. We prove that these two quantities are not computable over the tropical semiring, i.e. there is no algorithm that takes as input a finite set of matrices S and provides as output the joint spectral radius (resp. the ultimate rank) of S. On the other hand, we prove that the joint spectral radius is nevertheless approximable and we exhibit restricted cases in which the joint spectral radius and the ultimate rank are computable. To reach this aim, we study the problem of comparing functions computed by weighted automata over the tropical semiring. This problem is known to be undecidable, and we prove that it remains undecidable in some specific subclasses of automata.
Cite as

Laure Daviaud, Pierre Guillon, and Glenn Merlet. Comparison of Max-Plus Automata and Joint Spectral Radius of Tropical Matrices. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{daviaud_et_al:LIPIcs.MFCS.2017.19,
  author =	{Daviaud, Laure and Guillon, Pierre and Merlet, Glenn},
  title =	{{Comparison of Max-Plus Automata and Joint Spectral Radius of Tropical Matrices}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.19},
  URN =		{urn:nbn:de:0030-drops-81052},
  doi =		{10.4230/LIPIcs.MFCS.2017.19},
  annote =	{Keywords: max-plus automata, max-plus matrices, weighted automata, tropical semiring, joint spectral radius, ultimate rank}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.34
Another Characterization of the Higher K-Trivials

Authors: Paul-Elliot Anglès d'Auriac and Benoit Monin

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
In algorithmic randomness, the class of K-trivial sets has proved itself to be remarkable, due to its numerous different characterizations. We pursue in this paper some work already initiated on K-trivials in the context of higher randomness. In particular we give here another characterization of the non hyperarithmetic higher K-trivial sets.
Cite as

Paul-Elliot Anglès d'Auriac and Benoit Monin. Another Characterization of the Higher K-Trivials. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 34:1-34:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{anglesdauriac_et_al:LIPIcs.MFCS.2017.34,
  author =	{Angl\`{e}s d'Auriac, Paul-Elliot and Monin, Benoit},
  title =	{{Another Characterization of the Higher K-Trivials}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{34:1--34:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.34},
  URN =		{urn:nbn:de:0030-drops-80837},
  doi =		{10.4230/LIPIcs.MFCS.2017.34},
  annote =	{Keywords: Algorithmic randomness, higher computability, K-triviality, effective descriptive set theory, Kolmogorov complexity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.36
Towards a Polynomial Kernel for Directed Feedback Vertex Set

Authors: Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, and M. S. Ramanujan

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
In the Directed Feedback Vertex Set (DFVS) problem, the input is a directed graph D and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every directed cycle of D. DFVS was shown to be fixed-parameter tractable when parameterized by solution size by Chen, Liu, Lu, O'Sullivan and Razgon [JACM 2008]; since then, the existence of a polynomial kernel for this problem has become one of the largest open problems in the area of parameterized algorithmics. In this paper, we study DFVS parameterized by the feedback vertex set number of the underlying undirected graph. We provide two main contributions: a polynomial kernel for this problem on general instances, and a linear kernel for the case where the input digraph is embeddable on a surface of bounded genus.
Cite as

Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, and M. S. Ramanujan. Towards a Polynomial Kernel for Directed Feedback Vertex Set. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bergougnoux_et_al:LIPIcs.MFCS.2017.36,
  author =	{Bergougnoux, Benjamin and Eiben, Eduard and Ganian, Robert and Ordyniak, Sebastian and Ramanujan, M. S.},
  title =	{{Towards a Polynomial Kernel for Directed Feedback Vertex Set}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{36:1--36:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.36},
  URN =		{urn:nbn:de:0030-drops-81126},
  doi =		{10.4230/LIPIcs.MFCS.2017.36},
  annote =	{Keywords: parameterized algorithms, kernelization, (directed) feedback vertex set}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.38
Efficient Identity Testing and Polynomial Factorization in Nonassociative Free Rings

Authors: Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, and S. Raja

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
In this paper we study arithmetic computations in the nonassociative, and noncommutative free polynomial ring F{X}. Prior to this work, nonassociative arithmetic computation was considered by Hrubes, Wigderson, and Yehudayoff, and they showed lower bounds and proved completeness results. We consider Polynomial Identity Testing and Polynomial Factorization in F{X} and show the following results. 1. Given an arithmetic circuit C computing a polynomial f in F{X} of degree d, we give a deterministic polynomial algorithm to decide if f is identically zero. Our result is obtained by a suitable adaptation of the PIT algorithm of Raz and Shpilka for noncommutative ABPs. 2. Given an arithmetic circuit C computing a polynomial f in F{X} of degree d, we give an efficient deterministic algorithm to compute circuits for the irreducible factors of f in polynomial time when F is the field of rationals. Over finite fields of characteristic p, our algorithm runs in time polynomial in input size and p.
Cite as

Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, and S. Raja. Efficient Identity Testing and Polynomial Factorization in Nonassociative Free Rings. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.MFCS.2017.38,
  author =	{Arvind, Vikraman and Datta, Rajit and Mukhopadhyay, Partha and Raja, S.},
  title =	{{Efficient Identity Testing and Polynomial Factorization in  Nonassociative Free Rings}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{38:1--38:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.38},
  URN =		{urn:nbn:de:0030-drops-80690},
  doi =		{10.4230/LIPIcs.MFCS.2017.38},
  annote =	{Keywords: Circuits, Nonassociative, Noncommutative, Polynomial Identity Testing, Factorization}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.60
Fine-Grained Complexity of Rainbow Coloring and its Variants

Authors: Akanksha Agrawal

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Consider a graph G and an edge-coloring c_R:E(G) \rightarrow [k]. A rainbow path between u,v \in V(G) is a path P from u to v such that for all e,e' \in E(P), where e \neq e' we have c_R(e) \neq c_R(e'). In the Rainbow k-Coloring problem we are given a graph G, and the objective is to decide if there exists c_R: E(G) \rightarrow [k] such that for all u,v \in V(G) there is a rainbow path between u and v in G. Several variants of Rainbow k-Coloring have been studied, two of which are defined as follows. The Subset Rainbow k-Coloring takes as an input a graph G and a set S \subseteq V(G) \times V(G), and the objective is to decide if there exists c_R: E(G) \rightarrow [k] such that for all (u,v) \in S there is a rainbow path between u and v in G. The problem Steiner Rainbow k-Coloring takes as an input a graph G and a set S \subseteq V(G), and the objective is to decide if there exists c_R: E(G) \rightarrow [k] such that for all u,v \in S there is a rainbow path between u and v in G. In an attempt to resolve open problems posed by Kowalik et al. (ESA 2016), we obtain the following results. - For every k \geq 3, Rainbow k-Coloring does not admit an algorithm running in time 2^{o(|E(G)|)}n^{O(1)}, unless ETH fails. - For every k \geq 3, Steiner Rainbow k-Coloring does not admit an algorithm running in time 2^{o(|S|^2)}n^{O(1)}, unless ETH fails. - Subset Rainbow k-Coloring admits an algorithm running in time 2^{\OO(|S|)}n^{O(1)}. This also implies an algorithm running in time 2^{o(|S|^2)}n^{O(1)} for Steiner Rainbow k-Coloring, which matches the lower bound we obtain.
Cite as

Akanksha Agrawal. Fine-Grained Complexity of Rainbow Coloring and its Variants. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{agrawal:LIPIcs.MFCS.2017.60,
  author =	{Agrawal, Akanksha},
  title =	{{Fine-Grained Complexity of Rainbow Coloring and its Variants}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{60:1--60:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.60},
  URN =		{urn:nbn:de:0030-drops-80990},
  doi =		{10.4230/LIPIcs.MFCS.2017.60},
  annote =	{Keywords: Rainbow Coloring, Lower bound, ETH, Fine-grained Complexity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.67
Lossy Kernels for Hitting Subgraphs

Authors: Eduard Eiben, Danny Hermelin, and M. S. Ramanujan

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
In this paper, we study the Connected H-hitting Set and Dominating Set problems from the perspective of approximate kernelization, a framework recently introduced by Lokshtanov et al. [STOC 2017]. For the Connected H-hitting set problem, we obtain an \alpha-approximate kernel for every \alpha>1 and complement it with a lower bound for the natural weighted version. We then perform a refined analysis of the tradeoff between the approximation factor and kernel size for the Dominating Set problem on d-degenerate graphs and provide an interpolation of approximate kernels between the known d^2-approximate kernel of constant size and 1-approximate kernel of size k^{O(d^2)}.
Cite as

Eduard Eiben, Danny Hermelin, and M. S. Ramanujan. Lossy Kernels for Hitting Subgraphs. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.MFCS.2017.67,
  author =	{Eiben, Eduard and Hermelin, Danny and Ramanujan, M. S.},
  title =	{{Lossy Kernels for Hitting Subgraphs}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.67},
  URN =		{urn:nbn:de:0030-drops-80955},
  doi =		{10.4230/LIPIcs.MFCS.2017.67},
  annote =	{Keywords: parameterized algorithms, lossy kernelization, graph theory}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.78
Complexity of Restricted Variants of Skolem and Related Problems

Authors: Akshay S., Nikhil Balaji, and Nikhil Vyas

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Given a linear recurrence sequence (LRS), the Skolem problem, asks whether it ever becomes zero. The decidability of this problem has been open for several decades. Currently decidability is known only for LRS of order upto 4. For arbitrary orders (i.e., number of terms the n-th depends on), the only known complexity result is NP-hardness by a result of Blondel and Portier from 2002. In this paper, we give a different proof of this hardness result, which is arguably simpler and pinpoints the source of hardness. To demonstrate this, we identify a subclass of LRS for which the Skolem problem is in fact NP-complete. We show the generic nature of our lower-bound technique by adapting it to show stronger lower bounds of a related problem that encompasses many known decision problems on linear recurrent sequences.
Cite as

Akshay S., Nikhil Balaji, and Nikhil Vyas. Complexity of Restricted Variants of Skolem and Related Problems. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 78:1-78:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{s._et_al:LIPIcs.MFCS.2017.78,
  author =	{S., Akshay and Balaji, Nikhil and Vyas, Nikhil},
  title =	{{Complexity of Restricted Variants of Skolem and Related Problems}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{78:1--78:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.78},
  URN =		{urn:nbn:de:0030-drops-81306},
  doi =		{10.4230/LIPIcs.MFCS.2017.78},
  annote =	{Keywords: Linear recurrence sequences, Skolem problem, NP-completeness, Program termination}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2017.14
Flight Planning in Free Route Airspaces

Authors: Casper Kehlet Jensen, Marco Chiarandini, and Kim S. Larsen

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

Abstract
We consider the problem of finding cheapest flight routes through free route airspaces in a 2D setting. We subdivide the airspace into regions determined by a Voronoi subdivision around the points from a weather forecast. This gives rise to a regular grid of rectangular regions (quads) with every quad having an associated vector-weight that represents the wind magnitude and direction. Finding a cheapest path in this setting corresponds to finding a piece-wise linear path determined by points on the boundaries of the quads. In our solution approach, we discretize such boundaries by introducing border points and only consider segments connecting border points belonging to the same quad. While classic shortest path graph algorithms are available and applicable to the graphs originating from these border points, we design an algorithm that exploits the geometric structure of our scenario and show that this algorithm is more efficient in practice than classic graph-based algorithms. In particular, it scales better with the number of quads in the subdivision of the airspace, making it possible to find more accurate routes or to solve larger problems.
Cite as

Casper Kehlet Jensen, Marco Chiarandini, and Kim S. Larsen. Flight Planning in Free Route Airspaces. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jensen_et_al:OASIcs.ATMOS.2017.14,
  author =	{Jensen, Casper Kehlet and Chiarandini, Marco and Larsen, Kim S.},
  title =	{{Flight Planning in Free Route Airspaces}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{14:1--14:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.14},
  URN =		{urn:nbn:de:0030-drops-79047},
  doi =		{10.4230/OASIcs.ATMOS.2017.14},
  annote =	{Keywords: Flight planning, Geometric shortest path, Free route airspace, Vector weighted paths, Vector weighted planar subdivisions}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.18
WNetKAT: A Weighted SDN Programming and Verification Language

Authors: Kim G. Larsen, Stefan Schmid, and Bingtian Xue

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
Programmability and verifiability lie at the heart of the software-defined networking paradigm. While OpenFlow and its match-action concept provide primitive operations to manipulate hardware configurations, over the last years, several more expressive network programming languages have been developed. This paper presents WNetKAT, the first network programming language accounting for the fact that networks are inherently weighted, and communications subject to capacity constraints (e.g., in terms of bandwidth) and costs (e.g., latency or monetary costs). WNetKAT is based on a syntactic and semantic extension of the NetKAT algebra. We demonstrate several relevant applications for WNetKAT, including cost and capacity-aware reachability, as well as quality-of-service and fairness aspects. These applications do not only apply to classic, splittable and unsplittable (s,t)-flows, but also generalize to more complex (and stateful) network functions and service chains. For example, WNetKAT allows to model flows which need to traverse certain waypoint functions, which can change the traffic rate. This paper also shows the relationship between the equivalence problem of WNetKAT and the equivalence problem of the weighted finite automata, which implies undecidability of the former. However, this paper also shows the decidability of whether an expression equals to 0, which is sufficient in many practical scenarios, and we initiate the discussion of decidable subsets of the whole language.
Cite as

Kim G. Larsen, Stefan Schmid, and Bingtian Xue. WNetKAT: A Weighted SDN Programming and Verification Language. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{larsen_et_al:LIPIcs.OPODIS.2016.18,
  author =	{Larsen, Kim G. and Schmid, Stefan and Xue, Bingtian},
  title =	{{WNetKAT: A Weighted SDN Programming and Verification Language}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.18},
  URN =		{urn:nbn:de:0030-drops-70870},
  doi =		{10.4230/LIPIcs.OPODIS.2016.18},
  annote =	{Keywords: Software-Defined Networking, Verification, Reachability, Stateful Processing, Service Chains, Weighted Automata, Decidability, NetKAT}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2016.25
Probabilistic Mu-Calculus: Decidability and Complete Axiomatization

Authors: Kim G. Larsen, Radu Mardare, and Bingtian Xue

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract
We introduce a version of the probabilistic mu-calculus (PMC) built on top of a probabilistic modal logic that allows encoding n-ary inequational conditions on transition probabilities. PMC extends previously studied calculi and we prove that, despite its expressiveness, it enjoys a series of good meta-properties. Firstly, we prove the decidability of satisfiability checking by establishing the small model property. An algorithm for deciding the satisfiability problem is developed. As a second major result, we provide a complete axiomatization for the alternation-free fragment of PMC. The completeness proof is innovative in many aspects combining various techniques from topology and model theory.
Cite as

Kim G. Larsen, Radu Mardare, and Bingtian Xue. Probabilistic Mu-Calculus: Decidability and Complete Axiomatization. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{larsen_et_al:LIPIcs.FSTTCS.2016.25,
  author =	{Larsen, Kim G. and Mardare, Radu and Xue, Bingtian},
  title =	{{Probabilistic Mu-Calculus: Decidability and Complete Axiomatization}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{25:1--25:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.25},
  URN =		{urn:nbn:de:0030-drops-68607},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.25},
  annote =	{Keywords: Markov process, probabilistic modal mu-calculus, n-ary (in-)equational modalities, satisfiability, axiomatization}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2016.21
Complete Axiomatization for the Bisimilarity Distance on Markov Chains

Authors: Giorgio Bacci, Giovanni Bacci, Kim G. Larsen, and Radu Mardare

Published in: LIPIcs, Volume 59, 27th International Conference on Concurrency Theory (CONCUR 2016)

Abstract
In this paper we propose a complete axiomatization of the bisimilarity distance of Desharnais et al. for the class of finite labelled Markov chains. Our axiomatization is given in the style of a quantitative extension of equational logic recently proposed by Mardare, Panangaden, and Plotkin (LICS'16) that uses equality relations t =_e s indexed by rationals, expressing that "t is approximately equal to s up to an error e". Notably, our quantitative deductive system extends in a natural way the equational system for probabilistic bisimilarity given by Stark and Smolka by introducing an axiom for dealing with the Kantorovich distance between probability distributions.
Cite as

Giorgio Bacci, Giovanni Bacci, Kim G. Larsen, and Radu Mardare. Complete Axiomatization for the Bisimilarity Distance on Markov Chains. In 27th International Conference on Concurrency Theory (CONCUR 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 59, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bacci_et_al:LIPIcs.CONCUR.2016.21,
  author =	{Bacci, Giorgio and Bacci, Giovanni and G. Larsen, Kim and Mardare, Radu},
  title =	{{Complete Axiomatization for the Bisimilarity Distance on Markov Chains}},
  booktitle =	{27th International Conference on Concurrency Theory (CONCUR 2016)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-017-0},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{59},
  editor =	{Desharnais, Jos\'{e}e and Jagadeesan, Radha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2016.21},
  URN =		{urn:nbn:de:0030-drops-61569},
  doi =		{10.4230/LIPIcs.CONCUR.2016.21},
  annote =	{Keywords: Markov chains, Behavioral distances, Axiomatization}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.21
Online Dominating Set

Authors: Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbcik, and Kim S. Larsen

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
This paper is devoted to the online dominating set problem and its variants on trees, bipartite, bounded-degree, planar, and general graphs, distinguishing between connected and not necessarily connected graphs. We believe this paper represents the first systematic study of the effect of two limitations of online algorithms: making irrevocable decisions while not knowing the future, and being incremental, i.e., having to maintain solutions to all prefixes of the input. This is quantified through competitive analyses of online algorithms against two optimal algorithms, both knowing the entire input, but only one having to be incremental. We also consider the competitive ratio of the weaker of the two optimal algorithms against the other. In most cases, we obtain tight bounds on the competitive ratios. Our results show that requiring the graphs to be presented in a connected fashion allows the online algorithms to obtain provably better solutions. Furthermore, we get detailed information regarding the significance of the necessary requirement that online algorithms be incremental. In some cases, having to be incremental fully accounts for the online algorithm's disadvantage.
Cite as

Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbcik, and Kim S. Larsen. Online Dominating Set. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{boyar_et_al:LIPIcs.SWAT.2016.21,
  author =	{Boyar, Joan and Eidenbenz, Stephan J. and Favrholdt, Lene M. and Kotrbcik, Michal and Larsen, Kim S.},
  title =	{{Online Dominating Set}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.21},
  URN =		{urn:nbn:de:0030-drops-60434},
  doi =		{10.4230/LIPIcs.SWAT.2016.21},
  annote =	{Keywords: online algorithms, dominating set, competitive analysis, graph classes, connected graphs}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2014.121
Synchronizing Words for Weighted and Timed Automata

Authors: Laurent Doyen, Line Juhl, Kim G. Larsen, Nicolas Markey, and Mahsa Shirmohammadi

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Abstract
The problem of synchronizing automata is concerned with the existence of a word that sends all states of the automaton to one and the same state. This problem has classically been studied for complete deterministic finite automata, with the existence problem being NLOGSPACE-complete. In this paper we consider synchronizing-word problems for weighted and timed automata. We consider the synchronization problem in several variants and combinations of these, including deterministic and non-deterministic timed and weighted automata, synchronization to unique location with possibly different clock valuations or accumulated weights, as well as synchronization with a safety condition forbidding the automaton to visit states outside a safety-set during synchronization (e.g. energy constraints). For deterministic weighted automata, the synchronization problem is proven PSPACE-complete under energy constraints, and in 3-EXPSPACE under general safety constraints. For timed automata the synchronization problems are shown to be PSPACE-complete in the deterministic case, and undecidable in the non-deterministic case.
Cite as

Laurent Doyen, Line Juhl, Kim G. Larsen, Nicolas Markey, and Mahsa Shirmohammadi. Synchronizing Words for Weighted and Timed Automata. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 121-132, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{doyen_et_al:LIPIcs.FSTTCS.2014.121,
  author =	{Doyen, Laurent and Juhl, Line and Larsen, Kim G. and Markey, Nicolas and Shirmohammadi, Mahsa},
  title =	{{Synchronizing Words for Weighted and Timed Automata}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{121--132},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.121},
  URN =		{urn:nbn:de:0030-drops-48370},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.121},
  annote =	{Keywords: Synchronizing words, weighted automata, timed automata}
}
  • Refine by Author
  • 4 Larsen, Kim G.
  • 4 Larsen, Kim S.
  • 3 Boyar, Joan
  • 2 Eiben, Eduard
  • 2 Favrholdt, Lene M.
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 3 online algorithms
  • 2 competitive analysis
  • 2 parameterized algorithms
  • 2 weighted automata
  • 1 (directed) feedback vertex set
  • Show More...

  • Refine by Type
  • 17 document

  • Refine by Publication Year
  • 10 2017
  • 3 2016
  • 2 2014
  • 1 2009
  • 1 2022

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