Search

The famous edge flow decomposition theorem of Gallai (1958) states that any static edge $s$,$d$-flow in a directed graph can be decomposed into a linear combination of incidence vectors of paths and cycles. In this paper, we study the decomposition problem for the setting of dynamic edge $s$,$d$-flows assuming a quite general dynamic flow propagation model. We prove the following decomposition theorem: For any dynamic edge $s$,$d$-flow with finite support, there exists a decomposition into a linear combination of $s$,$d$-walk inflows and circulations, i.e. edge flows that circulate along cycles with zero transit time. We show that a variant of the classical algorithmic approach of iteratively subtracting walk inflows from the current dynamic edge flow converges to a dynamic circulation. The algorithm terminates in finite time, if there is a lower bound on the minimum edge travel times. We further characterize those dynamic edge flows which can be decomposed purely into linear combinations of $s$,$d$-walk inflows. The proofs rely on the new concept of parameterized network loadings which describe how particles of a different walk flow would hypothetically propagate throughout the network under the fixed travel times induced by the given edge flow. We show several technical properties of this type of network loading and as a byproduct we also derive some general results on dynamic flows which could be of interest outside the context of this paper as well., Comment: 54 pages, 3 figures

We consider generalized Nash equilibrium problems (GNEPs) with non-convex strategy spaces and non-convex cost functions. This general class of games includes the important case of games with mixed-integer variables for which only a few results are known in the literature. We present a new approach to characterize equilibria via a convexification technique using the Nikaido-Isoda function. To any given instance of the GNEP, we construct a set of convexified instances and show that a feasible strategy profile is an equilibrium for the original instance if and only if it is an equilibrium for any convexified instance and the convexified cost functions coincide with the initial ones. We develop this convexification approach along three dimensions: We first show that for quasi-linear models, where a convexified instance exists in which for fixed strategies of the opponent players, the cost function of every player is linear and the respective strategy space is polyhedral, the convexification reduces the GNEP to a standard (non-linear) optimization problem. Secondly, we derive two complete characterizations of those GNEPs for which the convexification leads to a jointly constrained or a jointly convex GNEP, respectively. These characterizations require new concepts related to the interplay of the convex hull operator applied to restricted subsets of feasible strategies and may be interesting on their own. Note that this characterization is also computationally relevant as jointly convex GNEPs have been extensively studied in the literature. Finally, we demonstrate the applicability of our results by presenting a numerical study regarding the computation of equilibria for three classes of GNEPs related to integral network flows and discrete market equilibria., Comment: 38 pages, 10 figures, 3 tables

The use of information and communication technologies (ICT) to support long-term care is gaining attention, also in the light of population ageing. Known in Scandinavian countries under the term of welfare technology, it aims to increase the quality of life and independence of people with physical, psychological or social impairments. In Germany, a new form of psychiatric home treatment, inpatient equivalent treatment (IET), is offered since 2018. It should allow service users with severe mental health issues to stay in their familiar environment during crisis, while being treated in the same complexity and flexibility like in an inpatient unit. However, this change in delivering healthcare services leads to sociotechnical challenges, such as coordination of work, integration into existing healthcare workflows and ensuring continuity of care. Hence, the objective of this exploratory study is to examine how information and communication technologies (ICT) interact in the new setting and how this process can be improved. Further, we also ask how service users can participate in designing home treatment services. Methodologically, this study follows a qualitative research approach. Different methods including participant observation, interviews and focus groups were conducted to answer the research questions. Data was collected during a field visit at the psychiatric department of a German clinic in summer 2019. Field notes and interviews were analyzed using the R package for qualitative data analysis RQDA. A list of socio-technical challenges and opportunities related to IET were identified. New forms of communication, gaps in documentation practices and continuity of care are seen to be highly relevant for designing and implementing home treatment services in psychiatric care. We also discuss how service users and health professionals can take pro-active part in designing these services.