Loading...
Please wait, while we are loading the content...
Similar Documents
2 Min-Knapsack and the Knapsack Cover Inequalities
| Content Provider | Semantic Scholar |
|---|---|
| Author | Dinitz, Michael |
| Copyright Year | 2019 |
| Abstract | Today we’re going to talk about a topic that we probably should have done earlier in the semester when we were talking about LPs. My apologies for the somewhat poor planning. But it’s also motivated by an observation that we made last class about the SDP relaxation for Correlation Clustering where we had to add vi · vj ≥ 0 constraints in order to make the algorithm and analysis work. Another interpretation was that if we started without those constraints, the SDP was actually a poor (though valid) relaxation for the vector program that we actually wanted to solve. But we could fix this by adding more valid constraints: constraints which are true for any feasible solution of the original problem, but which might not appear in the “obvious” relaxation. It turns out that this is generally a useful thing to think about: if we’re given an LP or SDP which is a poor relaxation (it has large integrality gap or we don’t know how to round it), we can try to add valid inequalities to make it a better or easier to handle relaxation. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.jhu.edu/~mdinitz/classes/ApproxAlgorithms/Spring2019/Lectures/lecture24.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
