School of Technology and Computer Science Seminars

NP-Hardness of Art Gallery Problem & Terrain Guarding Problem

Name: NP-Hardness of Art Gallery Problem & Terrain Guarding Problem
Start: 2011-05-30T17:00:00+05:30
End: 2011-05-30T18:00:00+05:30
Location: Colaba Campus

by Bodhayan Roy (School of Technology and Computer Science)

Monday 30 May 2011, 17:00 → 18:00 Asia/Kolkata

A-212 (STCS Seminarf Room) (Colaba Campus)

A-212 (STCS Seminarf Room)

Colaba Campus

School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road Mumbai 400005

Description

This will be a talk on the proof of NP hardness of the Art Gallery Problem (which was described by Pritam last week). Approximation algorithms for the terrain guarding problem will also be described. References: http://www.tcs.tifr.res.in/~ghosh/artgallery-approx.pdf