Search

Maximally recoverable codes are codes designed for distributed storage which combine quick recovery from single node failure and optimal recovery from catastrophic failure. Gopalan et al. [Maximally recoverable codes for grid-like topologies, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2017, pp. 2092--2108] studied the alphabet size needed for such codes in grid topologies and gave a combinatorial characterization for it. Consider a labeling of the edges of the complete bipartite graph Kn,n, with labels coming from F2d, that satisfies the following condition: for any simple cycle, the sum of the labels over its edges is nonzero. The minimal d where this is possible controls the alphabet size needed for maximally recoverable codes in n×n grid topologies. Prior to the current work, it was known that d is between (log n)² and n log n. We improve both bounds and show that d is linear in n. The upper bound is a recursive construction which beats the random construction. The lower bound follows by first relating the problem to the independence number of the Birkhoff polytope graph, and then providing tight bounds for it using the representation theory of the symmetric group. [ABSTRACT FROM AUTHOR]

A classical parking function of length n is a list of positive integers (a 1 , a 2 , ... , a n) whose nondecreasing rearrangement b 1 ≤ b 2 ≤ ⋯ ≤ b n satisfies b i ≤ i . The convex hull of all parking functions of length n is an n-dimensional polytope in R n , which we refer to as the classical parking function polytope. Its geometric properties have been explored in Amanbayeva and Wang (Enumer Combin Appl 2(2):Paper No. S2R10, 10, 2022) in response to a question posed by Stanley (Amer Math Mon 127(6):563–571, 2020). We generalize this family of polytopes by studying the geometric properties of the convex hull of x -parking functions for x = (a , b , ⋯ , b) , which we refer to as x -parking function polytopes. We explore connections between these x -parking function polytopes, the Pitman–Stanley polytope, and the partial permutahedra of Heuer and Striker (SIAM J Discrete Math 36(4):2863–2888, 2022). In particular, we establish a closed-form expression for the volume of x -parking function polytopes. This allows us to answer a conjecture of Behrend et al. (2022) and also obtain a new closed-form expression for the volume of the convex hull of classical parking functions as a corollary. [ABSTRACT FROM AUTHOR]

Cutting planes from the Boolean Quadric Polytope can be used to reduce the optimality gap of the NP -hard nonconvex quadratic program with box constraints (BoxQP). It is known that all cuts of the Chvátal–Gomory closure of the Boolean Quadric Polytope are A-odd cycle inequalities. We obtain a compact extended relaxation of allA-odd cycle inequalities, which allows to optimize over the Chvátal–Gomory closure without repeated calls to separation algorithms and has less inequalities than the formulation provided by Boros et al. (SIAM J Discrete Math 5(2):163–177, 1992) for sparse matrices. In a computational study, we confirm the strength of this relaxation and show that we can provide very strong bounds for the BoxQP, even with a plain linear program. The resulting bounds are significantly stronger than these from Bonami et al. (Math Program Comput 10(3):333–382, 2018), which arise from separating A-odd cycle inequalities heuristically. [ABSTRACT FROM AUTHOR]

A well-studied geometric object in combinatorial optimization is the perfect matching polytope of a graph $G$---the convex hull of the incidence vectors of all perfect matchings of $G$. In any investigation concerning the perfect matching polytope, one may assume that $G$ is matching covered---that is, $G$ is a connected graph (of order at least two) and each edge of $G$ lies in some perfect matching. A graph $G$ is Birkhoff--von Neumann if its perfect matching polytope is characterized solely by nonnegativity and degree constraints. A result of Balas [North Holland Math. Stud., 59 (1981), pp. 1--13] implies that $G$ is Birkhoff--von Neumann if and only if $G$ does not contain a pair of vertex-disjoint odd cycles $(C_1,C_2)$ such that $G-V(C_1)-V(C_2)$ has a perfect matching. It follows immediately that the corresponding decision problem is in co-$\mathcal{NP}$. However, it is not known to be in $\mathcal{NP}$. The problem is in $\mathcal{P}$ if the input graph is planar---due to a result of Carvalho, Lucchesi, and Murty [J. Combin. Theory Ser. B, 92 (2004), pp. 319--324]. More recently, these authors, along with Kothari [SIAM J. Discrete Math., 32 (2018), pp. 1478--1504], have shown that this problem is equivalent to the seemingly unrelated problem of deciding whether a given graph is $\overline{C_6}$-free. The combinatorial diameter of a polytope is the diameter of its $1$-skeleton graph. A graph $G$ is PM-compact if the combinatorial diameter of its perfect matching polytope equals one. Independent results of Balinski and Russakoff [SIAM Rev., 16 (1974), pp. 516--525] and of Chvátal [J. Combin. Theory Ser. B, 18 (1975), pp. 138--154] imply that $G$ is PM-compact if and only if $G$ does not contain a pair of vertex-disjoint even cycles $(C_1,C_2)$ such that $G-V(C_1)-V(C_2)$ has a perfect matching. Once again the corresponding decision problem is in co-$\mathcal{NP}$, but it is not known to be in $\mathcal{NP}$. The problem is in $\mathcal{P}$ if the input graph is bipartite or is near-bipartite---due to a result of Wang et al. [Discrete Math., 313 (2013), pp. 772--783]. In this paper, we consider the “intersection” of the aforementioned problems. We give an alternative description of matching covered graphs that are Birkhoff--von Neumann as well as PM-compact; our description implies that the corresponding decision problem is in $\mathcal{P}$. [ABSTRACT FROM AUTHOR]

