Interior-point methods offer a highly versatile framework for convex optimization that is effective in theory and practice. A key notion in their theory is that of a self-concordant barrier. We give a suitable generalization of self-concordance to Riemannian manifolds and show that it gives the same structural results and guarantees as in the Euclidean setting, in particular local quadratic convergence of Newton’s method. We analyze a path-following method for optimizing compatible objectives over a convex domain for which one has a self-concordant barrier, and obtain the standard complexity guarantees as in the Euclidean setting. We provide general constructions of barriers, and show that on the space of positive-definite matrices and other symmetric spaces, the squared distance to a point is self-concordant. To demonstrate the versatility of our framework, we give algorithms with state-of-the-art complexity guarantees for the general class of scaling and non-commutative optimization problems, which have been of much recent interest, and we provide the first algorithms for efficiently finding high-precision solutions for computing minimal enclosing balls and geometric medians in non-positive curvature.

Abstract. The terminal backup problems ([E. Anshelevich and A. Karagiozova, SIAM J. Comput., 40 (2011), pp. 678–708]) form a class of network design problems: Given an undirected graph with a requirement on terminals, the goal is to find a minimum-cost subgraph satisfying the connectivity requirement. The node-connectivity terminal backup problem requires a terminal to connect other terminals with a number of node-disjoint paths. This problem is not known whether is NP-hard or tractable. Fukunaga [ SIAM J. Discrete Math., 30 (2016), pp. 777–800] gave a [Formula: see text]-approximation algorithm based on an LP-rounding scheme using a general LP-solver. In this paper, we develop a combinatorial algorithm for the relaxed LP to find a half-integral optimal solution in [Formula: see text] time, where [Formula: see text] is the number of nodes, [Formula: see text] is the number of edges, [Formula: see text] is the number of terminals, [Formula: see text] is the maximum edge-cost, [Formula: see text] is the maximum edge-capacity, and [Formula: see text] is the time complexity of a max-flow algorithm in a network with [Formula: see text] nodes and [Formula: see text] edges. The algorithm implies that the [Formula: see text]-approximation algorithm for the node-connectivity terminal backup problem is also efficiently implemented. For the design of algorithm, we explore a connection between the node-connectivity terminal backup problem and a new type of a multiflow, which is called a separately capacitated multiflow. We show a min-max theorem which extends the Lovász–Cherkassky theorem to the node-capacity setting. Our results build on discrete convexity in the node-connectivity terminal backup problem.

Abstract In this paper, we address computation of the degree $$\deg {\rm Det} A$$ deg Det A of Dieudonné determinant $${\rm Det} A$$ Det A of $$\begin{aligned} A = \sum_{k=1}^m A_k x_k t^{c_k}, \end{aligned}$$ A = ∑ k = 1 m A k x k t c k , where $$A_k$$ A k are $$n \times n$$ n × n matrices over a field $$\mathbb{K}$$ K , $$x_k$$ x k are noncommutative variables, t is a variable commuting with $$x_k$$ x k , $$c_k$$ c k are integers, and the degree is considered for t. This problem generalizes noncommutative Edmonds' problem and fundamental combinatorial optimization problems including the weighted linear matroid intersection problem. It was shown that $$\deg {\rm Det} A$$ deg Det A is obtained by a discrete convex optimization on a Euclidean building (Hirai 2019). We extend this framework by incorporating a cost-scaling technique and show that $$\deg {\rm Det} A$$ deg Det A can be computed in time polynomial of $$n,m,\log_2 C$$ n , m , log 2 C , where $$C:= \max_k |c_k|$$ C : = max k | c k | . We give a polyhedral interpretation of $$\deg {\rm Det}$$ deg Det , which says that $$\deg {\rm Det}$$ deg Det A is given by linear optimization over an integral polytope with respect to objective vector $$c = (c_k)$$ c = ( c k ) . Based on it, we show that our algorithm becomes a strongly polynomial one. We also apply our result to an algebraic combinatorial optimization problem arising from a symbolic matrix having $$2 \times 2$$ 2 × 2 -submatrix structure.

In this article, we develop an O (( m log k )MSF( n,m ,1))-time algorithm to find a half-integral node-capacitated multiflow of the maximum total flow-value in a network with n nodes, m edges, and k terminals, where MSF( n ′ , m ′ ,γ) denotes the time complexity of solving the maximum submodular flow problem in a network with n ′ nodes, m ′ edges, and the complexity γ of computing the exchange capacity of the submodular function describing the problem. By using Fujishige-Zhang algorithm for submodular flow, we can find a maximum half-integral multiflow in O ( m n 3 log k ) time. This is the first combinatorial strongly polynomial time algorithm for this problem. Our algorithm is built on a developing theory of discrete convex functions on certain graph structures. Applications include “ellipsoid-free” combinatorial implementations of a 2-approximation algorithm for the minimum node-multiway cut problem by Garg, Vazirani, and Yannakakis.

A binary VCSP is a general framework for the minimization problem of a function represented as the sum of unary and binary cost functions. An important line of VCSP research is to investigate what functions can be solved in polynomial time. Cooper and Živný classified the tractability of binary VCSP instances according to the concept of “triangle,” and showed that the only interesting tractable case is the one induced by the joint winner property (JWP). Recently, Iwamasa, Murota, and Živný made a link between VCSP and discrete convex analysis, showing that a function satisfying the JWP can be transformed into a function represented as the sum of two quadratic M-convex functions, which can be minimized in polynomial time via an M-convex intersection algorithm if the value oracle of each M-convex function is given. In this article, we give an algorithmic answer to a natural question: What binary finite-valued CSP instances can be represented as the sum of two quadratic M-convex functions and can be solved in polynomial time via an M-convex intersection algorithm? We solve this problem by devising a polynomial-time algorithm for obtaining a concrete form of the representation in the representable case. Our result presents a larger tractable class of binary finite-valued CSPs, which properly contains the JWP class.

A phylogenetic tree is a graphical representation of an evolutionary history in a set of taxa in which the leaves correspond to taxa and the non-leaves correspond to speciations. One of important problems in phylogenetic analysis is to assemble a global phylogenetic tree from smaller pieces of phylogenetic trees, particularly, quartet trees. Quartet Compatibility is to decide whether there is a phylogenetic tree inducing a given collection of quartet trees, and to construct such a phylogenetic tree if it exists. It is known that Quartet Compatibility is NP-hard but there are only a few results known for polynomial-time solvable subclasses. In this paper, we introduce two novel classes of quartet systems, called complete multipartite quartet system and full multipartite quartet system, and present polynomial time algorithms for Quartet Compatibility for these systems. We also see that complete/full multipartite quartet systems naturally arise from a limited situation of block-restricted measurement.

A binary VCSP is a general framework for the minimization problem of a function represented as the sum of unary and binary cost functions.An important line of VCSP research is to investigate what functions can be solved in polynomial time. Cooper-Zivny classified the tractability of binary VCSP instances according to the concept of "triangle," and showed that the only interesting tractable case is the one induced by the joint winner property (JWP). Recently, Iwamasa-Murota-Zivny made a link between VCSP and discrete convex analysis, showing that a function satisfying the JWP can be transformed into a function represented as the sum of two M-convex functions, which can be minimized in polynomial time via an M-convex intersection algorithm if the value oracle of each M-convex function is given. In this paper, we give an algorithmic answer to a natural question: What binary finite-valued CSP instances can be solved in polynomial time via an M-convex intersection algorithm? We solve this problem by devising a polynomial-time algorithm for obtaining a concrete form of the representation in the representable case. Our result presents a larger tractable class of binary finite-valued CSPs, which properly contains the JWP class.

$k$-submodular functions, introduced by Huber and Kolmogorov, are functions defined on $\{0, 1, 2, \dots, k\}^n$ satisfying certain submodular-type inequalities. $k$-submodular functions typically arise as relaxations of NP-hard problems, and the relaxations by $k$-submodular functions play key roles in design of efficient, approximation, or fixed-parameter tractable algorithms. Motivated by this, we consider the following problem: Given a function $f : \{1, 2, \dots, k\}^n \rightarrow \mathbb{R} \cup \{+ \infty\}$, determine whether $f$ can be extended to a $k$-submodular function $g : \{0, 1, 2, \dots, k\}^n \rightarrow \mathbb{R} \cup \{+ \infty\}$, where $g$ is called a $k$-submodular relaxation of $f$, i.e., the restriction of $g$ on $\{1, 2, \dots, k\}^n$ is equal to $f$. We give a characterization, in terms of polymorphisms, of the functions which admit a $k$-submodular relaxation, and also give a combinatorial $O((k^n)^2)$-time algorithm to find a $k$-submodular relaxation or establish that a $k$-submodular relaxation does not exist. Our algorithm has interesting properties: (1) If the input function is integer valued, then our algorithm outputs a half-integral relaxation, and (2) if the input function is binary, then our algorithm outputs the unique optimal relaxation. We present applications of our algorithm to valued constraint satisfaction problems.

