4 Search Results for "Bart, Hans-Jörg"

Document
DOI: 10.4230/LIPIcs.MFCS.2017.21
A Formal Semantics of Influence in Bayesian Reasoning

Authors: Bart Jacobs and Fabio Zanasi

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

Abstract
This paper proposes a formal definition of influence in Bayesian reasoning, based on the notions of state (as probability distribution), predicate, validity and conditioning. Our approach highlights how conditioning a joint entwined/entangled state with a predicate on one of its components has 'crossover' influence on the other components. We use the total variation metric on probability distributions to quantitatively measure such influence. These insights are applied to give a rigorous explanation of the fundamental concept of d-separation in Bayesian networks.
Cite as

Bart Jacobs and Fabio Zanasi. A Formal Semantics of Influence in Bayesian Reasoning. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jacobs_et_al:LIPIcs.MFCS.2017.21,
  author =	{Jacobs, Bart and Zanasi, Fabio},
  title =	{{A Formal Semantics of Influence in Bayesian Reasoning}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{21:1--21: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.21},
  URN =		{urn:nbn:de:0030-drops-80896},
  doi =		{10.4230/LIPIcs.MFCS.2017.21},
  annote =	{Keywords: probability distribution, Bayesian network, influence}
}
Document
DOI: 10.4230/OASIcs.VLUDS.2011.59
CFD Simulation of Liquid-Liquid Extraction Columns and Visualization of Eulerian Datasets

Authors: Mark W. Hlawitschka, Fang Chen, Hans-Jörg Bart, and Bernd Hamann

Published in: OASIcs, Volume 27, Visualization of Large and Unstructured Data Sets: Applications in Geospatial Planning, Modeling and Engineering - Proceedings of IRTG 1131 Workshop 2011

Abstract
In this joint work, a complete framework for modeling, simulating and visualizing multiphase fluid flow within an extraction column is presented. We first present a volume-of-fluid simulation, which is able to predict the surface of the droplets during coalescence. However, a fast and efficient model is needed for the simulation of a liquid-liquid extraction column due to the high number of occurring droplets. To simulate the velocity and droplet size in a DN32 extraction column, a coupled computational fluid dynamic-population balance model solver is used. The simulation is analyzed using path-line based visualization techniques. A novel semi-automatic re-seeding technique for droplet path-line integration is proposed. With our technique, path-lines of fluid droplets can be re-initialized after contact with the stirring devices. The droplet breakage is captured, allowing the engineer to improve the design of liquid-liquid columns layout.
Cite as

