Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor(s)

Author(s):

Boros, Endre
Elbassioni, Khaled M.
Khachiyan, Leonid
Gurvich, Vladimir

dblp
dblp
dblp
dblp

Not MPG Author(s):

Boros, Endre
Gurvich, Vladimir
Khachiyan, Leonid

BibTeX cite key*:

Elbassioni2003a

Title

Title*:

An Inequality for Polymatroid Functions and its Applications

Journal

Journal Title*:

Discrete Applied mathematics

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

131

Number:


Publishing Date:

2003

Pages*:

27

Number of
VG Pages:


Page Start:

255

Page End:

281

Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

An integral-valued set function $f:2^V \mapsto \ZZ$ is called
polymatroid if it is submodular, non-decreasing, and
$f(\emptyset)=0$. Given a polymatroid function $f$
and an integer threshold $t\geq 1$, let $\alpha=\alpha(f,t)$ denote the number of maximal sets $X \subseteq V$ satisfying $f(X) < t$, let $\beta=\beta(f,t)$ be the number of minimal sets $X \subseteq V $ for which $f(X) \ge t$,
and let $n=|V|$. We show that if $\beta \ge 2$ then $\alpha \le
\beta^{(\log t)/c}$, where $c=c(n,\beta)$ is the unique positive root of the equation $1=2^c(n^{c/\log\beta}-1)$.
In particular, our bound implies that $\alpha \le (n\beta)^{\log t}$ for all $\beta \ge 1$. We also give examples of polymatroid functions with arbitrarily large $t, n, \alpha$ and $\beta$ for which $\alpha \ge \beta^{(.551 \log t)/c}$.
More generally, given a polymatroid function $f:2^V \mapsto \ZZ$
and an integral threshold $t \ge 1$, consider an arbitrary
hypergraph $\cH$ such that $|\cH| \ge 2$ and $f(H) \ge t$ for all
$H \in \cH$. Let $\cS$ be the family of all maximal independent
sets $X$ of $\cH$ for which $f(X) <t$. Then $|\cS| \leq
|\cH|^{(\log t)/c(n,|\cH|)}$. As an application, we show that
given a system of polymatroid inequalities $f_1(X) \ge
t_1,\ldots,f_m(X) \ge t_m$ with quasi-polynomially bounded right
hand sides $t_1,\ldots,t_m$, all minimal feasible solutions to
this system can be generated in incremental quasi-polynomial time. In contrast to this result, the generation of all maximal
infeasible sets is an NP-hard problem for many polymatroid
inequalities of small range.

URL for the Abstract:


Categories,
Keywords:

dualization, incremental algorithm, independent set, matroid, submodular function, polymatroid function, system of polymatroid inequalities, transversal hypergraph

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{Elbassioni2003a,
AUTHOR = {Boros, Endre and Elbassioni, Khaled M. and Khachiyan, Leonid and Gurvich, Vladimir},
TITLE = {An Inequality for Polymatroid Functions and its Applications},
JOURNAL = {Discrete Applied mathematics},
PUBLISHER = {Elsevier},
YEAR = {2003},
VOLUME = {131},
PAGES = {27},
}


Entry last modified by Christine Kiesel, 07/15/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
02/22/2005 06:41:34 PM
Revisions
2.
1.
0.

Editor(s)
Christine Kiesel
Khaled Elbassioni
Khaled Elbassioni

Edit Dates
02.05.2007 15:40:17
04/20/2006 06:41:29 PM
02/22/2005 06:41:34 PM