English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Borradaile et al. (2017) investigated orientations of an undirected graph inwhich the sequence of in-degrees of the nodes is lexicographically minimal,which we call decreasingly minimal (=dec-min). They proved that an orientationis dec-min if and only if there is no dipath from $s$ to $t$ with in-degrees$\varrho (t) \geq \varrho (s)+2$. They conjectured that an analogous statementholds for strongly connected dec-min orientations, as well. We prove not onlythis conjecture but its extension to $k$-edge-connected orientations, as well.We also provide a solution to a discrete version of Megiddo's lexicographicallyoptimal (fractional) network flow problem (1974, 1977).  Our main goal is to integrate these cases into a single framework. Namely, wecharacterize dec-min elements of an M-convex set (which is nothing but the setof integral points of an integral base-polyhedron), and prove that the set ofdec-min elements is a special M-convex set arising from a matroidbase-polyhedron by translation. The topic of our investigations may beinterpreted as a discrete counter-part of the work by Fujishige (1980) on the(unique) lexicographically optimal base of a base-polyhedron. We also exhibit acanonical chain (and partition) associated with a base-polyhedron. We also showthat dec-min elements of an M-convex set are exactly those which minimize thesquare-sum of components, and describe a new min-max formula for the minimumsquare-sum. Our approach gives rise to a strongly polynomial algorithm forcomputing a dec-min element, as well as the canonical chain. The algorithmrelies on a submodular function minimizer oracle in the general case, whichcan, however, be replaced by more efficient classic flow- and matroidalgorithms in the relevant special cases.

Discrete Decreasing Minimization, Part I: Base-polyhedra with Applications in Network Optimization