We survey recent results on the existence of polynomial time
approximation schemes for some dense instances of NP-hard
optimization problems. We indicate further some inherent limits
for existence of such schemes for some other dense instances of
the optimization problems.
We study the problem of assigning different communication channels to
acces points in a wireless Local Area Network. Each access point will
be assigned a specific radio frequency channel. Since channels with
similar frequencies interfere, it is desirable to assign far apart
channels (frequencies) to nearby access points. Our goal ...
more >>>
In this paper, we prove a general hardness amplification scheme for optimization problems based on the technique of direct products.
We say that an optimization problem $\Pi$ is direct product feasible if it is possible to efficiently aggregate any $k$ instances of $\Pi$ and form one large instance ...
more >>>
