If I am given an optimization problem $L$, and a problem instance of $L$, which is of size $(m,n)$ (i.e. it depends on more than one parameter) then what does it mean to have, let's say, a linear-approximation algorithm?

Do I then mention whether it is linear in $m$ or $n$?

On the other hand I might be allowed to set $m$ equal to $n$ and thereby I would be obsolete to mention in which parameter the problem is linearly approximated.

  • $\begingroup$ By a "linear-approximation algorithm" do you mean an approximation algorithm running in linear time? Then, I see nothing special for approximation algorithms, but you'd be just referring to running time. $\endgroup$ Dec 31 '11 at 10:18
  • $\begingroup$ @Yoshio Okamoto I was unprecise: I didn't mean the running time but the approximation factor. $\endgroup$
    – 101011
    Dec 31 '11 at 10:48
  • $\begingroup$ Thanks a lot for the clarification. Do you have a concrete example of such an approximation algorithm in mind? $\endgroup$ Dec 31 '11 at 12:15

This is not an answer, but rather a personal experience. I'll post it as an answer since it's too long to be a comment.

If I would be an author, I wouldn't use the expression like "linear-approximation" since it's confusing.

I haven't seen an expression like "linear-approximation" or "logarithmic-approximation" for referring to approximation ratios. For example, the greedy algorithm for the minimum set cover problem is an $H(n)$-approximation algorithm, where $H(n)$ is the $n$-th Harmonic number, but I haven't seen it's called a logarithmic-approximation algorithm. Here, $n$ is the size of a universe, and this should be explained in the definition of the problem. Please note that $n$ is not the input size.

There's one exception. In the book "Complexity and Approximation" by Ausiello, Crescenzi, Gambosi, Kann, Marchetti-Spaccamela, and Protasi, I can find expressions like log-APX, poly-APX and exp-APX. For example, log-APX refers to the class of NP optimization problems that have an $O(\log n)$-approximation algorithm, where $n$ is the input size.

Some authors use "a linear approximation algorithm" to mean a linear-time approximation algorithm. I feel this is still confusing, and I would write linear-time approximation. People tend to omit "time", and for example when they write "a polynomial algorithm", they often mean a polynomial-time algorithm.

  • $\begingroup$ it's entirely possible I misunderstood the question, and 'linear approximation' is as you indicate. $\endgroup$ Dec 31 '11 at 20:35
  • $\begingroup$ @SureshVenkat: Please look at the comment by user695652 right below the question for clarification. $\endgroup$ Jan 1 '12 at 0:17
  • $\begingroup$ Ah. I should probably delete my answer then. $\endgroup$ Jan 1 '12 at 6:32
  • $\begingroup$ I've changed my answer accordingly. Thank you. $\endgroup$ Jan 1 '12 at 8:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.