<p>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.</p>

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

<p>I haven't seen an expression like "linear-approximation" or "logarithmic-approximation" for referring to approximation ratios.  For example, the greedy algorithm for <a href="http://en.wikipedia.org/wiki/Set_cover_problem" rel="nofollow">the minimum set cover problem</a> 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.</p>

<p>There's one exception.  In <a href="http://www.csc.kth.se/~viggo/approxbook/" rel="nofollow">the book "Complexity and Approximation" by Ausiello, Crescenzi, Gambosi, Kann, Marchetti-Spaccamela, and Protasi</a>, 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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-12-31T20:35:53.770Z
it's entirely possible I misunderstood the question, and 'linear approximation' is as you indicate.
Suresh Venkat
CC BY-SA 3.0
2012-01-01T00:17:30.247Z
@SureshVenkat: Please look at the comment by user695652 right below the question for clarification.
Yoshio Okamoto
CC BY-SA 3.0
2012-01-01T06:32:46.950Z
Ah. I should probably delete my answer then.
Suresh Venkat
CC BY-SA 3.0
2012-01-01T08:50:22.370Z
I've changed my answer accordingly.  Thank you.
Yoshio Okamoto
CC BY-SA 3.0
2011-12-31T16:19:19.230Z
2012-01-01T08:46:48.513Z
2012-01-01T08:46:48.513Z
Yoshio Okamoto
<p>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?</p>

<p>Do I then mention whether it is linear in $m$ or $n$?</p>

<p>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.</p>

CC BY-SA 3.0
2011-12-31T10:18:05.667Z
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.
Yoshio Okamoto
CC BY-SA 3.0
2011-12-31T10:48:20.163Z
@Yoshio Okamoto  I was unprecise: I didn't mean the running time but the approximation factor.
101011
CC BY-SA 3.0
2011-12-31T12:15:32.800Z
Thanks a lot for the clarification.  Do you have a concrete example of such an approximation algorithm in mind?
Yoshio Okamoto
<ds.algorithms><approximation-algorithms>
approximating problems described by multiple parameters
101011
# approximating problems described by multiple parameters

(Asked by: username_0 on 2011-12-30)

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.

**Tags:** ds.algorithms, approximation-algorithms
> **Comments:**
> **username_1**: 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.  
> **username_0**: @Yoshio Okamoto  I was unprecise: I didn't mean the running time but the approximation factor.  
> **username_1**: Thanks a lot for the clarification.  Do you have a concrete example of such an approximation algorithm in mind?  

---

## 1 answers

### Answer by username_1 on 2011-12-31. Score: 5 | Accepted answer

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](http://en.wikipedia.org/wiki/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](http://www.csc.kth.se/~viggo/approxbook/), 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.

> **Comments:**
> **username_2**: it's entirely possible I misunderstood the question, and 'linear approximation' is as you indicate.  
> **username_1**: @SureshVenkat: Please look at the comment by user695652 right below the question for clarification.  
> **username_2**: Ah. I should probably delete my answer then.  
> **username_1**: I've changed my answer accordingly.  Thank you.  

---

