Skip to main content
  • Skip to main content
  • Site Map
  • Log in
  • T
  • T
-A A +A
Home
School of Mathematical Sciences
राष्ट्रीय विज्ञान शिक्षा एवंअनुसंधान संस्थान
National Institute of Science Education and Research

NISER

  • Home
    • About SMS
  • People
    • Faculty
    • Staff
    • Students
      • Int. M.Sc.
      • Int.MSc-PhD
      • Ph.D.
    • Postdoc
    • Visitors
    • Alumni
      • Integrated M.Sc
      • PhD
      • Faculty
  • Research
    • Research Areas
    • Publications
  • Curriculum
    • Course Directory
      • UG Core Courses
      • UG Elective Courses
      • PG Core Courses
  • Activity
    • Upcoming
      • Seminar/Colloquium
      • Conference/Sympos/Workshop
      • Meeting
      • Outreach Program
    • Past
      • Seminar/Colloquium
      • Conference/Sympos/Workshop
      • Meeting
      • Outreach
    • MathematiX Club
      • SUMS
  • Blogs
  • Committees
  • Gallery
  • Contact

Breadcrumb

  1. Home
  2. Seminar

Seminar

By sutanu on Mon, 29/11/2021 - 14:24
Venue
Online (GoogleMeet)
Speaker
K Prahlad Narasimhan
Affiliation
NISER Bhubaneswar
Title
Optimality of local search algorithms

In this talk, we discuss our attempts to solve an important open problem regarding Terrain Guarding: is the state-of-the-art polynomial-time approximation scheme for the problem [Gibson2014], a simple local search construct, optimal? In this regard, we first sketch a proof of a recent advancement in this domain by Mustafa and Jartoux [Jartoux2018]. This work proves, for geometric hitting set problems which give rise to arbitrarily large grid-like exchange graphs, that the local search algorithm is indeed optimal. In light of this result, we question if the Terrain Guarding problem can give rise to such grids. We will conclude the talk by laying out a possible plan for future work on this problem.

Useful links

  • DAE
  • DST
  • JSTOR
  • MathSciNet
  • NBHM
  • ProjectEuclid
  • ScienceDirect

Quick links at NISER

  • NISER HOME
  • NISER Mail
  • Library
  • Intranet
  • Phone Book
  • WEB Portal
  • Office orders

Recent blog posts

Noncommutative Geometry and its Applications (NCG@NISER2020)
Purna Chandra Das : A Prosaic Ode to his Exceptional Life
Best paper award at SENSORNETS 2017 for Deepak Kumar Dalai

Contact us

School of Mathematical Sciences

NISER, PO- Bhimpur-Padanpur, Via- Jatni, District- Khurda, Odisha, India, PIN- 752050

Tel: +91-674-249-4081

© 2023 School of Mathematical Sciences, NISER, All Rights Reserved.