Search

We show the existence of a polynomial-size extended formulation for the base polytope of a $$(k,\ell )$$ -sparsity matroid. For an undirected graph $$G=(V,E)$$ , the size of the formulation is $$O(|V|\cdot |E|)$$ when $$k \ge \ell $$ and $$O(|V|^2 |E|)$$ when $$k \le \ell $$ . To this end, we employ the technique developed by Faenza et al. recently that uses a randomized communication protocol. [ABSTRACT FROM AUTHOR]

We introduce polylinking networks, which is a flow model based on polylinking systems that generalizes the classical flow model of Ford and Fulkerson on acyclic networks and has applications in the context of wireless networks. More precisely, a flow model recently introduced by Avestimehr et al. (Proceedings of the Allerton conference on communication, control, and computing ) used in the context of wireless information networks is a special case of the presented model. We define a notion of source-destination cut and derive a max-flow min-cut theorem. Additionally, we present various properties of polylinking networks that can be seen as generalizations of properties for classical flows. Using submodular function minimization and submodular flow algorithms, one can efficiently determine a maximum flow, a minimum source-destination cut, as well as a minimum cost flow. These algorithms lead to new efficient algorithms for the information flow model. [ABSTRACT FROM AUTHOR]

Modern modeling approaches for circuit analysis lead to differential-algebraic equations (DAEs). The index of a DAE is a measure of the degree of numerical difficulty. In general, the higher the index is, the more difficult it is to solve the DAE. The index of the DAE arising from the modified nodal analysis (MNA) is determined uniquely by the structure of the circuit. Instead, we consider a broader class of analysis method called the hybrid analysis. For linear time-invariant electric circuits, we devise a combinatorial algorithm for finding an optimal hybrid analysis in which the index of the DAE to be solved attains the minimum. The optimal hybrid analysis often results in a DAE with lower index than MNA. [ABSTRACT FROM AUTHOR]