Given positive integers m, n, a fractional assignment x ∈ [0,1]^{m × n} and weights d ∈ ℝⁿ_{> 0}, we show that there exists an assignment y ∈ {0,1}^{m × n} so that for every i ∈ [m] and t ∈ [n], |∑_{j ∈ [t]} d_j (x_{ij} - y_{ij})| < max_{j ∈ [n]} d_j. This generalizes a result of Tijdeman (1973) on the unweighted version, known as the chairman assignment problem. This also confirms a special case of the single-source unsplittable flow conjecture with arc-wise lower and upper bounds due to Morell and Skutella (IPCO 2020). As an application, we consider a scheduling problem where jobs have release times and machines have closing times, and a job can only be scheduled on a machine if it is released before the machine closes. We give a 3-approximation algorithm for maximum flow-time minimization.

Flows and colorings are disparate concepts in graph algorithms -- the former is tractable while the latter is intractable. Tutte introduced the concept of nowhere-zero flows to unify these two concepts. Jaeger showed that nowhere-zero flows are equivalent to cut-balanced orientations. Motivated by connections between nowhere-zero flows, cut-balanced orientations, Nash-Williams' well-balanced orientations, and postman problems, we study optimization versions of nowhere-zero flows and cut-balanced orientations. Given a bidirected graph with asymmetric costs on two orientations of each edge, we study the min cost nowhere-zero $k$-flow problem and min cost $k$-cut-balanced orientation problem. We show that both problems are NP-hard to approximate within any finite factor. Given the strong inapproximability result, we design bicriteria approximations for both problems: we obtain a $(6,6)$-approximation to the min cost nowhere-zero $k$-flow and a $(k,6)$-approximation to the min cost $k$-cut-balanced orientation. For the case of symmetric costs (where the costs of both orientations are the same for every edge), we show that the nowhere-zero $k$-flow problem remains NP-hard and admits a $3$-approximation.

Abstract Let $$D\,=\,(V,A)$$ D = ( V , A ) be a digraph whose underlying graph is 2-edge-connected, and let P be the polytope whose vertices are the incidence vectors of arc sets whose reversal makes D strongly connected. We study the lattice theoretic properties of the integer points contained in a proper face F of P not contained in $$\{x:x_a=i\}$$ { x : x a = i } for any $$a\in A,i\in \{0,1\}$$ a ∈ A , i ∈ { 0 , 1 } . We prove under a mild necessary condition that $$F\cap \{0,1\}^A$$ F ∩ { 0 , 1 } A contains an integral basis B, i.e., B is linearly independent, and any integral vector in the linear hull of F is an integral linear combination of B. This result is surprising as the integer points in F do not necessarily form a Hilbert basis. In proving the result, we develop a theory similar to Matching Theory for degree-constrained dijoins in bipartite digraphs. Our result has consequences for head-disjoint strong orientations in hypergraphs, and also to a famous conjecture by Woodall that the minimum size of a dicut of D, say $$\tau $$ τ , is equal to the maximum number of disjoint dijoins. We prove a relaxation of this conjecture, by finding for any prime number $$p\,\ge \,2$$ p ≥ 2 , a p-adic packing of dijoins of value $$\tau $$ τ and of support size at most 2|A|. We also prove that the all-ones vector belongs to the lattice generated by $$F\cap \{0,1\}^A$$ F ∩ { 0 , 1 } A , where F is the face of P satisfying $$x(\delta ^+(U))=1$$ x ( δ + ( U ) ) = 1 for every minimum dicut $$\delta ^+(U)$$ δ + ( U ) .