Let us assume that we have the following (non linear) program :

R = min { ( (c1^T)*x + d1 ) / ( (c2^T)x + d2 ) : Ax<=b , (c2^T)*x+d2>0}

We also assume that the feasible solution area is bounded and that the objective value of the optimal solution belongs to [L,U].

We assume that we know a δ >0 , so that for every feasible solution x , ( c2^T)*x >= δ .

How can I prove that for every ε > 0 there is an ( 1 + ε) approximation of the solution of R? ( We can use a linear programming algorithm as subroutine). In addition , which is the time complexity of that algorithm?

  • 1
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Apr 17 '17 at 19:48
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – D.W. Apr 18 '17 at 2:39

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.