Document

**Published in:** Dagstuhl Reports, Volume 4, Issue 8 (2015)

This report documents the program and the outcomes of Dagstuhl Seminar 14341 'Resource-bounded Problem Solving'. This seminar is a successor to Dagstuhl Seminar 11351: 'Computer Science & Problem Solving: New Foundations', held in August 2011, which was the first Dagstuhl event to bring together computer scientists and psychologists to exchange perspectives on problem solving in general. The current seminar built on the previous seminar by (1) narrowing the focus to issues related to resource-bounded problem solving and (2) broadening the range of perspectives on the specific topic by including a balanced number of attendees with expertise in computer science, psychology, artificial intelligence, and cognitive neuroscience.

Yll Haxhimusa, Iris van Rooij, Sashank Varma, and Todd Wareham. Resource-bounded Problem Solving (Dagstuhl Seminar 14341). In Dagstuhl Reports, Volume 4, Issue 8, pp. 45-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{haxhimusa_et_al:DagRep.4.8.45, author = {Haxhimusa, Yll and van Rooij, Iris and Varma, Sashank and Wareham, Todd}, title = {{Resource-bounded Problem Solving (Dagstuhl Seminar 14341)}}, pages = {45--72}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2014}, volume = {4}, number = {8}, editor = {Haxhimusa, Yll and van Rooij, Iris and Varma, Sashank and Wareham, Todd}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.8.45}, URN = {urn:nbn:de:0030-drops-47989}, doi = {10.4230/DagRep.4.8.45}, annote = {Keywords: complexity theory, problem solving, cognitive psychology, computational trade-offs} }

Document

**Published in:** Dagstuhl Reports, Volume 1, Issue 8 (2011)

This report documents the program and the outcomes of Dagstuhl Seminar 11351 ``Computer Science & Problem Solving: New Foundations''. This seminar was the first Dagstuhl seminar that brought together a balanced group of computer scientists and psychologists to exchange perspectives on problem solving. In the 1950s the seminal work of Allen Newell and Herbert Simon laid the theoretical foundations for problem solving research as we know it today, but the field had since become disconnected from contemporary computer science. The aim of this seminar was to promote theoretical progress in problem solving research by renewing the connection between psychology and computer science in this area.

Iris van Rooij, Yll Haxhimusa, Zygmunt Pizlo, and Georg Gottlob. Computer Science & Problem Solving: New Foundations (Dagstuhl Seminar 11351). In Dagstuhl Reports, Volume 1, Issue 8, pp. 96-124, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{vanrooij_et_al:DagRep.1.8.96, author = {van Rooij, Iris and Haxhimusa, Yll and Pizlo, Zygmunt and Gottlob, Georg}, title = {{Computer Science \& Problem Solving: New Foundations (Dagstuhl Seminar 11351)}}, pages = {96--124}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2011}, volume = {1}, number = {8}, editor = {van Rooij, Iris and Haxhimusa, Yll and Pizlo, Zygmunt and Gottlob, Georg}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.8.96}, URN = {urn:nbn:de:0030-drops-33169}, doi = {10.4230/DagRep.1.8.96}, annote = {Keywords: Problem solving, Cognitive psychology, Cognitive systems, Vision Representations, Computational complexity} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)

hen it is hard to compute an optimal solution $y in optsol(x)$ to an
instance $x$ of a problem, one may be willing to settle for an efficient
algorithm $A$ that computes an approximate solution $A(x)$. The most
popular type of approximation algorithm in Computer Science (and indeed
many other applications) computes solutions whose value is within some multiplicative factor of the optimal solution value, {em e.g.},
$max(frac{val(A(x))}{optval(x)}, frac{optval(x)}{val(A(x))}) leq
h(|x|)$ for some function $h()$. However, an algorithm might also
produce a solution whose structure is ``close'' to the structure of an
optimal solution relative to a specified solution-distance function $d$,
{em i.e.}, $d(A(x), y) leq h(|x|)$ for some $y in optsol(x)$. Such
structure-approximation algorithms have applications within Cognitive
Science and other areas. Though there is an
extensive literature dating back over 30 years on value-approximation,
there is to our knowledge no work on general techniques for assessing
the structure-(in)approximability of a given problem.
In this talk, we describe a framework for investigating the
polynomial-time and fixed-parameter structure-(in)approximability of
combinatorial optimization problems relative to metric solution-distance
functions, {em e.g.}, Hamming distance. We motivate this framework by
(1) describing a particular application within Cognitive Science and (2)
showing that value-approximability does not necessarily imply
structure-approximability (and vice versa). This framework includes
definitions of several types of structure approximation algorithms
analogous to those studied in value-approximation, as well as
structure-approximation problem classes and a
structure-approximability-preserving reducibility. We describe a set of techniques for proving the degree of
structure-(in)approximability of a given problem, and summarize all
known results derived using these techniques. We also list 11 open
questions summarizing particularly promising directions for future
research within this framework.
vspace*{0.15in}
oindent
(co-presented with Todd Wareham)
vspace*{0.15in}
jointwork{Hamilton, Matthew; M"{u}ller, Moritz; van Rooij, Iris; Wareham, Todd}

Iris van Rooij, Matthew Hamilton, Moritz Müller, and Todd Wareham. Approximating Solution Structure. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{vanrooij_et_al:DagSemProc.07281.3, author = {van Rooij, Iris and Hamilton, Matthew and M\"{u}ller, Moritz and Wareham, Todd}, title = {{Approximating Solution Structure}}, booktitle = {Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs}, pages = {1--24}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7281}, editor = {Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.3}, URN = {urn:nbn:de:0030-drops-12345}, doi = {10.4230/DagSemProc.07281.3}, annote = {Keywords: Approximation Algorithms, Solution Structure} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail