dc.contributor.author Berstein, Yael dc.contributor.author Lee, Jon dc.contributor.author Onn, Shmuel dc.contributor.author Weismantel, Robert dc.date.accessioned 2008-03-20T12:00:22Z dc.date.accessioned 2016-10-05T14:14:09Z dc.date.available 2008-03-20T12:00:22Z dc.date.available 2016-10-05T14:14:09Z dc.date.issued 2008-03-17 dc.identifier.uri http://publications.mfo.de/handle/mfo/1134 dc.description Research in Pairs 2007 en_US dc.description.abstract We address optimization of nonlinear functions of the form $f(W_x)$ , where $f : \mathbb{R}^d \to \mathbb{R}$ is a nonlinear function, $W$ is a $d \times n$ matrix, and feasible $x$ are in some large finite set $\mathcal{F}$ of integer points in $\mathbb{R}^n$ . Generally, such problems are intractable, so we obtain positive algorithmic results by looking at broad natural classes of $f$, $W$ and $\mathcal{F}$. One of our main motivations is multi-objective discrete optimization, where $f$ trades off the linear functions given by the rows of $W$ . Another motivation is that we want to extend as much as possible the known results about polynomial-time linear optimization over trees, assignments, matroids, polymatroids, etc. to nonlinear optimization over such structures. We assume that the convex hull of $\mathcal{F}$ is well-described by linear inequalities (i.e., we have an efficient separation oracle). For example, the set of characteristic vectors of common bases of a pair of matroids on a common ground set satisfies this property for $\mathcal{F}$. In this setting, the problem is already known to be intractable (even for a single matroid), for general $f$ (given by a comparison oracle), for (i) $d = 1$ and binary-encoded $W$, and for (ii) $d = n$ and $W = I$. dc.language.iso en en_US dc.publisher Mathematisches Forschungsinstitut Oberwolfach en_US dc.relation.ispartofseries Oberwolfach Preprints;2008,14 dc.title Nonlinear Optimization for Matroid Intersection and Extensions en_US dc.type Preprint en_US dc.rights.license Dieses Dokument darf im Rahmen von § 53 UrhG zum eigenen Gebrauch kostenfrei heruntergeladen, gelesen, gespeichert und ausgedruckt, aber nicht im Internet bereitgestellt oder an Außenstehende weitergegeben werden. de dc.rights.license This document may be downloaded, read, stored and printed for your own use within the limits of § 53 UrhG but it may not be distributed via the internet or passed on to external parties. en dc.identifier.doi 10.14760/OWP-2008-14 local.scientificprogram Research in Pairs 2007 local.series.id OWP-2008-14 dc.identifier.urn urn:nbn:de:101:1-2008111299 dc.identifier.ppn 1647467802
﻿