Mark W. Hlawitschka, Fang Chen, Hans-Jörg Bart, and Bernd Hamann. CFD Simulation of Liquid-Liquid Extraction Columns and Visualization of Eulerian Datasets. In Visualization of Large and Unstructured Data Sets: Applications in Geospatial Planning, Modeling and Engineering - Proceedings of IRTG 1131 Workshop 2011. Open Access Series in Informatics (OASIcs), Volume 27, pp. 59-70, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{hlawitschka_et_al:OASIcs.VLUDS.2011.59,
  author =	{Hlawitschka, Mark W. and Chen, Fang and Bart, Hans-J\"{o}rg and Hamann, Bernd},
  title =	{{CFD Simulation of Liquid-Liquid Extraction Columns and Visualization of Eulerian Datasets}},
  booktitle =	{Visualization of Large and Unstructured Data Sets: Applications in Geospatial Planning, Modeling and Engineering - Proceedings of IRTG 1131 Workshop 2011},
  pages =	{59--70},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-46-0},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{27},
  editor =	{Garth, Christoph and Middel, Ariane and Hagen, Hans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.VLUDS.2011.59},
  URN =		{urn:nbn:de:0030-drops-37410},
  doi =		{10.4230/OASIcs.VLUDS.2011.59},
  annote =	{Keywords: computational fluid dynamics, multiphase fluid, droplet collision, Eule- rian, path-line}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.165
Cross-Composition: A New Technique for Kernelization Lower Bounds

Authors: Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
We introduce a new technique for proving kernelization lower bounds, called cross-composition. A classical problem L cross-composes into a parameterized problem $Q$ if an instance of Q with polynomially bounded parameter value can express the logical OR of a sequence of instances of L. Building on work by Bodlaender et al. (ICALP 2008) and using a result by Fortnow and Santhanam (STOC 2008) we show that if an NP-hard problem cross-composes into a parameterized problem Q then Q does not admit a polynomial kernel unless the polynomial hierarchy collapses. Our technique generalizes and strengthens the recent techniques of using OR-composition algorithms and of transferring the lower bounds via polynomial parameter transformations. We show its applicability by proving kernelization lower bounds for a number of important graphs problems with structural (non-standard) parameterizations, e.g., Chromatic Number, Clique, and Weighted Feedback Vertex Set do not admit polynomial kernels with respect to the vertex cover number of the input graphs unless the polynomial hierarchy collapses, contrasting the fact that these problems are trivially fixed-parameter tractable for this parameter. We have similar lower bounds for Feedback Vertex Set.
Cite as

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Cross-Composition: A New Technique for Kernelization Lower Bounds. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 165-176, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.STACS.2011.165,
  author =	{Bodlaender, Hans L. and Jansen, Bart M. P. and Kratsch, Stefan},
  title =	{{Cross-Composition: A New Technique for Kernelization Lower Bounds}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{165--176},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.165},
  URN =		{urn:nbn:de:0030-drops-30082},
  doi =		{10.4230/LIPIcs.STACS.2011.165},
  annote =	{Keywords: kernelization, lower bounds, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.177
Vertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter

Authors: Bart M. P. Jansen and Hans L. Bodlaender

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
Kernelization is a concept that enables the formal mathematical analysis of data reduction through the framework of parameterized complexity. Intensive research into the Vertex Cover problem has shown that there is a preprocessing algorithm which given an instance (G,k) of Vertex Cover outputs an equivalent instance (G',k') in polynomial time with the guarantee that G' has at most 2k' vertices (and thus O((k')^2) edges) with k' <= k. Using the terminology of parameterized complexity we say that k-Vertex Cover has a kernel with 2k vertices. There is complexity-theoretic evidence that both 2k vertices and Theta(k^2) edges are optimal for the kernel size. In this paper we consider the Vertex Cover problem with a different parameter, the size fvs(G) of a minimum feedback vertex set for G. This refined parameter is structurally smaller than the parameter k associated to the vertex covering number VC(G) since fvs(G) <= VC(G) and the difference can be arbitrarily large. We give a kernel for Vertex Cover with a number of vertices that is cubic in fvs(G): an instance (G,X,k) of Vertex Cover, where X is a feedback vertex set for G, can be transformed in polynomial time into an equivalent instance (G',X',k') such that k' <= k, |X'| <= |X| and most importantly |V(G')| <= 2k and |V(G')| in O(|X'|^3). A similar result holds when the feedback vertex set X is not given along with the input. In sharp contrast we show that the Weighted Vertex Cover problem does not have polynomial kernel when parameterized by fvs(G) unless the polynomial hierarchy collapses to the third level (PH=Sigma_3^p). Our work is one of the first examples of research in kernelization using a non-standard parameter, and shows that this approach can yield interesting computational insights. To obtain our results we make extensive use of the combinatorial structure of independent sets in forests.
Cite as

Bart M. P. Jansen and Hans L. Bodlaender. Vertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 177-188, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.STACS.2011.177,
  author =	{Jansen, Bart M. P. and Bodlaender, Hans L.},
  title =	{{Vertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{177--188},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.177},
  URN =		{urn:nbn:de:0030-drops-30097},
  doi =		{10.4230/LIPIcs.STACS.2011.177},
  annote =	{Keywords: kernelization, lower bounds, parameterized complexity}
}
  • Refine by Author
  • 2 Bodlaender, Hans L.
  • 2 Jansen, Bart M. P.
  • 1 Bart, Hans-Jörg
  • 1 Chen, Fang
  • 1 Hamann, Bernd
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 2 kernelization
  • 2 lower bounds
  • 2 parameterized complexity
  • 1 Bayesian network
  • 1 Eule- rian
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2011
  • 1 2012
  • 1 2017

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