Please use this identifier to cite or link to this item:
https://oa.tib.eu/renate/handle/123456789/2677
Files in This Item:
File | Size | Format | |
---|---|---|---|
OWP2008_14.pdf | 261,9 kB | Adobe PDF | View/Open |
Title: | Nonlinear optimization for matroid intersection and extensions |
Authors: | Berstein, Yael; Lee, Jon; Onn, Shmuel; Weismantel, Robert |
Publishers version: | https://doi.org/10.14760/OWP-2008-14 |
URI: | https://doi.org/10.34657/2744 https://oa.tib.eu/renate/handle/123456789/2677 |
Issue Date: | 2008 |
Published in: | Oberwolfach preprints (OWP), Volume 2008-14, ISSN 1864-7596 |
Journal: | Oberwolfach Preprints (OWP) |
Volume: | 2008-14 |
Publisher: | Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach |
Abstract: | We address optimization of nonlinear functions of the form f(Wx) , where f : Rd ! R is a nonlinear function, W is a d × n matrix, and feasible x are in some large finite set F of integer points in Rn . Generally, such problems are intractable, so we obtain positive algorithmic results by looking at broad natural classes of f , W and 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 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 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 . Our main results (a few technicalities suppressed): 1- 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. 2- 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. 3- 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 constantapproximation algorithm for minimization. 4- 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. |
Type: | report; Text |
Publishing status: | publishedVersion |
DDC: | 510 |
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. 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. |
Appears in Collections: | Mathematik |
Show full item record
Berstein, Yael, Jon Lee, Shmuel Onn and Robert Weismantel, 2008. Nonlinear optimization for matroid intersection and extensions. Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach
Berstein, Y., Lee, J., Onn, S. and Weismantel, R. (2008) Nonlinear optimization for matroid intersection and extensions. Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach. doi: https://doi.org/10.14760/OWP-2008-14.
Berstein Y, Lee J, Onn S, Weismantel R. Nonlinear optimization for matroid intersection and extensions. Vol. 2008-14. Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach; 2008.
Berstein, Y., Lee, J., Onn, S., & Weismantel, R. (2008). Nonlinear optimization for matroid intersection and extensions (Version publishedVersion, Vol. 2008-14). Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach. https://doi.org/https://doi.org/10.14760/OWP-2008-14
Berstein Y, Lee J, Onn S, Weismantel R. Nonlinear optimization for matroid intersection and extensions. Vol. 2008-14. Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach; 2008. doi:https://doi.org/10.14760/OWP-2008-14
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.