CaltechAUTHORS
  A Caltech Library Service

Recurrence-Based Reductions for Inclusion and Exclusion Algorithms Applied to P Problems

Bax, Eric (1996) Recurrence-Based Reductions for Inclusion and Exclusion Algorithms Applied to P Problems. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechCSTR:1996.cs-tr-96-01

[img]
Preview
Postscript - Submitted Version
See Usage Policy.

2261Kb
[img]
Preview
PDF - Submitted Version
See Usage Policy.

1090Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1996.cs-tr-96-01

Abstract

There are inclusion and exclusion algorithms for many #P problems. By imposing a hierarchy on the inclusion and exclusion formula's terms, we develop general reductions for inclusion and exclusion algorithms. We outline sufficient steps to tailor the general reductions to specific problems, and we ilustrate this process by applying it to algorithms for several #P problems. We test the reductions on the problem of counting Hamiltonian paths. Within the framework of the general reductions, we develop the concepts or zero sets and vestigial elements, and we present problem decomposition strategies. Also, we show how the reductions can be applied to algorithms that give approximate solutions to #P problems.


Item Type:Report or Paper (Technical Report)
Additional Information:© 1996 California Institute of Technology. January 23, 1996. I thank three great teachers at Furman University: Dr. Douglas Rall for introducing me to combinatorics and to research, Dr. P. M. Cook for listening and guidance, and Or. Hayden Porter for teaching me two concepts that are central to this work - recursion and abstraction. Thanks to Dr. Andras Recski at MTKI in Budapest for teaching me when I was a student there, and also for taking the time to read my papers and point me in useful directions when I walked into his office out of the blue several years later. I thank Dr. Joel Franklin for showing an interest in this work, for listening patiently as I tried to explain it, and for supplying just the right information at just the right time. I thank my advisor Dr. Yaser S. Abu-Mostafa for his support, advice, and example. Supported by an NSF fellowship.
Group:Computer Science Technical Reports
Funders:
Funding AgencyGrant Number
NSF Predoctoral FellowshipUNSPECIFIED
Subject Keywords:algorithms, combinatorial problems, parallel algorithms.
Classification Code:AMS subject classifications 05,68
DOI:10.7907/Z9ST7MVX
Record Number:CaltechCSTR:1996.cs-tr-96-01
Persistent URL:http://resolver.caltech.edu/CaltechCSTR:1996.cs-tr-96-01
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26923
Collection:CaltechCSTR
Deposited By: Imported from CaltechCSTR
Deposited On:07 Mar 2002
Last Modified:11 Apr 2017 18:00

Repository Staff Only: item control page