Marek Karpinski

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.

Tomas Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu

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 >>>

Elazar Goldenberg, Karthik C. S.

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 >>>