Loading...
Please wait, while we are loading the content...
Similar Documents
Some optimal inapproximability results (2002)
| Content Provider | CiteSeerX |
|---|---|
| Author | Håstad, Johan |
| Abstract | We prove optimal, up to an arbitrary > 0, inapproximability results for Max-Ek-Sat for k 3, maximizing the number of satised linear equations in an over-determined system of linear equations modulo a prime p and Set Splitting. As a consequence of these results we get improved lower bounds for the efficient approximability of many optimization problems studied previously. In particular, for Max-E2-Sat, Max-Cut, Max-di-Cut, and Vertex cover. |
| File Format | |
| Publisher Date | 2002-01-01 |
| Access Restriction | Open |
| Subject Keyword | Set Splitting Many Optimization Problem Efficient Approximability Over-determined System Satised Linear Equation Vertex Cover Optimal Inapproximability Result Inapproximability Result |
| Content Type | Text |
