0
$\begingroup$

I have an exercise that tells me that, given a problem P (of which now I omit the description) there is no integrality gap between LP and ILP formulation of this problem, and for every fractional LP-solution, there exists an integral feasible solution with the same cost. Then I have to design a poly-time algorithm that from any given optimal LP-solution, computes such an optimal integer assignment.

The fact that there is integrality gap what does it mean in this case? I mean, if I design an approximation-algorithm to compute an optimal integer assignment from a given optimal LP-solution, I will get a solution with object value like something * Optimal value of LP problem . Isn't this in contrast with the fact that there's no IG? It should mean that the optimal value of LP and ILP should be the same, no?

Please, clarify my doubts.

EDIT: Michele is very interested in fashion and owns a whole bunch of nice outfits, collectively forming the set O. A set F of his friends all want to borrow one of Michele’s outfits to go to a wedding. This should be doable, since |F| ≤ |O|. However, due to different restrictions like size, body form, or adjustements that have to be made to an outfit to really look wedding-appropriate, there will be some extra effort w(f, o) ≥ 0 required when any friend f wants to wear outfit o. Of course, Michele would like to keep the overall effort to a minimum. a) Model the problem as an integer linear program, and relax this to a corresponding LP. b) Usually, the optimal solution to a problem’s LP-relaxation is better than that of the original ILP. The factor by which both can differ is called the integrality gap. For Michele’s problem, there is no such gap and for every fractional LP-solution, there exists an integral feasible solution with the same cost. Give a polynomial-time algorithm that, from any given optimal LP-solution, computes such an optimal integer assignmen

$\endgroup$
7
  • $\begingroup$ "For every fractional LP-solution, there exists an integral feasible solution with the same cost." Are you sure about this statement? It should be impossible unless the feasible region is a single point $\endgroup$ Dec 28 '19 at 18:11
  • $\begingroup$ The last paragraph is not very well formatted. Can you please edit your question and make it more clear. $\endgroup$ Dec 28 '19 at 18:14
  • $\begingroup$ Well I'm sorry more than you because that is exactly what the exercise says, I don't know how to make this more clear, it is all I have. The problem is an assignment one, if this can help you to understand. Given two sets N and M, with |N| <= |M| and a function cost between these, I have to minimize the total cost having all |N| elements matched with some of M. $\endgroup$ Dec 28 '19 at 18:17
  • $\begingroup$ do you have a link to the exercise? $\endgroup$ Dec 28 '19 at 18:18
  • $\begingroup$ I edited for the complete exercise $\endgroup$ Dec 28 '19 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.