3 Search Results for "Oetsch, Johannes"


Document
Complexity and Approximability of Parameterized MAX-CSPs

Authors: Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)


Abstract
We study the optimization version of constraint satisfaction problems (Max-CSPs) in the framework of parameterized complexity; the goal is to compute the maximum fraction of constraints that can be satisfied simultaneously. In standard CSPs, we want to decide whether this fraction equals one. The parameters we investigate are structural measures, such as the treewidth or the clique-width of the variable–constraint incidence graph of the CSP instance. We consider Max-CSPs with the constraint types AND, OR, PARITY, and MAJORITY, and with various parameters k. We attempt to fully classify them into the following three cases: 1. The exact optimum can be computed in FPT-time. 2. It is W[1]-hard to compute the exact optimum, but there is a randomized FPT approximation scheme (FPT-AS), which computes a (1-epsilon)-approximation in time f(k,epsilon) * poly(n). 3. There is no FPT-AS unless FPT=W[1]. For the corresponding standard CSPs, we establish FPT vs. W[1]-hardness results.

Cite as

Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke. Complexity and Approximability of Parameterized MAX-CSPs. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 294-306, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{dell_et_al:LIPIcs.IPEC.2015.294,
  author =	{Dell, Holger and Kim, Eun Jung and Lampis, Michael and Mitsou, Valia and M\"{o}mke, Tobias},
  title =	{{Complexity and Approximability of Parameterized MAX-CSPs}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{294--306},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.294},
  URN =		{urn:nbn:de:0030-drops-55910},
  doi =		{10.4230/LIPIcs.IPEC.2015.294},
  annote =	{Keywords: Approximation, Structural Parameters, Constraint Satisfaction}
}
Document
An FLP-Style Answer-Set Semantics for Abstract-Constraint Programs with Disjunctions

Authors: Johannes Oetsch, Jörg Pührer, and Hans Tompits

Published in: LIPIcs, Volume 17, Technical Communications of the 28th International Conference on Logic Programming (ICLP'12) (2012)


Abstract
We introduce an answer-set semantics for abstract-constraint programs with disjunction in rule heads in the style of Faber, Leone, and Pfeifer (FLP). To this end, we extend the definition of an answer set for logic programs with aggregates in rule bodies using the usual FLP-reduct. Additionally, we also provide a characterisation of our semantics in terms of unfounded sets, likewise generalising the standard concept of an unfounded set. Our work is motivated by the desire to have simple and rule-based definitions of the semantics of an answer-set programming (ASP) language that is close to those implemented by the most prominent ASP solvers. The new definitions are intended as a theoretical device to allow for development methods and methodologies for ASP, e.g., debugging or testing techniques, that are general enough to work for different types of solvers. We use abstract constraints as an abstraction of literals whose truth values depend on subsets of an interpretation. This includes weight constraints, aggregates, and external atoms, which are frequently used in real-world answer-set programs. We compare the new semantics to previous semantics for abstract-constraint programs and show that they are equivalent to recent extensions of the FLP semantics to propositional and first-order theories when abstract-constraint programs are viewed as theories.

Cite as

Johannes Oetsch, Jörg Pührer, and Hans Tompits. An FLP-Style Answer-Set Semantics for Abstract-Constraint Programs with Disjunctions. In Technical Communications of the 28th International Conference on Logic Programming (ICLP'12). Leibniz International Proceedings in Informatics (LIPIcs), Volume 17, pp. 222-234, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{oetsch_et_al:LIPIcs.ICLP.2012.222,
  author =	{Oetsch, Johannes and P\"{u}hrer, J\"{o}rg and Tompits, Hans},
  title =	{{An FLP-Style Answer-Set Semantics for Abstract-Constraint Programs with Disjunctions}},
  booktitle =	{Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)},
  pages =	{222--234},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-43-9},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{17},
  editor =	{Dovier, Agostino and Santos Costa, V{\'\i}tor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2012.222},
  URN =		{urn:nbn:de:0030-drops-36246},
  doi =		{10.4230/LIPIcs.ICLP.2012.222},
  annote =	{Keywords: answer-set programming, abstract constraints, aggregates, disjunction}
}
Document
Methods and Methodologies for Developing Answer-Set Programs - Project Description

Authors: Johannes Oetsch, Jörg Pührer, and Hans Tompits

Published in: LIPIcs, Volume 7, Technical Communications of the 26th International Conference on Logic Programming (2010)


Abstract
Answer-set programming (ASP) is a well-known formalism for declarative problem solving, enjoying a continuously increasing number of diverse applications. However, arguably one of the main challenges for a wider acceptance of ASP is the need of tools, methods, and methodologies that support the actual programming process. In this paper, we review the main goals of a project, funded by the Austrian Science Fund (FWF), which aims to address this aspect in a systematic manner. The project is planned for a duration of three years and started in September 2009. Generally, the focus of research will be on methodologies for systematic program development, program testing, and debugging. In particular, in working on these areas, special emphasis shall be given to the ability of the developed techniques to respect the declarative nature of ASP. To support a sufficient level of usability, solutions are planned to be compatible not only for the core language of ASP but also for important extensions thereof that are commonly used and realised in various answer-set solvers. Ultimately, the methods resulting from the project shall form the basis of an integrated development environment (IDE) for ASP that is envisaged to combine straightforward as well as advanced techniques, realising a convenient tool for developing answer-set programs.

Cite as

Johannes Oetsch, Jörg Pührer, and Hans Tompits. Methods and Methodologies for Developing Answer-Set Programs - Project Description. In Technical Communications of the 26th International Conference on Logic Programming. Leibniz International Proceedings in Informatics (LIPIcs), Volume 7, pp. 154-161, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{oetsch_et_al:LIPIcs.ICLP.2010.154,
  author =	{Oetsch, Johannes and P\"{u}hrer, J\"{o}rg and Tompits, Hans},
  title =	{{Methods and Methodologies for Developing Answer-Set Programs - Project Description}},
  booktitle =	{Technical Communications of the 26th International Conference on Logic Programming},
  pages =	{154--161},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-17-0},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{7},
  editor =	{Hermenegildo, Manuel and Schaub, Torsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2010.154},
  URN =		{urn:nbn:de:0030-drops-25937},
  doi =		{10.4230/LIPIcs.ICLP.2010.154},
  annote =	{Keywords: Answer-set programming, program development, testing, debugging}
}
  • Refine by Author
  • 2 Oetsch, Johannes
  • 2 Pührer, Jörg
  • 2 Tompits, Hans
  • 1 Dell, Holger
  • 1 Kim, Eun Jung
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Answer-set programming
  • 1 Approximation
  • 1 Constraint Satisfaction
  • 1 Structural Parameters
  • 1 abstract constraints
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2010
  • 1 2012
  • 1 2015

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