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.
Amos Golan
- Published in print:
- 2017
- Published Online:
- November 2017
- ISBN:
- 9780199349524
- eISBN:
- 9780199349555
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780199349524.003.0012
- Subject:
- Economics and Finance, Econometrics
This chapter is the first of a two-chapter sequence looking into the relationship between info-metrics and the more familiar statistical methods of inference, with an emphasis on ...
More
This chapter is the first of a two-chapter sequence looking into the relationship between info-metrics and the more familiar statistical methods of inference, with an emphasis on information-theoretic methods. In this chapter I concentrate on discrete models. The relationship between info-metrics and information-theoretic statistical methods is established via duality theory, which provides a way for specifying all inferential methods as constrained optimization models. Since the objective here is to compare different approaches and philosophies, the analysis and examples are kept simple. A main result is that, for discrete problems, the maximum-likelihood approach is a special case of the info-metrics framework. To show this, I reconstruct the likelihood model as a constrained optimization problem. The relevant diagnostics and statistics are developed and discussed. I conclude the chapter with a detailed summary of the benefits of info-metrics for inference of discrete problems. Two detailed case studies are provided.Less
This chapter is the first of a two-chapter sequence looking into the relationship between info-metrics and the more familiar statistical methods of inference, with an emphasis on information-theoretic methods. In this chapter I concentrate on discrete models. The relationship between info-metrics and information-theoretic statistical methods is established via duality theory, which provides a way for specifying all inferential methods as constrained optimization models. Since the objective here is to compare different approaches and philosophies, the analysis and examples are kept simple. A main result is that, for discrete problems, the maximum-likelihood approach is a special case of the info-metrics framework. To show this, I reconstruct the likelihood model as a constrained optimization problem. The relevant diagnostics and statistics are developed and discussed. I conclude the chapter with a detailed summary of the benefits of info-metrics for inference of discrete problems. Two detailed case studies are provided.
Iain Pardoe and Dean Keith Simonton
- Published in print:
- 2013
- Published Online:
- January 2014
- ISBN:
- 9780199797813
- eISBN:
- 9780199369522
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199797813.003.0010
- Subject:
- Psychology, Social Psychology
Ever since 1928, the Academy of Motion Picture Arts and Sciences have bestowed its “Oscars” for major cinematic achievements. Well before the awards are announced at a gala ceremony now broadcast ...
More
Ever since 1928, the Academy of Motion Picture Arts and Sciences have bestowed its “Oscars” for major cinematic achievements. Well before the awards are announced at a gala ceremony now broadcast worldwide, the public and the media begin to speculate about which nominees will take home a golden statuette. Although there is no shortage of speculative theories about who is most likely to win, the announcements often include some major surprises. In this chapter, the prediction is framed as a discrete choice problem. Not only do these predictions enable us to calculate the probabilities of winning for each nominee, but they also provide a direct measure of surprise when an apparent frontrunner is eclipsed by a dark horse. These predictions are calculated up to the 2010 award season.Less
Ever since 1928, the Academy of Motion Picture Arts and Sciences have bestowed its “Oscars” for major cinematic achievements. Well before the awards are announced at a gala ceremony now broadcast worldwide, the public and the media begin to speculate about which nominees will take home a golden statuette. Although there is no shortage of speculative theories about who is most likely to win, the announcements often include some major surprises. In this chapter, the prediction is framed as a discrete choice problem. Not only do these predictions enable us to calculate the probabilities of winning for each nominee, but they also provide a direct measure of surprise when an apparent frontrunner is eclipsed by a dark horse. These predictions are calculated up to the 2010 award season.
