Nonlinear optimization for matroid intersection and extensions

Details Nonlinear optimization for matroid intersection and extensions Nonlinear optimization for matroid intersection and extensions

2008-07-24

arxiv.org/abs/0807.3907v1

Mathematics

Combinatorics

Scientific paper

We address optimization of nonlinear functions of the form $f(Wx)$, where $f:\R^d\to \R$ is a nonlinear function, $W$ is a $d\times n$ matrix, and feasible $x$ are in some large finite set $F$ of integer points in $\R^n$. One motivation is multi-objective discrete optimization, where $f$ trades off the linear functions given by the rows of $W$. Another motivation is to extend known results about polynomial-time linear optimization over discrete structures to nonlinear optimization. We assume that the convex hull of $F$ is well-described by linear inequalities. For example, the set of characteristic vectors of common bases of a pair of matroids on a common ground set. When $F$ is well described, $f$ is convex (or even quasiconvex), and $W$ has a fixed number of rows and is unary encoded or with entries in a fixed set, we give an efficient deterministic algorithm for maximization. When $F$ is well described, $f$ is a norm, and binary-encoded $W$ is nonnegative, we give an efficient deterministic constant-approximation algorithm for maximization. When $F$ is well described, $f$ is ``ray concave'' and non-decreasing, and $W$ has a fixed number of rows and is unary encoded or with entries in a fixed set, we give an efficient deterministic constant-approximation algorithm for minimization. When $F$ is the set of characteristic vectors of common bases of a pair of vectorial matroids on a common ground set, $f$ is arbitrary, and $W$ has a fixed number of rows and is unary encoded, we give an efficient randomized algorithm for optimization.

Affiliated with

Also associated with

No associations

Rating

Nonlinear optimization for matroid intersection and extensions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Nonlinear optimization for matroid intersection and extensions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nonlinear optimization for matroid intersection and extensions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-676910