DROPS

Document

Resource-bounded Problem Solving (Dagstuhl Seminar 14341)

Authors: Yll Haxhimusa, Iris van Rooij, Sashank Varma, and Todd Wareham

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

Abstract

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.

Cite as

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-dev.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

DOI: 10.4230/DagRep.1.8.96

Computer Science & Problem Solving: New Foundations (Dagstuhl Seminar 11351)

Authors: Iris van Rooij, Yll Haxhimusa, Zygmunt Pizlo, and Georg Gottlob

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

Abstract

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.

Cite as

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-dev.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

DOI: 10.4230/DagSemProc.07281.3

Approximating Solution Structure

Authors: Iris van Rooij, Matthew Hamilton, Moritz Müller, and Todd Wareham

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

Abstract

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}

Cite as

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-dev.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}
}

3 Search Results for "van Rooij, Iris"

Resource-bounded Problem Solving (Dagstuhl Seminar 14341)

Abstract

Cite as

Computer Science & Problem Solving: New Foundations (Dagstuhl Seminar 11351)

Abstract

Cite as

Approximating Solution Structure

Abstract

Cite as

Thanks for your feedback!

Could not send message