Nonlinear optimization for matroid intersection and extensions

MaRDI QIDQ6210358zbMATH OpenFDO

Authors Yael Berstein, Jon Lee, Shmuel Onn, Robert Weismantel

Publication date 24 July 2008

Mathematics Subject Classification ID

Enumerative combinatorics (05Axx) Basic linear algebra (15Axx) Real and complex geometry (51Mxx) General convexity (52Axx) Polytopes and polyhedra (52Bxx) Discrete geometry (52Cxx) Multivariate analysis (62Hxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Computing methodologies and applications (68Uxx) Algorithms in computer science (68Wxx) Operations research and management science (90Bxx) Mathematical programming (90Cxx)

Abstract: We address optimization of nonlinear functions of the form $f(Wx)$, where $f:R^{d}oR$ is a nonlinear function, $W$ is a $dimesn$ 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.

This page was built for publication: Nonlinear optimization for matroid intersection and extensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6210358)