Rolf Niedermeier
- Published in print:
- 2006
- Published Online:
- September 2007
- ISBN:
- 9780198566076
- eISBN:
- 9780191713910
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566076.001.0001
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
This book provides an introduction to the concept of fixed-parameter tractability. The corresponding design and analysis of efficient fixed-parameter algorithms for optimally solving combinatorially ...
More
This book provides an introduction to the concept of fixed-parameter tractability. The corresponding design and analysis of efficient fixed-parameter algorithms for optimally solving combinatorially explosive (NP-hard) discrete problems is a vividly developing field, with a growing list of applications in various contexts such as network analysis or bioinformatics. The book emphasizes algorithmic techniques over computational complexity theory. It is divided into three parts: a broad introduction that provides the general philosophy and motivation; followed by coverage of algorithmic methods developed over the years in fixed-parameter algorithmics forming the core of the book; and a discussion of the essentials of parameterized hardness theory with a focus on W[1]-hardness which parallels NP-hardness, then stating some relations to polynomial-time approximation algorithms, and finishing up with a list of selected case studies to show the wide range of applicability of the presented methodology.Less
This book provides an introduction to the concept of fixed-parameter tractability. The corresponding design and analysis of efficient fixed-parameter algorithms for optimally solving combinatorially explosive (NP-hard) discrete problems is a vividly developing field, with a growing list of applications in various contexts such as network analysis or bioinformatics. The book emphasizes algorithmic techniques over computational complexity theory. It is divided into three parts: a broad introduction that provides the general philosophy and motivation; followed by coverage of algorithmic methods developed over the years in fixed-parameter algorithmics forming the core of the book; and a discussion of the essentials of parameterized hardness theory with a focus on W[1]-hardness which parallels NP-hardness, then stating some relations to polynomial-time approximation algorithms, and finishing up with a list of selected case studies to show the wide range of applicability of the presented methodology.
John L. Pollock
- Published in print:
- 2006
- Published Online:
- October 2011
- ISBN:
- 9780195304817
- eISBN:
- 9780199850907
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780195304817.003.0012
- Subject:
- Philosophy, Philosophy of Mind
This chapter reiterates the proposition that practical cognition should not aim at finding optimal solutions to practical problems. A rational cognizer should instead look for good solutions, and ...
More
This chapter reiterates the proposition that practical cognition should not aim at finding optimal solutions to practical problems. A rational cognizer should instead look for good solutions, and replace them with better solutions if any are found. Solutions come in the form of plans. In general, a change to the master plan may consist of deleting several local plans and adding several others. This theory is still fairly schematic. It leaves most details to the imagination of the reader, and in philosophy, that is often a recipe for disaster. When philosophical theories fail, it is not because they did not look good in the abstract—it is because it is impossible to make the details work. This chapter simply gives a preliminary sketch of how a resource bounded agent can actually perform locally global planning.Less
This chapter reiterates the proposition that practical cognition should not aim at finding optimal solutions to practical problems. A rational cognizer should instead look for good solutions, and replace them with better solutions if any are found. Solutions come in the form of plans. In general, a change to the master plan may consist of deleting several local plans and adding several others. This theory is still fairly schematic. It leaves most details to the imagination of the reader, and in philosophy, that is often a recipe for disaster. When philosophical theories fail, it is not because they did not look good in the abstract—it is because it is impossible to make the details work. This chapter simply gives a preliminary sketch of how a resource bounded agent can actually perform locally global planning.
John E. Prussing
- Published in print:
- 2017
- Published Online:
- February 2018
- ISBN:
- 9780198811084
- eISBN:
- 9780191848360
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780198811084.001.0001
- Subject:
- Mathematics, Applied Mathematics
Optimal spacecraft trajectories are given a modern comprehensive treatment of the theory and important results. In most cases “optimal” means minimum propellant. Less propellant required results in ...
More
Optimal spacecraft trajectories are given a modern comprehensive treatment of the theory and important results. In most cases “optimal” means minimum propellant. Less propellant required results in more payload delivered to the destination. Both necessary and sufficient conditions for an optimal solution are analysed. Numerous illustrative examples are included and problems are provided at the ends of the chapters along with references. Newer topics such as cooperative rendezvous and second-order conditions are considered. Seven appendices are included to supplement the text, some with problems. Both classical results and newer research results are included. A new test for a conjugate point is demonstrated. The book is both a graduate-level textbook and a scholarly reference book.Less
Optimal spacecraft trajectories are given a modern comprehensive treatment of the theory and important results. In most cases “optimal” means minimum propellant. Less propellant required results in more payload delivered to the destination. Both necessary and sufficient conditions for an optimal solution are analysed. Numerous illustrative examples are included and problems are provided at the ends of the chapters along with references. Newer topics such as cooperative rendezvous and second-order conditions are considered. Seven appendices are included to supplement the text, some with problems. Both classical results and newer research results are included. A new test for a conjugate point is demonstrated. The book is both a graduate-level textbook and a scholarly reference book.
