dimacs logo color

Events

Event Calendar

« Previous Month

August 2026

Next Month »
Sun Mon Tue Wed Thu Fri Sat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Seminar Details

How fast can NP-Complete problems be solved in worst case?

  • Start Date: June 30, 2004
  • Event Start Time: 1:00 PM
  • Event End Time: 2:00 PM
  • Organizers: Brenda Latka
  • Seminar Series: REU Seminar
  • Presenter(s): Michael Saks - Rutgers University
  • Event Location: DIMACS Seminar room
  • Abstract: It is widely believed that any algorithm that solves an NP-Complete problem must have running time that, in worst case, is an exponential function of the size of the input. Researchers have developed ad hoc algorithms for specific problems that work surprisingly well in practice. These algorithms tend to be rather complicated and it is difficult to prove anything about their worst case behavior. In this talk, I'll discuss the problem of developing algorithms for NP-complete problems whose PROVABLE worst case running time is as small as possible. I'll concentrate on three computational problems: (1) hamiltonian cycle, (2) chromatic number, and (3) Boolean CNF satisfiability.