Cognitive radio technology improves radio resource usage by reconfiguring the wireless connection settings according to the optimum decisions, which are made on the basis of the collected context information. This paper focuses on optimization algorithms for decision making to optimize radio resource usage in heterogeneous cognitive wireless networks. For networks with centralized management, we proposed a novel optimization algorithm whose solution is guaranteed to be exactly optimal. In order to avoid an exponential increase of computational complexity in large-scale wireless networks, we model the target optimization problem as a minimum cost-flow problem and find the solution of the problem in polynomial time. For the networks with decentralized management, we propose a distributed algorithm using the distributed energy minimization dynamics of the Hopfield–Tank neural network. Our algorithm minimizes a given objective function without any centralized calculation. We derive the decision-making rule for each terminal to optimize the entire network. We demonstrate the validity of the proposed algorithms by several numerical simulations and the feasibility of the proposed schemes by designing and implementing them on experimental cognitive radio network systems.

The minimum 0-extension problem 0-Ext[Γ] on a graph Γ is: given a set V including the vertex set VΓ of Γ and a nonnegative cost function c defined on the set of all pairs of V, find a 0-extension d of the path metric dΓ of Γ with Σxy c(xy)d(x, y) minimum, where a 0-extension is a metric d on V such that the restriction of d to VΓ coincides with dΓ and for all x ∊ V there exists a vertex s in Γ with d(x, s) = 0. 0-Ext[Γ] includes a number of basic combinatorial optimization problems, such as minimum (s, t)-cut problem and multiway cut problem. Karzanov proved the polynomial solvability for a certain large class of modular graphs, and raised the question: What are the graphs Γ for which 0-Ext[Γ] can be solved in polynomial time? He also proved that 0-Ext[Γ] is NP-hard if Γ is not modular or not orientable (in a certain sense). In this paper, we prove the converse: if Γ is orientable and modular, then 0-Ext[Γ] can be solved in polynomial time. This completes the classification of the tractable graphs for the 0-extension problem. To prove our main result, we develop a theory of discrete convex functions on orientable modular graphs, analogous to discrete convex analysis by Murota, and utilize a recent result of Thapper and Živný on Valued-CSP.

In multiflow maximization problems, there are several combinatorial duality relations, such as the Ford–Fulkerson max-flow min-cut theorem for single commodity flows, Hu’s max-biflow min-cut theorem for two-commodity flows, the Lovász–Cherkassky duality theorem for free multiflows, and so on. In this paper, we provide a unified framework for such multiflow combinatorial dualities by using the notion of a folder complex, which is a certain 2-dimensional polyhedral complex introduced by Chepoi. We show that for a nonnegative weight [Formula: see text] on terminal set, the [Formula: see text]-weighted maximum multiflow problem admits a combinatorial duality relation if and only if [Formula: see text] is represented by distances between certain subsets in a folder complex, and we show that the corresponding combinatorial dual problem is a discrete location problem on the graph of the folder complex. This extends a result of Karzanov in the case of metric weights.

This paper addresses a fundamental issue in the multicommodity flow theory. For an undirected capacitated supply graph (G,c) having commodity graph H, the maximum multiflow problem is to maximize the total flow-value of multicommodity flows with respect to (G,c;H). For a commodity graph H, the fractionality of H is the least positive integer k with property that there exists a 1/k-integral optimal multiflow in the maximum multiflow problem for every integer-capacitated supply graph (G,c) having H as a commodity graph. If such a positive integer k does not exist, then the fractionality is defined to be infinity. Around 1990, Karzanov raised the problem of classifying commodity graphs with finite fractionality, gave a necessary condition (property P) for the finiteness of fractionality, and conjectured that the property P is also sufficient. Our main result affirmatively solves Karzanov's conjecture in algorithmic form: If H has property P, then there exists a 1/24-integral optimal multiflow in maximum multiflow problem for every integer-capacitated supply graph having H as a commodity graph, and there exists a strongly polynomial time algorithm to find it. Our proof is based on a special combinatorial duality relation involving a class of CAT(0) complexes, and on a fractional version of the splitting-off method for finding an optimal multiflow with a bounded denominator.