Reading Randomized Rounding without Solving the Linear Program paper I came across this definition:

Let $P$ be a convex set in $\mathbb{R}^n$ and let $f$ be a linear function (not necessarily homogeneous) from $P$ to $\mathbb{R}^m$.

Correct me if I am wrong, but $f$ is a non-homogenous function that takes a set of points in $\mathbb{R}^n$ and returns a set of points in $\mathbb{R}^m$?


1 Answer 1


A homogeneous function $f$ satisfies $f(ax)=af(x)$ for scalars.

When $f(x)=Ax+b$ is linear, this is to say that $b=0$. So a non-homogeneous linear function may have a non-zero constant vector term.

So in your case, $f$ may or may not be homogeneous/non-homogeneous. Strictly speaking it doesn't map $\mathbb{R}^n\to\mathbb{R}^m$, it maps $P\to\mathbb{R}^m$. But since $f$ is linear, the extension is a natural one, and it makes good sense to just think of it as mapping $\mathbb{R}^n\to\mathbb{R}^m$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .