rapid-communication

Characterizations of the set of integer points in an integral bisubmodular polyhedron

Author:

Yuni IwamasaAuthors Info & Claims

Volume 347, Issue 4

https://doi.org/10.1016/j.disc.2023.113855

Published: 25 June 2024 Publication History

Abstract

In this note, we provide two characterizations of the set of integer points in an integral bisubmodular polyhedron. Our characterizations do not require the assumption that a given set satisfies the hole-freeness, i.e., the set of integer points in its convex hull coincides with the original set. One is a natural multiset generalization of the exchange axiom of a delta-matroid, and the other comes from the notion of the tangent cone of an integral bisubmodular polyhedron.

References

[1]

K. Ando, S. Fujishige, On structures of bisubmodular polyhedra, Math. Program. 74 (1996) 293–317.

[2]

K. Ando, S. Fujishige, T. Naitoh, A greedy algorithm for minimizing a separable convex function over an integral bisubmodular polyhedron, J. Oper. Res. Soc. Jpn. 37 (3) (1994) 188–196.

[3]

G. Appa, B. Kotnyek, A bidirected generalization of network matrices, Networks 47 (4) (2006) 185–198.

[4]

A.V. Borovik, I.M. Gelfand, N. White, Coxeter Matroids, Birkhäuser Boston, Boston, MA, 2003.

[5]

A. Bouchet, Greedy algorithm and symmetric matroids, Math. Program. 38 (1987) 147–159.

[6]

A. Bouchet, W.H. Cunningham, Delta-matroids, jump systems, and bisubmodular polyhedra, SIAM J. Discrete Math. 8 (1) (1995) 17–32.

[7]

R. Chandrasekaran, S.N. Kabadi, Pseudomatroids, Discrete Math. 71 (1988) 205–217.

[8]

A. Dress, T.F. Havel, Some combinatorial properties of discriminants in metric vector spaces, Adv. Math. 62 (1986) 285–312.

[9]

S. Fujishige, A min-max theorem for bisubmodular polyhedra, SIAM J. Discrete Math. 10 (2) (1995) 294–308.

[10]

S. Fujishige, Submodular Functions and Optimization, 2nd edition, Elsevier, Amsterdam, 2005.

[11]

S. Fujishige, Bisubmodular polyhedra, simplicial divisions, and discrete convexity, Discrete Optim. 12 (2014) 115–120.

[12]

K. Murota, Convexity and Steinitz's exchange property, Adv. Math. 124 (1996) 272–311.

[13]

K. Murota, Discrete Convex Analysis, SIAM, Philadelphia, 2003.

[14]

L. Qi, Directed submodularity, ditroids and directed submodular flows, Math. Program. 42 (1988) 579–599.

[15]

R.T. Rockafellar, Convex Analysis, Princeton University Press, 1970.

Recommendations

Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra

This paper relates an axiomatic generalization of matroids, called a jump system, to polyhedra arising from bisubmodular functions. Unlike the case for usual submodularity, the points of interest are not all the integral points in the relevant ...
The Integer Knapsack Cover Polyhedron

We study the integer knapsack cover polyhedron which is the convex hull of the set of vectors $x\in \mathbb{Z}_{+}^{n}$ that satisfy $C^{T}x\geq b$, with $C\in \mathbb{Z}_{++}^{n}$ and $b\in \mathbb{Z}_{++}$. We present some general results about the ...
On the facets of the mixed---integer knapsack polyhedron

We study the mixed---integer knapsack polyhedron, that is, the convex hull of the mixed---integer set defined by an arbitrary linear inequality and the bounds on the variables. We describe facet---defining inequalities of this polyhedron that can be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete Mathematics

Discrete Mathematics Volume 347, Issue 4

Apr 2024

575 pages

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 25 June 2024

Author Tags

Qualifiers

Rapid-communication

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents