# approximating problems described by multiple parameters

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.

• 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. Dec 31 '11 at 10:18
• @Yoshio Okamoto I was unprecise: I didn't mean the running time but the approximation factor. Dec 31 '11 at 10:48
• Thanks a lot for the clarification. Do you have a concrete example of such an approximation algorithm in mind? 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.

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