Publications

1999

• E. Grädel and A. Malmström. 0-1 Laws for Recursive Structures. Archive for Mathematical Logic, vol. 38, pp. 205–215, 1999.                                 
  Abstract   BibTeX

  We discuss resource-bounded measures on the class of recursive structures and prove that with respect to such measures a random recursive structure is almost surely isomorphic to the unique countable model of the extension axioms.

  @article{GrMa99,
       author = {Erich Gr{\"a}del and Anders Malmstr{\"o}m},
       journal = {Archive for Mathematical Logic},
       pages = {205--215},
       title = {{0-1 Laws for Recursive Structures}},
       url = {http://www.logic.rwth-aachen.de/pub/anders/recursive.ps},
       volume = {38},
       year = {1999},
  }
  

1997

• A. Malmström. Logic and Approximation. PhD thesis, RWTH Aachen, 1997.             
  BibTeX

  @phdthesis{Ma97b,
       author = {Anders Malmstr{\"o}m},
       school = {RWTH Aachen},
       title = {{Logic and Approximation}},
       url = {http://www.logic.rwth-aachen.de/pub/anders/intro.ps},
       year = {1997},
  }
  

• A. Malmström. Optimization problems with approximation schemes. In Annual Conference of the European Association for Computer Science Logic CSL'96, Selected Papers, Utrecht (NL) (D. van Dalen and M. Bezem, Eds.), vol. 1258 of LNCS, pp. 316–333. Springer, 1997.                                 
  Abstract   BibTeX

  In this paper we extend recent work about the relationship between the syntactic description of NP optimization problems and their approximation properties. In contrast to \textbfMax SNP we consider problems that take arbitrary weighted structures as input instances and we use the framework of Metafinite Model Theory \citeGrGu98 to get a more general definability theory of optimization problems. We define a new class and show that every problem in this class has a fully polynomial-time approximation scheme (FPTAS), i.e. can be approximated to every desired accuracy e in time polynomial in the size of the input and $1/e$. An example for a problem in this class is \textbfKnapsack.

  @inproceedings{Ma97,
       author = {Anders Malmstr{\"o}m},
       booktitle = {{Annual Conference of the European Association for Computer Science Logic CSL'96, Selected Papers, Utrecht (NL)}},
       editor = {D. van Dalen and M. Bezem},
       pages = {316--333},
       publisher = {{Springer}},
       series = {{LNCS}},
       title = {{Optimization problems with approximation schemes}},
       url = {http://www.logic.rwth-aachen.de/pub/anders/csl96.ps},
       volume = {1258},
       year = {1997},
  }
  

1995

• A. Malmström. Log-approximable minimization problems on random input. In Annual Conference of the European Association for Computer Science Logic CSL'94, Selected Papers, Kazimierz (Poland), vol. 933 of LNCS, pp. 217–227. Springer, 1995.                                 
  Abstract   BibTeX

  We extend recent work about the relationship between logically defined classes of NP optimization problems and the asymptotic growth of optimal solutions on random inputs. We consider the syntactic class $MinF+\Pi\_2(1)$ of minimization problems. Kolaitis and Thakur proved that every problem in this class is log-approximable. We show that for every problem Q in the class Min $F+\Pi\_2(1)$ there exist polynomials $g(n)$ and $h(n)$ such the optimal solution of Q almost surely grows like $\Theta (g(n)+h(n) log n)$. Applying this result we show without using any complexity theoretical assumptions that the problem \textbfMin Graph Colouring is not in $Min F+\Pi\_2(1)$. With the same method we get a similar criterion for each class $Min F+Pi\_2(k)$. Using the fact that on a random graph with n nodes the chromatic number is $n/(2log n)$ almost surely we prove that \textbfMin Graph Colouring is not in $Min F+\Pi\_2$, resolving a conjecture by Kolaitis and Thakur.

  @inproceedings{Ma95,
       author = {Anders Malmstr{\"o}m},
       booktitle = {{Annual Conference of the European Association for Computer Science Logic CSL'94, Selected Papers, Kazimierz (Poland)}},
       pages = {217--227},
       publisher = {{Springer}},
       series = {{LNCS}},
       title = {{Log-approximable minimization problems on random input}},
       url = {http://www.logic.rwth-aachen.de/pub/anders/csl94.ps},
       volume = {933},
       year = {1995},
  }
  

1994

• E. Grädel and A. Malmström. Approximable minimization problems and optimal solutions on random input. In Computer Science Logic, 7th Workshop, CSL `93, Swansea 1993, Selected Papers (E. Börger, Y. Gurevich, and K. Meinke, Eds.), vol. 832 of LNCS, pp. 139–149. Springer, 1994.                                 
  Abstract   BibTeX

  In this paper we extend recent work about logical criteria for approximation properties of optimization problems. We focus on the relationship between logical expressibility and expected asymptotic growth of optimal solutions on random inputs. This further develops a probabilistic approach due to Behrendt, Compton and Grädel showing that expected optimal solutions for any problem in the class Max Sigma1 grows essentially like a polynomial. We show that there is a similar result for Min $F+\Pi\_1$, a syntactic class of minimization problems which provides a logical criterion for approximability. As a consequence, we show that some important problems do not belong to Min $F+\Pi\_1$.

  @inproceedings{GrMa94,
       author = {Erich Gr{\"a}del and Anders Malmstr{\"o}m},
       booktitle = {{Computer Science Logic, 7th Workshop, CSL `93, Swansea 1993, Selected Papers}},
       editor = {E. B{\"o}rger and Y. Gurevich and K. Meinke},
       pages = {139--149},
       publisher = {{Springer}},
       series = {{LNCS}},
       title = {{Approximable minimization problems and optimal solutions on random input}},
       url = {http://www.logic.rwth-aachen.de/pub/anders/csl93.ps},
       volume = {832},
       year = {1994},
  }