We analyze the maximal growth of trajectories of discrete-time linear switching system, i.e., controlled linear systems with the control set being an arbitrary compact set of matrices. This is done by applying the optimal convex Lyapunov function called the Barabanov norm, which provides a very refined analysis of trajectories. Until recently that notion remained rather theoretical apart from special cases. In 2015 N. Guglielmi and M. Zennaro [SIAM J. Matrix Anal. Appl., 36 (2015), pp. 634-655] showed that many systems possess at least one efficiently computed Barabanov norm. In this paper we classify all possible Barabanov norms and prove that, under mild assumptions, which can be verified algorithmically, those norms are unique and are either piecewise-linear or piecewise-quadratic. For some narrow classes of systems, there are more complicated Barabanov norms, but they can still be classified and constructed. Using those results we find all trajectories of the fastest growth. Examples and numerical results are provided. [ABSTRACT FROM AUTHOR]

We consider optimal control problems for partial differential equations where the controls take binary values but vary over the time horizon; they can thus be seen as dynamic switches. The switching patterns may be sub ject to combinatorial constraints such as, e.g., an upper bound on the total number of switchings or a lower bound on the time between two switchings. In a companion paper [C. Buchheim, A. Gruütering, and C. Meyer, SIAM J. Optim., arXiv:2203.07121, 2024], we describe the Lp -closure of the convex hull of feasible switching patterns as the intersection of convex sets derived from finite-dimensional pro jections. In this paper, the resulting outer description is used for the construction of an outer approximation algorithm in function space, whose iterates are proven to converge strongly in L² to the global minimizer of the convexified optimal control problem. The linear-quadratic subproblems arising in each iteration of the outer approximation algorithm are solved by means of a semismooth Newton method. A numerical example in two spatial dimensions illustrates the efficiency of the overall algorithm. [ABSTRACT FROM AUTHOR]

The determinant lower bound of Lovász, Spencer, and Vesztergombi [European J. Combin., 7 (1986), pp. 151-160] is a general way to prove lower bounds on the hereditary discrepancy of a set system. In their paper, Lovász, Spencer, and Vesztergombi asked if hereditary discrepancy can also be bounded from above by a function of the determinant lower bound. This was answered in the negative by Hoffman, and the largest known multiplicative gap between the two quantities for a set system of m subsets of a universe of size n is on the order of max {log n, √log m}. On the other hand, building upon work of Matousek [Proc. Amer. Math. Soc., 141 (2013), pp. 451-460], Jiang and Reis [in Proceedings of the Symposium on Simplicity in Algorithms (SOSA), SIAM, Philadelphia, 2022, pp. 308-313] showed that this gap is always bounded up to constants by √log(m)log(n). This is tight when m is polynomial in n but leaves open the case of large m. We show that the bound of Jiang and Reis is tight for nearly the entire range of m. Our proof amplifies the discrepancy lower bounds of a set system derived from the discrete Haar basis via Kronecker products. [ABSTRACT FROM AUTHOR]

