Search

Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow/circulation X on a directed graph G into weighted source-to-sink paths whose weighted sum equals X. We show that, for acyclic graphs, considering the width 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 of width-stable graphs, for which a popular heuristic is a O(log Val (X))-approximation (Val(X) being the total flow of X), and strengthen its worst-case approximation ratio from \(\Omega (\sqrt {m})\) to Ω (m/log m) for sparse graphs, where m 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 of X 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. [ABSTRACT FROM AUTHOR]

Genome assembly asks to reconstruct an unknown string from many shorter substrings of it. Even though it is one of the key problems in Bioinformatics, it is generally lacking major theoretical advances. Its hardness stems both from practical issues (size and errors of real data), and from the fact that problem formulations inherently admit multiple solutions. Given these, at their core, most state-of-the-art assemblers are based on finding non-branching paths (unitigs) in an assembly graph. While such paths constitute only partial assemblies, they are likely to be correct. More precisely, if one defines a genome assembly solution as a closed arc-covering walk of the graph, then unitigs appear in all solutions, being thus safe partial solutions. Until recently, it was open what are all the safe walks of an assembly graph. Tomescu and Medvedev (RECOMB 2016) characterized all such safe walks (omnitigs), thus giving the first safe and complete genome assembly algorithm. Even though maximal omnitig finding was later improved to quadratic time by Cairo et al. (ACM Trans. Algorithms 2019), it remained open whether the crucial linear-time feature of finding unitigs can be attained with omnitigs. We answer this question affirmatively, by describing a surprising O(m)-time algorithm to identify all maximal omnitigs of a graph with n nodes and m arcs, notwithstanding the existence of families of graphs with Θ (mn) total maximal omnitig size. This is based on the discovery of a family of walks (macrotigs) with the property that all the non-trivial omnitigs are univocal extensions of subwalks of a macrotig. This has two consequences: (1) A linear-time output-sensitive algorithm enumerating all maximal omnitigs. (2) A compact O(m) representation of all maximal omnitigs, which allows, e.g., for O(m)-time computation of various statistics on them. Our results close a long-standing theoretical question inspired by practical genome assemblers, originating with the use of unitigs in 1995. We envision our results to be at the core of a reverse transfer from theory to practical and complete genome assembly programs, as has been the case for other key Bioinformatics problems. [ABSTRACT FROM AUTHOR]

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.07.020 Byline: Stefano Benati (a), Romeo Rizzi (b) Keywords: Portfolio optimization; Complexity theory; Linear integer programming Abstract: In this paper, we consider an extension of the Markovitz model, in which the variance has been replaced with the Value-at-Risk. So a new portfolio optimization problem is formulated. We showed that the model leads to an NP-hard problem, but if the number of past observation T or the number of assets K are low, e.g. fixed to a constant, polynomial time algorithms exist. Furthermore, we showed that the problem can be formulated as an integer programming instance. When K and T are large and [alpha].sup.VaR is small -- as common in financial practice -- the computational results show that the problem can be solved in a reasonable amount of time. Author Affiliation: (a) Dipartimento di Informatica e Studi Aziendali, Universita di Trento, Via Inama 5, 38100 Trento, Italy (b) Dipartimento di Informatica e Telecomunicazioni, Universita di Trento, Via Sommarie 14, 38100 Trento, Italy Article History: Received 29 April 2004; Accepted 6 July 2005

A 'simulation program with integrated circuit emphasis' (SPICE) model for the evaluation, in frequency and time domain, of the coupling of a bundle of shielded coaxial cables with an external electromagnetic source such as a bulk current injection clamp, is developed. The proposed equivalent circuit takes into account the presence of the transfer impedance and the presence of the transfer admittance, and it does not need the subdivision in elementary cells. Intermediate results are validated by comparing the exact numerical solutions with the output of the SPICE circuit, and the final results are validated by means of comparison with measurements carried out on an experimental setup. The feature selective validation (FSV) technique is used as a measure of the comparisons. Index Terms--Bundles, coaxial cables, feature selective validation (FSV), simulation program with integrated circuit emphasis (SPICE) model, transfer admittance, transfer impedance.

A novel simulation approach for hypercubes on to the partitioned optical passive stars (POPS) network is proposed. The results of the study imply a novel algorithm for solving the fundamental prefix sums problem on the POPS network, improving even on the best ad hoc algorithm known so far, and as a by-product, algorithms for other important problems are similarly improved, proving that the strength of the simulation, can be used to move the extremely rich and complex class of hypercube algorithms towards efficient implementation on the POPS network.