Skip to main content
  • Home
  • About Us
    • Governing Board & Executive Council
    • IMSc Logo
  • Research
    • Theoretical Physics
    • Mathematics
    • Theoretical Computer Science
    • Computational Biology
  • People
    • Faculty
    • Former Faculty
    • Doctoral Fellows
    • Post Doctoral Fellows
    • Staff
  • Events
    • Seminars
    • Conferences
    • Event Calendar
    • IMSc @60
    • Azadi Ka Amrit Mahotsav
  • Resources
    • Library
    • Outreach
    • IMSc Media
    • Anti-Ragging
    • Internal Complaints Committee
  • Opportunities
    • Faculty Recruitment
    • Doctoral Programme
    • Post Doctoral Programme
    • Summer Research Programme
    • Associateship Programme
    • Visiting Scientist Programme
    • Visiting Student Programme
    • Other Positions
  • Tenders
  • Webmail

Search form

Home
The Institute of Mathematical Sciences
A national institute for research in the theoretical sciences

Upcoming Events

Oct 17
09:00-19:00
Conference
Quantum fields and strings
Conference | Alladi Ramakrishnan Hall
Oct 17
10:00-11:30
Saket+ | IMSc
Graph Theory Seminar
TCS Seminar | E C G Sudarshan Hall
Oct 17
14:15-15:30
Sipra Singh | IIT KGP
Knapsack: Connectedness, path and shortest-path
We study the Knapsack problem with graph-theoretic constraints. That is, there exists a graph structure on the input set of items of Knapsack and the solution also needs to satisfy certain graph theoretic properties on top of the Knapsack constraints. In particular, we study Connected Knapsack where the solution must be a connected subset of items which has maximum value and satisfies the size constraint of the knapsack. We show that this problem is strongly NP-complete even for graphs of maximum degree four and NP-complete even for star graphs. On the other hand, we develop an algorithm running in time O(2^tw logtw .poly(n). min{s^2, d^2}) where tw, s, d, n are respectively treewidth of the graph, the size of the knapsack, the target value of the knapsack, and the number of items. We also exhibit a (1-\epsilon) factor approximation algorithm running in time O(2^tw logtw .poly(n)) for every (\epsilon >0). We show similar results for Path Knapsack and Shortest Path Knapsack, where the solution must also induce a path and shortest path, respectively. Our results suggest that Connected Knapsack is computationally the hardest, followed by Path Knapsack and then Shortest Path Knapsack.
TCS Colloquium | Room 326
Oct 17
15:30-16:30
S Velmurugan | IMSc
Eigenvalues of permutations in representations of symmetric and alternating groups
This talk will be live-streamed on zoom. Join Zoom Meeting https://zoom.us/j/98206472628 [zoom.us] Meeting ID: 982 0647 2628 Passcode: 560304
Thesis Defence | E C G Sudarshan Hall
Oct 21
14:00-15:00
Abhishek Mohapatra | Technical University of Munich
TBA (Online)
TBA
Physics Seminar | Alladi Ramakrishnan Hall
More Seminars

Notice Board

  • Hindi Day Celebrations 2025
  • Prof A P Balachandran, In Memoriam
  • NBHM portal

Contact

The Institute of Mathematical Sciences
IV Cross Road, CIT Campus
Taramani
Chennai 600 113
Tamil Nadu, India.
Phone : 91-44-22543100
Fax      : 91-44-22541586

Useful Info

  • Getting Here
  • Shuttle Service
  • Working Hours
  • Forms
  • Vigilance Awareness Week

Resources

  • Computer Facilities
  • Important Numbers
  • Institute Reports
  • Official Language Policy
  • arXiv
  • RTI
  • Anti-Ragging
  • Internal Complaints Committee

For Members

  • Login
  • Student Info
  • HBNI
  • Committees