Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow/circulation
- NSF-PAR ID:
- 10410649
- Date Published:
- Journal Name:
- Forum of Mathematics, Pi
- Volume:
- 11
- ISSN:
- 2050-5086
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
X on a directed graphG into weighted source-to-sink paths whose weighted sum equalsX . We show that, for acyclic graphs, considering thewidth of the graph (the minimum number of paths needed to cover all of its edges) yields advances in our understanding of its approximability. For the version of the problem that uses only non-negative weights, we identify and characterise a new class ofwidth-stable graphs, for which a popular heuristic is aO (logVal (X ))-approximation (Val (X ) being the total flow ofX ), and strengthen its worst-case approximation ratio from\(\Omega (\sqrt {m})\) m /logm ) for sparse graphs, wherem is the number of edges in the graph. We also study a new problem on graphs with cycles, Minimum Cost Circulation Decomposition (MCCD), and show that it generalises MFD through a simple reduction. For the version allowing also negative weights, we give a (⌈ log ‖ X ‖ ⌉ +1)-approximation (‖X ‖ being the maximum absolute value ofX on any edge) using a power-of-two approach, combined with parity fixing arguments and a decomposition of unitary circulations (‖X ‖ ≤ 1), using a generalised notion of width for this problem. Finally, we disprove a conjecture about the linear independence of minimum (non-negative) flow decompositions posed by Kloster et al. [2018 ], but show that its useful implication (polynomial-time assignments of weights to a given set of paths to decompose a flow) holds for the negative version. -
We give a new operator formula for Grothendieck polynomials that generalizes Magyar’s Demazure operator formula for Schubert polynomials. Our proofs are purely combinatorial, contrasting with the geometric and representation theoretic tools used by Magyar. We apply our formula to prove a necessary divisibility condition for a monomial to appear in a given Grothendieck polynomial.more » « less
-
Tauman Kalai, Yael (Ed.)Over the last two decades, a significant line of work in theoretical algorithms has made progress in solving linear systems of the form 𝐋𝐱 = 𝐛, where 𝐋 is the Laplacian matrix of a weighted graph with weights w(i,j) > 0 on the edges. The solution 𝐱 of the linear system can be interpreted as the potentials of an electrical flow in which the resistance on edge (i,j) is 1/w(i,j). Kelner, Orrechia, Sidford, and Zhu [Kelner et al., 2013] give a combinatorial, near-linear time algorithm that maintains the Kirchoff Current Law, and gradually enforces the Kirchoff Potential Law by updating flows around cycles (cycle toggling). In this paper, we consider a dual version of the algorithm that maintains the Kirchoff Potential Law, and gradually enforces the Kirchoff Current Law by cut toggling: each iteration updates all potentials on one side of a fundamental cut of a spanning tree by the same amount. We prove that this dual algorithm also runs in a near-linear number of iterations. We show, however, that if we abstract cut toggling as a natural data structure problem, this problem can be reduced to the online vector-matrix-vector problem (OMv), which has been conjectured to be difficult for dynamic algorithms [Henzinger et al., 2015]. The conjecture implies that the data structure does not have an O(n^{1-ε}) time algorithm for any ε > 0, and thus a straightforward implementation of the cut-toggling algorithm requires essentially linear time per iteration. To circumvent the lower bound, we batch update steps, and perform them simultaneously instead of sequentially. An appropriate choice of batching leads to an Õ(m^{1.5}) time cut-toggling algorithm for solving Laplacian systems. Furthermore, we show that if we sparsify the graph and call our algorithm recursively on the Laplacian system implied by batching and sparsifying, we can reduce the running time to O(m^{1 + ε}) for any ε > 0. Thus, the dual cut-toggling algorithm can achieve (almost) the same running time as its primal cycle-toggling counterpart.more » « less
-
Abstract We prove the extended delta conjecture of Haglund, Remmel and Wilson, a combinatorial formula for $\Delta _{h_l}\Delta ' _{e_k} e_{n}$ , where $\Delta ' _{e_k}$ and $\Delta _{h_l}$ are Macdonald eigenoperators and $e_n$ is an elementary symmetric function. We actually prove a stronger identity of infinite series of $\operatorname {\mathrm {GL}}_m$ characters expressed in terms of LLT series. This is achieved through new results in the theory of the Schiffmann algebra and its action on the algebra of symmetric functions.more » « less
-
more » « less
Abstract Designing an algorithm with a singly exponential complexity for computing semialgebraic triangulations of a given semialgebraic set has been a holy grail in algorithmic semialgebraic geometry. More precisely, given a description of a semialgebraic set
$S \subset \mathbb {R}^k$ $\Delta $ $|\Delta |$ S . In this paper, we consider a weaker version of this question. We prove that for any$\ell \geq 0$ $S \subset \mathbb {R}^k$ $\phi $ $\Delta $ $|\Delta |$ $\ell $ S . The complexity of our algorithm is bounded by$(sd)^{k^{O(\ell )}}$ s is the number of polynomials appearing in the formula$\phi $ d a bound on their degrees. For fixed$\ell $ singly exponential ink . In particular, since$\ell $ homotopy groups up to dimension$\ell $ $|\Delta |$ S , we obtain a reduction (having singly exponential complexity) of the problem of computing the first$\ell $ S to the combinatorial problem of computing the first$\ell $ $(sd)^{k^{O(\ell )}}$
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/fmp.2023.4
