Loading...
Please wait, while we are loading the content...
Similar Documents
CMSC 858 F : Algorithmic Lower Bounds Fall 2014 Puzzles and Reductions from 3-Partition Instructor :
| Content Provider | Semantic Scholar |
|---|---|
| Author | Hajiaghayi, Mohammad Taghi |
| Copyright Year | 2014 |
| Abstract | In this lecture, we first examine several classes of NP-hardness and polynomial time algorithms which arise from differences in how integers are encoded in problem input. We then look at the 3-partition problem, which is very useful for proving the strongest notion of NP-hardness. Finally, we use reduction from 3-partition to prove NP-hardness for a handful of problems, including a set of 4 packing type puzzles which we also show equivalent. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.umd.edu/~hajiagha/ALB14/scribe-09-09-2014.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
