Abstract
In the past decade, there has been a stream of work in designing approximation schemes for dense instances of NP-Hard problems. These include the work of Arora, Karger and Karpinski from 1995 and that of Frieze and Kannan from 1996. We address the problem of proving hardness results for (fully) dense problems, which has been neglected despite the fruitful effort put in upper bounds. In this work, we prove hardness results of dense instances of a broad family of CSP problems, as well as a broad family of ranking problems which we refer to as CSP-Rank. Our techniques involve a construction of a pseudorandom hypergraph coloring, which generalizes the well-known Paley graph, recently used by Alon to prove hardness of feedback arc-set in tournaments.
Original language | English (US) |
---|---|
Pages (from-to) | 1117-1129 |
Number of pages | 13 |
Journal | Information and Computation |
Volume | 205 |
Issue number | 8 |
DOIs | |
State | Published - Aug 2007 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics
Keywords
- Dense problems
- NP-hardness