We design approximation algorithms for several NP-hard combinatorial problems achieving ratios that cannot be achieved in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation. We study in particular MAX INDEPENDENT SET, MIN VERTEX COVER and MIN SET COVER and then extend our results to MAX CLIQUE, MAX BIPARTITE SUBGRAPH and MAX SET PACKING.
展开▼
机译：我们设计近似算法，用于实现在多项式时间（除非确认非常不太可能的复杂性猜测）中无法实现的比率的近似算法（除非确认非常不太可能的复杂性猜测）比精确计算更低（虽然超多项式）。我们特别研究MAX独立集，最小顶点盖板和MIN SET盖，然后将结果扩展到MAX Clique，MAX Biparte Subgraph和Max Set Packing。
展开▼
