DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2011.55

Applications of Discrepancy Theory in Multiobjective Approximation

Authors: Christian Glaßer, Christian Reitwießner, and Maximilian Witek

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract

We apply a multi-color extension of the Beck-Fiala theorem to show that the multiobjective maximum traveling salesman problem is randomized 1/2-approximable on directed graphs and randomized 2/3-approximable on undirected graphs. Using the same technique we show that the multiobjective maximum satisfiablilty problem is 1/2-approximable.

Cite as

Christian Glaßer, Christian Reitwießner, and Maximilian Witek. Applications of Discrepancy Theory in Multiobjective Approximation. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 55-65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{glaer_et_al:LIPIcs.FSTTCS.2011.55,
  author =	{Gla{\ss}er, Christian and Reitwie{\ss}ner, Christian and Witek, Maximilian},
  title =	{{Applications of Discrepancy Theory in Multiobjective Approximation}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{55--65},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.55},
  URN =		{urn:nbn:de:0030-drops-33233},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.55},
  annote =	{Keywords: Discrepancy Theory, Multiobjective Optimization, Satisfiability, Traveling Salesman}
}

Document

DOI: 10.4230/DagSemProc.10501.3

Parsing Unary Boolean Grammars Using Online Convolution

Authors: Alexander Okhotin and Christian Reitwießner

Published in: Dagstuhl Seminar Proceedings, Volume 10501, Advances and Applications of Automata on Words and Trees (2011)

Abstract

In contrast to context-free grammars, the extension of these grammars by explicit conjunction, the so-called conjunctive grammars can generate (quite complicated) non-regular languages over a single-letter alphabet (DLT 2007). Given these expressibility results, we study the parsability of Boolean grammars, an extension of context-free grammars by conjunction and negation, over a unary alphabet and show that they can be parsed in time O(|G| log^2(n) M(n)) where M(n) is the time to multiply two n-bit integers. This multiplication algorithm is transformed into a convolution algorithm which in turn is converted to an online convolution algorithm which is used for the parsing.

Cite as

Alexander Okhotin and Christian Reitwießner. Parsing Unary Boolean Grammars Using Online Convolution. In Advances and Applications of Automata on Words and Trees. Dagstuhl Seminar Proceedings, Volume 10501, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{okhotin_et_al:DagSemProc.10501.3,
  author =	{Okhotin, Alexander and Reitwie{\ss}ner, Christian},
  title =	{{Parsing Unary Boolean Grammars Using Online Convolution}},
  booktitle =	{Advances and Applications of Automata on Words and Trees},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10501},
  editor =	{Christian Glasser and Jean-Eric Pin and Nicole Schweikardt and Victor Selivanov and Wolfgang Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10501.3},
  URN =		{urn:nbn:de:0030-drops-31465},
  doi =		{10.4230/DagSemProc.10501.3},
  annote =	{Keywords: }
}

Search Results

Documents authored by Reitwießner, Christian

Applications of Discrepancy Theory in Multiobjective Approximation

Abstract

Cite as

Parsing Unary Boolean Grammars Using Online Convolution

Abstract

Cite as

Thanks for your feedback!

Could not send message