Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Obtaining Lower Bounds Using Artificial Components: Application to the Max Gap Problem

IP.com Disclosure Number: IPCOM000128363D
Original Publication Date: 1986-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 6 page(s) / 21K

Publishing Venue

Software Patent Institute

Related People

Prakash Ramanan: AUTHOR [+3]

Abstract

In this paper, we consider the technique of creating artificial components to obtain good lower bounds in the fixed order algebraic decision tree model, for geometric decision problems whose solution space (set of YES instances) consists of very few connected components. Using this technique, we obtain an 0(n log n) lower bound for the MAX CAP problem.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 30% of the total text.

Page 1 of 6

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Obtaining Lower Bounds Using Artificial Components: Application to the Max Gap Problem

Prakash Ramanan

Department of Computer Science

January 19P6

OBTAINING LOWER BOUNDS USING ARTIFICIAL COMPONENTS: APPLICATION TO THE MAX GAP PROBLEM Prakash Ramanan Department of Computer Science University of California Santa Barbara, CA 93106

Abstract.

In this paper, we consider the technique of creating artificial components to obtain good lower bounds in the fixed order algebraic decision tree model, for geometric decision problems whose solution space (set of YES instances) consists of very few connected components. Using this technique, we obtain an 0(n log n) lower bound for the MAX CAP problem.

1. Introduction

In this paper, we consider a technique for obtaining lower bounds in the fixed order algebraic decision tree model of computation (see (I)), for decision problems whose input instances can be considered as points in the n dimensional Cartesian space E". One well-known technique for obtaining lower bounds for such problems is based on the following theorem of Ben-Or (1).

Theorem 1. Let W be a set in the Cartesian space E", and let #( W) be the number of disjoint connected components of W. Then any algebraic decision tree of fixed order that solves the membership problem for

(Equation Omitted)

depth. For a problem P whose instances are points in F;", let the "solution space" W be the set of alt YES instances of P. Then the above theorem can be used to obtain reasonable lower bounds on the time-complexity of P if # ( W) is large. If this lower bound is not satisfactory, we can consider

(Equation Omitted)

is the solution space of P, the complement of problem P. Unfortunately, for some problems, both # ( W) and # ( W) are small, and the lower bounds obtained using the above theorem are unsatisfactory. To over come this, we propose the technique of creating artificial components. This technique is explained in Section 2. In Section 3, we illus-trate this technique for the MAY

University of California at Santa Barbara Page 1 Dec 31, 1986

Page 2 of 6

Obtaining Lower Bounds Using Artificial Components: Application to the Max Gap Problem

GAP problem. In Section 9, we discuss some other problems for which this technique might lead to good lower bound results.

2. Artificial Components

Our technique for creating artificial components is as follows. Modify the problem P (or P) slightly, by adding some Artificial Conditions that an YES instance must satisfy, thereby obtaining the problem RIC. Let WAC be the solution space of P1C. The artificial conditions should be such that

(Equation Omitted)

is large, and PAC is

(Equation Omitted)

time transformable to P. Then we can conclude that P has an

(Equation Omitted)

lower bound in the fixed order algeb{~sric decision tree model. This is surnmariacd by the (allowing theorem. Theorem 2. Let W be a set in the Cartesian space E , and let S be a...