Deutsch Intern
Chair of Computer Science I - Algorithms and Complexity

Veröffentlichungen

Articles in Journals and Books

  • Parsing Boolean grammars over a one-letter alphabet using online convolution
    Alexander Okhotin, Christian Reitwießner.
    Theoretical Computer Science, Volume 457, pages 149-157, 2012.
  • The Shrinking Property for NP and coNP
    Christian Glaßer, Christian Reitwießner, Victor Selivanov.
    Theoretical Computer Science, Volume 415, pages 853-864, 2011.
  • Satisfiability of Algebraic Circuits over Sets of Natural Numbers
    Christian Glaßer, Christian Reitwießner, Stephen Travers, Matthias Waldherr.
    Discrete Applied Mathematics, Volume 158(13), pages 1394-1403, 2010.
  • Conjunctive Grammars with Restricted Disjunction
    Alexander Okhotin, Christian Reitwießner.
    Theoretical Computer Science, Volume 411, pages 2559-2571, 2010.
  • Equivalence Problems for Circuits over Sets of Natural Numbers
    Christian Glaßer, Katrin Herr, Christian Reitwießner, Stephen Travers, Matthias Waldherr.
    Theory of Computing Systems, Volume 46(1), pages 80-103, 2010.

Refereed Conference Papers

  • Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions
    Christian Glaßer, Dung Nguyen, Christian Reitwießner, Alan Selman, Maximilian Witek.
    ICALP 2013, to appear.
  • Structural Complexity of Multiobjective NP Search Problems
    Krzysztof Fleszar, Christian Glasser, Fabian Lipp, Christian Reitwießner and Maximilian Witek.
    Proceedings 10th Latin American Theoretical Informatics Symposium (LATIN), Arequipa, Peru, 2012.
    Lecture Notes in Computer Science 7256, pages 338-349, Springer-Verlag, 2012.
  • Applications of Discrepancy Theory in Multiobjective Approximation
    Christian Glaßer, Christian Reitwießner, Maximilian Witek.
    Proceedings Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Mumbai, India, 2011.
    LIPIcs 13, pages 55-65, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2011.

    PDF
  • Approximability and Hardness in Multi-Objective Optimization
    Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek.
    Computability in Europe (CiE), 2010.
    Lecture Notes in Computer Science 6158, pages 180-189, Springer-Verlag, 2010.
  • Conjunctive Grammars with Restricted Disjunction
    Alexander Okhotin, Christian Reitwießner.
    Proceedings 30th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Špindlerův Mlýn, Czech Republic, 2009.
    Lecture Notes in Computer Science 5404, pages 425-436, Springer-Verlag, 2009.
  • Multiobjective Disk Cover Admits a PTAS
    Christian Glaßer, Christian Reitwießner, Heinz Schmitz.
    Proceedings International Symposium on Algorithms and Computation (ISAAC), Gold Coast, Australia, 2008.
    Lecture Notes in Computer Science 5369, pages 40-51, Springer-Verlag, 2008.
  • The Shrinking Property for NP and coNP
    Christian Glaßer, Christian Reitwießner, Victor Selivanov.
    Proceedings Logic and Theory of Algorithms, Computability in Europe (CiE 2008), Athens, Greece, 2008.
    Lecture Notes in Computer Science 5028, pages 210-220, Springer-Verlag, 2008.
  • Satisfiability of Algebraic Circuits over Sets of Natural Numbers
    Christian Glaßer, Christian Reitwießner, Stephen Travers, Matthias Waldherr.
    Proceedings 27th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), New Delhi, India, 2007.
    Lecture Notes in Computer Science 4855, pages 253-264, Springer-Verlag, 2007.
  • Equivalence Problems for Circuits over Sets of Natural Numbers
    Christian Glaßer, Katrin Herr, Christian Reitwießner, Stephen Travers, Matthias Waldherr.
    Proceedings International Computer Science Symposium in Russia (CSR), Ekaterinburg, Russia, 2007.
    Lecture Notes in Computer Science 4649, pages 127-138, Springer-Verlag, 2007.

