Campus Event Calendar: Michael Fellows (10/01/2008 in E1 4/024)

Campus Event Calendar

Campus Event Calendar:
- All Upcoming:
  - only for D1
  - only for D2
  - only for INET
  - only for D4
  - only for D5
  - only for D6
  - only for RG1
  - Mailing Lists
  - by Speaker
  - by Type
  - by Category
  - by Title
  - Calendar
  - RSS Feed
- History of Events:

Event Entry

What and Who

W-hardness: a tutorial

Michael Fellows

Max-Planck-Institut für Informatik - D1

Talk

AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS

MPI Audience

English

Note: We use this to send email in the morning.

Date, Time and Location

Wednesday, 1 October 2008

10:30

60 Minutes

E1 4

024

Saarbrücken

Abstract

Today we focus on W-hardness, i.e. we focus on problems that are probably not fixed-parameter tractable (similar to P vs NP). This includes a short introduction to the W-hierarchy.

Since some notions of approximability imply the fixed-parameter tractability of a parameterized version of the problem, W[1]-hardness proofs are an important tool (for example in proving that a problem is unlikely to admit an efficient PTAS).

Contact

Stefan Kratsch

--email hidden

System used:

Meeting URL:

Meeting ID:

Passcode:

passcode not visible

Code Visible for:

logged in users only

Stefan Kratsch, 09/24/2008 16:11 -- Created document.

Imprint / Impressum | Data Protection / Datenschutzhinweis