We propose a new algorithm for Promise Constraint Satisfaction Problems (PCSPs). It is a combination of the Constraint Basic LP relaxation and the Affine IP relaxation (CLAP). We give a characterization of the power of CLAP in terms of a minion homomorphism. Using this characterization, we identify a certain weak notion of symmetry which, if satisfied by infinitely many polymorphisms of PCSPs, guarantees tractability. We demonstrate that there are PCSPs solved by CLAP that are not solved by any of the existing algorithms for PCSPs; in particular, not by the BLP+AIP algorithm of Brakensiek et al. [SIAM J. Comput., 49 (2020), pp. 1232--1248] and not by a reduction to tractable finite-domain CSPs. [ABSTRACT FROM AUTHOR]

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 4/3-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 O(mlog(n-A · MF(/cn,m T/c2n)) time, where n is the number of nodes, m is the number of edges, k is the number of terminals, A is the maximum edge-cost, U is the maximum edge-capacity, and MF(nz,mz) is the time complexity of a max-flow algorithm in a network with nz nodes and m' edges. The algorithm implies that the 4/3-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 Lovasz-Cherkassky theorem to the node-capacity setting. Our results build on discrete convexity in the node-connectivity terminal backup problem. [ABSTRACT FROM AUTHOR]

In the machine learning and optimization community, there are two main approaches for the convex risk minimization problem, namely the Stochastic Approximation (SA) and the Sample Average Approximation (SAA). In terms of the oracle complexity (required number of stochastic gradient evaluations), both approaches are considered equivalent on average (up to a logarithmic factor). The total complexity depends on a specific problem, however, starting from the work [A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro, Robust stochastic approximation approach to stochastic programming, SIAM. J. Opt. 19 (2009), pp. 1574–1609] it was generally accepted that the SA is better than the SAA. We show that for the Wasserstein barycenter problem, this superiority can be inverted. We provide a detailed comparison by stating the complexity bounds for the SA and SAA implementations calculating barycenters defined with respect to optimal transport distances and entropy-regularized optimal transport distances. As a byproduct, we also construct confidence intervals for the barycenter defined with respect to entropy-regularized optimal transport distances in the ℓ 2 -norm. The preliminary results are derived for a general convex optimization problem given by the expectation to have other applications besides the Wasserstein barycenter problem. [ABSTRACT FROM AUTHOR]

Purpose: This study aims to provide a measurement model, and the underlying constructs and items, for Logistics 4.0 in manufacturing companies. Industry 4.0 technology for logistics processes has been termed Logistics 4.0. Logistics 4.0 and its elements have seen varied conceptualizations in the literature. The literature has mainly focused on conceptual and theoretical studies, which supports the notion that Logistics 4.0 is a relatively young area of research. Refinement of constructs and building consensus perspectives and definitions is necessary for practical and theoretical advances in this area. Design/methodology/approach: Based on a detailed literature review and practitioner focus group interviews, items of Logistics 4.0 for manufacturing enterprises were further validated by using a large-scale survey with practicing experts from organizations located in Central Europe, the Northeastern United States of America and Northern Thailand. Exploratory and confirmatory factor analyses were used to define a measurement model for Logistics 4.0. Findings: Based on 239 responses the exploratory and confirmatory factor analyses resulted in nine items and three factors for the final Logistics 4.0 measurement model. It combines "the leveraging of increased organizational capabilities" (factor 1) with "the rise of interconnection and material flow transparency" (factor 2) and "the setting up of autonomization in logistics processes" (factor 3). Practical implications: Practitioners can use the proposed measurement model to assess their current level of maturity regarding the implementation of Logistics 4.0 practices. They can map the current state and derive appropriate implementation plans as well as benchmark against best practices across or between industries based on these metrics. Originality/value: Logistics 4.0 is a relatively young research area, which necessitates greater development through empirical validation. To the best of the authors knowledge, an empirically validated multidimensional construct to measure Logistics 4.0 in manufacturing companies does not exist. [ABSTRACT FROM AUTHOR]

We investigate a hierarchy of semidefinite bounds v(r)(G) for the stability number α(G) of a graph G, based on its copositive programming formulation and introduced by de Klerk and Pasechnik [SIAM J. Optim., 12 (2002), pp. 875-892], who conjectured convergence to α(G) in r = α(G) -- 1 steps. Even the weaker conjecture claiming finite convergence is still open. We establish links between this hierarchy and sum-of-squares hierarchies based on the Motzkin--Straus formulation of α(G), which we use to show finite convergence when G is acritical, i.e., when α(G \ ᵉ) = α(G) for all edges e of G. This relies, in particular, on understanding the structure of the minimizers of the Motzkin--Straus formulation and showing that their number is finite precisely when G is acritical. Moreover we show that these results hold in the general setting of the weighted stable set problem for graphs equipped with positive node weights. In addition, as a byproduct we show that deciding whether a standard quadratic program has finitely many minimizers does not admit a polynomial-time algorithm unless P=NP. [ABSTRACT FROM AUTHOR]

We develop convexification techniques for mathematical programs with complementarity constraints. Specifically, we adapt the reformulation-linearization technique of Sherali and Adams (SIAM J Discrete Math 3, 411–430, 1990) to problems with linear complementarity constraints and discuss how this procedure reduces to its standard specification for binary mixed-integer programs. Then, we consider specially structured complementarity sets that appear in KKT systems with linear constraints. For sets with a single complementarity constraint, we develop a convexification procedure that generates all nontrivial facet-defining inequalities and has an appealing "cancel-and-relax" interpretation. This procedure is used to describe the convex hull of problems with few side constraints in closed-form. As a consequence, we delineate cases when the factorable relaxation techniques yield the convex hull from those for which they do not. We then discuss how these results extend to sets with multiple complementarity constraints. In particular, we show that a suitable sequential application of the cancel-and-relax procedure produces all nontrivial inequalities of their convex hull. We conclude by illustrating, on a set of randomly generated problems, that the relaxations we propose can be significantly stronger than those available in the literature. [ABSTRACT FROM AUTHOR]

The l1-l2 regularization is a popular nonconvex yet Lipschitz continuous metric, which has been widely used in signal and image processing. The theory for the l1-l2 minimization method shows that it has superior sparse recovery performance over the classical l1 minimization method. The motivation and major contribution of this paper is to provide a positive answer to the open problem posed in [T.-H. Ma, Y. Lou, and T.-Z. Huang, SIAM J. Imaging Sci., 10 (2017), pp. 1346-1380] about the sufficient conditions that can be sharpened for the l1-l2 minimization method. The novel technique used in our analysis of the l1-l2 minimization method is a crucial sparse representation adapted to the l1-l2 metric which is different from the other state-of-the-art works in the context of the l1-l2 minimization method. The new restricted isometry property (RIP) analysis is better than the existing RIP based conditions to guarantee the exact and stable recovery of signals. [ABSTRACT FROM AUTHOR]

Explaining the excellent practical performance of the simplex method for linear programming has been a major topic of research for over 50 years. One of the most successful frameworks for understanding the simplex method was given by Spielman and Teng [J. ACM, 51 (2004), pp. 385--463] who developed the notion of smoothed analysis. Starting from an arbitrary linear program (LP) with d variables and n constraints, Spielman and Teng analyzed the expected runtime over random perturbations of the LP, known as the smoothed LP, where variance \sigma 2 Gaussian noise is added to the LP data. In particular, they gave a two-stage shadow vertex simplex algorithm which uses an expected \widetilde O(d55n86\sigma 30 + d70n86) number of simplex pivots to solve the smoothed LP. Their analysis and runtime was substantially improved by Deshpande and Spielman [FOCS '05, 2005, pp. 349--356] and later Vershynin [SIAM J. Comput., 39 (2009), pp. 646--678]. The fastest current algorithm, due to Vershynin, solves the smoothed LP using an expected O \bigl(log2 n \cdot log log n \cdot (d3\sigma 4+d5 log2 n+d9 log4 d) \bigr) number of pivots, improving the dependence on n from polynomial to polylogarithmic. While the original proof of Spielman and Teng has now been substantially simplified, the resulting analyses are still quite long and complex and the parameter dependencies far from optimal. In this work, we make substantial progress on this front, providing an improved and simpler analysis of shadow simplex methods, where our algorithm requires an expected O(d2 \surd log n \sigma 2 + d3 log3/2 n) number of simplex pivots. We obtain our results via an improved shadow bound, key to earlier analyses as well, combined with improvements on algorithmic techniques of Vershynin. As an added bonus, our analysis is completely modular and applies to a range of perturbations, which, aside from Gaussians, also includes Laplace perturbations. [ABSTRACT FROM AUTHOR]

Carvalho, Lucchesi, and Murty [J. Combin. Theory Ser. B, 92 (2004), pp. 319--324, Theorem 3.5] presented a proof of a theorem of Reed and Wakabayashi that a brick G is nonsolid if and only if there exist two vertex-disjoint odd cycles C1 and C2 such that G V (C1 ∪ C2) has a perfect matching. Consequently, every brick with no two vertex-disjoint odd cycles is solid. Recently, Lucchesi et al. [SIAM J. Discrete Math., 32 (2018), pp. 1478--1501] constructed infinite families of solid bricks containing two vertex-disjoint odd cycles. Noticing that none of these graphs is cubic, they conjectured that no cubic solid brick contains two vertex-disjoint odd cycles. In this note, we present an infinite family of graphs showing that this conjecture fails. We further show that the minimum counterexample is unique, which has 12 vertices. [ABSTRACT FROM AUTHOR]