Technical Reports

  • Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions
    Christian Glaßer, Dung Nguyen, Christian Reitwießner, Alan Selman, Maximilian Witek.
    Electronic Colloquium on Computational Complexity, Report TR13-047, March 2013.
    PDF
  • Applications of Discrepancy Theory in Multiobjective Approximation
    Christian Glaßer, Christian Reitwießner, Maximilian Witek.
    Computing Research Repository CoRR, arXiv:1107.0634 [cs.DS], July 2011.
    PDF
  • Parsing Unary Boolean Grammars Using Online Convolution
    Alexander Okhotin, Christian Reitwießner.
    In: Christian Glaßer, Jean-Eric Pin, Nicole Schweikardt, Victor Selivanov and Wolfgang Thomas (eds.): Advances and Applications of Automata on Words and Trees, Dagstuhl Seminar Proceedings 10501, Dagstuhl, Germany, May 2011.
    PDF
  • The Complexity of Solving Multiobjective Optimization Problems and its Relation to Multivalued Functions
    Krzysztof Fleszar, Christian Glaßer, Fabian Lipp, Christian Reitwießner, Maximilian Witek.
    Electronic Colloquium on Computational Complexity, Report TR11-053, April 2011.
    PDF
  • Balanced Combinations of Solutions in Multi-Objective Optimization
    Christian Glaßer, Christian Reitwießner, Maximilian Witek.
    Computing Research Repository CoRR, arXiv:1007.5475v1 [cs.DS], July 2010.
    PDF
  • Hardness and Approximability in Multi-Objective Optimization
    Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek.
    Electronic Colloquium on Computational Complexity, Report TR10-031, March 2010.
    PDF
  • Improved and Generalized Approximations for Two-Objective Traveling Salesman
    Chrisitan Glaßer, Christian Reitwießner, Maximilian Witek.
    Electronic Colloquium on Computational Complexity, Report TR09-076-1, March 2010.
    PDF
  • Conjunctive Grammars with Restricted Disjuction
    Alexander Okhotin, Christian Reitwießner.
    In: Markus Holzer, Martin Kutrib, Andreas Malcher (eds.), 18. Theorietag Automaten und Formale Sprachen, Wettenberg-Launsbach, 2008, Proceedings. Justus-Liebig-Universität Gießen, Germany, 2008, 93 - 98.
    (Also appeared as Technical Report No. 915, Turku Centre for Computer Science, March 2009. PDF)
  • Multiobjective Disk Cover Admits a PTAS
    Christian Glaßer, Christian Reitwießner, Heinz Schmitz.
    Technical Report No. 443, Universität Würzburg, May 2008.
    PDF (461 kB)
  • The Shrinking Property for NP and coNP
    Christian Glaßer, Christian Reitwießner, Victor Selivanov.
    Technical Report No. 440, Universität Würzburg, January 2008.
    PDF (228 kB)
  • Satisfiability of Algebraic Circuits over Sets of Natural Numbers
    Christian Glaßer, Christian Reitwießner, Stephen Travers, Matthias Waldherr.
    Technical Report No. 402, Universität Würzburg, March 2007.
    PDF (202 kB)
  • Equivalence Problems for Circuits over Sets of Natural Numbers
    Christian Glaßer, Katrin Herr, Christian Reitwießner, Stephen Travers, Matthias Waldherr.
    Technical Report No. 392, Universität Würzburg, September 2006.
    PDF (326 kB)
  • Zusammenfalten des Postschen Verbandes mittels Operationen aus binären Booleschen Funktionen
    Christian Reitwießner.
    Technical Report No. 386, Universität Würzburg, June 2006.
    PDF (269 kB)

Theses

  • Multiobjective Optimization and Language Equations
    Christian Reitwießner.
    PhD thesis, Universität Würzburg, December 2011.
    PDF (2000 kB)
  • Formal Languages Defined by Recurrent Circuits
    Christian Reitwießner.
    Diploma thesis, Universität Würzburg, August 2007.
    PDF (1704 kB)
  • Zusammenfalten des Postschen Verbandes mittels Operationen aus binären Booleschen Funktionen
    Christian Reitwießner.
    Student project, Universität Würzburg, May 2006.
    PDF (280 kB)

Talks

  • Necklace Splitting and Multiobjective Optimization
    Universidad de Chile, January 2013.
    Slides
  • Parsing Unary Boolean Grammars Using Online Convolution
    Dagstuhl Seminar 10501 Advances and Applications of Automata on Words and Trees, Schloss Dagstuhl, Germany, December 2010.
    Slides
  • Multi-Objective Combinatorial Optimization: The Traveling Salesman Problem and Variants
    Turku, Finland, March 2010.
    Slides
  • Gentrys vollständig homomorphes Verschlüsselungsschema
    Oberseminar Theoretische Informatik, Universität Würzburg, Germany, July 2009.
  • Multiobjective Disk Cover Admits a PTAS
    International Symposium on Algorithms and Computation (ISAAC), Gold Coast, Australia, 2008.
    Slides
  • Konjunktive Grammatiken mit eingeschränkter Disjunktion
    Theorietag "Automaten und Formale Sprachen", Gießen, Germany, October 2008.
    Slides (in German)
    FORMAT-Workshop, Würzburg, Germany, February 2009.
  • Satisfiability of Algebraic Circuits over Sets of Natural Numbers
    Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2007, New Delhi, India, December 2007.
    Slides
  • Formal Languages Defined by Recurrent Circuits
    Oberseminar Theoretische Informatik, Universität Würzburg, Germany, June 2007.
    Slides (483 kB)
  • Äquivalenz- und Erfüllbarkeitsprobleme bei Schaltkreisen über Teilmengen der natürlichen Zahlen
    FORMAT-Workshop 2007, TU Kaiserslautern, Germany, March 2007.
  • Äquivalenzprobleme für Schaltkreise über Mengen von natürlichen Zahlen
    Oberseminar Theoretische Informatik, Universität Würzburg, Germany, November 2006.
  • Verallgemeinerte Quantorenoperationen auf Booleschen Funktionen
    Oberseminar Theoretische Informatik, Universität Würzburg, Germany, June 2006.
  • Skolem's Paradox
    Séminaire Franco-Allemand, Université de Caen, France, October 2005.