Jump to content

Applying Polynomial Time Approximation Scheme (PTAS) on an algorithm

zak100
in Computer Science

Featured Replies

Hi,

I am trying to apply PTAS on an algorithm. I think that we apply PTAS on the running time equation of the algorithm. We use the term (1-ϵ) and (1+ ϵ) in the running time of the algorithm but I don’t know how we insert these terms in the running time equation of the algorithm, and that’s what I want to understand. Also how we evaluate the value of ϵ.

 

Let suppose we have a algorithm:

 

M = K * Y

Let’s the running time of algorithm is pseudo-polynomial i.e p(n) * K where k and p(n)  are polynomial in n.

Somebody please guide me.

 

Zulfi.

Archived

This topic is now archived and is closed to further replies.

Go to topic listing

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.

Configure browser push notifications
Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.