Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with optimization problems:
TR97-024 | 9th June 1997
Marek Karpinski

Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems

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.

more >>>

TR06-040 | 6th March 2006
Tomas Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu

Channel assignment in wireless networks and classification of minimum graph homomorphism

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

TR19-125 | 27th August 2019
Elazar Goldenberg, Karthik C. S.

Hardness Amplification of Optimization Problems

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

ISSN 1433-8092 | Imprint