Search

The Micali–Vazirani (MV) algorithm for finding a maximum cardinality matching in general graphs, which was published in 1980, remains to this day the most efficient known algorithm for the problem. The current paper gives the first complete and correct proof of this algorithm. The MV algorithm resorts to finding minimum-length augmenting paths. However, such paths fail to satisfy an elementary property, called breadth first search honesty in this paper. In the absence of this property, an exponential time algorithm appears to be called for—just for finding one such path. On the other hand, the MV algorithm accomplishes this and additional tasks in linear time. The saving grace is the various "footholds" offered by the underlying structure, which the algorithm uses in order to perform its key tasks efficiently. The theory expounded in this paper elucidates this rich structure and yields a proof of correctness of the algorithm. It may also be of independent interest as a set of well-knit graph-theoretic facts. Funding: This work was supported in part by the National Science Foundation [Grant CCF-2230414]. [ABSTRACT FROM AUTHOR]

The progressive hedging algorithm (PHA) is an effective solution method for solving monotone stochastic variational inequalities (SVIs). However, this validity is based on the assumption of global maximal monotonicity. In this paper, we propose a localized PHA for solving nonmonotone SVIs and show that its validity is based on the weaker assumption of locally elicitable maximal monotonicity. Furthermore, we prove that such assumption holds when the mapping involved in the SVI is locally elicitable monotone or locally monotone. The local convergence of the proposed algorithm is established, and it is shown that the localized PHA has the rate of linear convergence under some mild assumptions. Some numerical experiments, including a two-stage orange market problem and randomly generated two-stage piecewise stochastic linear complementarity problems, indicate that the proposed algorithm is efficient. Funding: This work was supported by the National Natural Science Foundation of China [Grant 12171271]. [ABSTRACT FROM AUTHOR]

This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix of a prespecified size from a covariance matrix. MESP is widely applied to many areas, including healthcare, power systems, manufacturing, and data science. By investigating its Lagrangian dual and primal characterization, we derive a novel convex integer program for MESP and show that its continuous relaxation yields a near-optimal solution. The results motivate us to study efficient approximation algorithms and develop their approximation bounds for MESP, which improves the best known one in the literature. This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix of a prespecified size from a covariance matrix. By investigating its Lagrangian dual and primal characterization, we derive a novel convex integer program for MESP and show that its continuous relaxation yields a near-optimal solution. The results motivate us to develop a sampling algorithm and derive its approximation bound for MESP, which improves the best known bound in literature. We then provide an efficient deterministic implementation of the sampling algorithm with the same approximation bound. Besides, we investigate the widely used local search algorithm and prove its first known approximation bound for MESP. The proof techniques further inspire for us an efficient implementation of the local search algorithm. Our numerical experiments demonstrate that these approximation algorithms can efficiently solve medium-size and large-scale instances to near optimality. Finally, we extend the analyses to the A-optimal MESP, for which the objective is to minimize the trace of the inverse of the selected principal submatrix. Funding: This work was supported by the National Science Foundation Division of Information and Intelligent Systems [Grant 2246417] and Division of Civil, Mechanical and Manufacturing Innovation [Grant 2246414]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2023.2488. [ABSTRACT FROM AUTHOR]

Solving Rank Constrained Least Squares via Recursive Importance Sketching In statistics and machine learning, we sometimes run into the rank-constrained least squares problems, for which we need to find the best low-rank fit between sets of data, such as trying to figure out what factors are affecting the data, filling in missing information, or finding connections between different sets of data. This paper introduces a new method for solving this problem called the recursive importance sketching algorithm (RISRO), in which the central idea is to break the problem down into smaller, easier parts using a unique technique called "recursive importance sketching." This new method is not only easy to use, but it is also very efficient and gives accurate results. We prove that RISRO converges in a local quadratic-linear and quadratic rate under some mild conditions. Simulation studies also demonstrate the superior performance of RISRO. In this paper, we propose a recursive importance sketching algorithm for rank-constrained least squares optimization (RISRO). The key step of RISRO is recursive importance sketching, a new sketching framework based on deterministically designed recursive projections, and it significantly differs from the randomized sketching in the literature. Several existing algorithms in the literature can be reinterpreted under this new sketching framework, and RISRO offers clear advantages over them. RISRO is easy to implement and computationally efficient, and the core procedure in each iteration is to solve a dimension-reduced least squares problem. We establish the local quadratic-linear and quadratic rate of convergence for RISRO under some mild conditions. We also discover a deep connection of RISRO to the Riemannian Gauss–Newton algorithm on fixed rank matrices. The effectiveness of RISRO is demonstrated in two applications in machine learning and statistics: low-rank matrix trace regression and phase retrieval. Simulation studies demonstrate the superior numerical performance of RISRO. Funding: Y. Luo and A. Zhang were partially supported by the National Science Foundation [Grant CAREER-2203741]. W. Huang was partially supported by the Fundamental Research Funds for the Central Universities [Grant 20720190060] and the National Natural Science Foundation of China [Grant 12001455]. X. Li was partially supported by the National Natural Science Foundation of China [Grants 62141407 and 12271107], the Chenguang Program by the Shanghai Education Development Foundation and Shanghai Municipal Education Commission [Grant 19CG02], and the Shanghai Science and Technology Program [Grant 21JC1400600]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2023.2445. [ABSTRACT FROM AUTHOR]

Projecting a vector onto a simplex is a well-studied problem that arises in a wide range of optimization problems. Numerous algorithms have been proposed for determining the projection; however, the primary focus of the literature is on serial algorithms. We present a parallel method that decomposes the input vector and distributes it across multiple processors for local projection. Our method is especially effective when the resulting projection is highly sparse, which is the case, for instance, in large-scale problems with independent and identically distributed (i.i.d.) entries. Moreover, the method can be adapted to parallelize a broad range of serial algorithms from the literature. We fill in theoretical gaps in serial algorithm analysis and develop similar results for our parallel analogues. Numerical experiments conducted on a wide range of large-scale instances, both real world and simulated, demonstrate the practical effectiveness of the method. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous. Funding: This work was supported by the Office of Naval Research [Grant N00014-23-1-2632]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0328) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0328). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

In this paper we consider the fundamental scheduling problem of minimizing the weighted number of tardy jobs on a single machine. We present a simple pseudo polynomial-time algorithm for this problem that improves upon the classical Lawler and Moore algorithm from the late 60's under certain scenarios and parameter settings. Our algorithm uses (max,+)-convolutions as its main tool, exploiting recent improved algorithms for computing such convolutions, and obtains several different running times depending on the specific improvement used. We also provide a related lower bound for the problem under a variant of the well-known Strong Exponential Time Hypothesis (SETH). History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This work was supported by the Israel Science Foundation [Grant 1070/20]. [ABSTRACT FROM AUTHOR]

An algorithm for the two-stage robust optimization surgery-to-operating room allocation problem is presented. The second-stage problem is an integer linear program whose convex hull is approximated using three types of specialized valid inequalities and Chvátal-Gomory cuts. The resulting linear relaxation of the second-stage problem is then dualized and integrated into the first-stage problem. The resulting mixed integer linear program, which is an approximation of the original problem, is then solved using a commercial solver. If the solution of this model is not optimal for the second-stage problem, valid inequalities for the second-stage problem are generated, yielding a type of column-generation based approach that we refer to as the sequential follower refinement (SFR) algorithm. Data from an academic medical center are used to compare the computational performance of SFR with the constraint and column generation (C&CG) algorithm, which is the only exact approach that has been specifically applied for this problem in the literature. An extensive numerical study of SFR and its computational characteristics is presented that shows that SFR yields better-quality solutions compared with C&CG, even as the termination criterion of SFR is met much sooner, especially for problems involving higher number of surgeries. History: Accepted by Paul Brooks, Area Editor for Applications in Biology, Medicine, & Healthcare. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0191) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0191). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

We introduce a bundle method for the unconstrained minimization of nonsmooth difference-of-convex (DC) functions, and it is based on the calculation of a special type of descent direction called descent–ascent direction. The algorithm only requires evaluations of the minuend component function at each iterate, and it can be considered as a parsimonious bundle method as accumulation of information takes place only in case the descent–ascent direction does not provide a sufficient decrease. No line search is performed, and proximity control is pursued independent of whether the decrease in the objective function is achieved. Termination of the algorithm at a point satisfying a weak criticality condition is proved, and numerical results on a set of benchmark DC problems are reported. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms – Continuous. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0142) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2023.0142). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

We study the problem of allocating divisible bads (chores) among multiple agents with additive utilities when monetary transfers are not allowed. The competitive rule is known for its remarkable fairness and efficiency properties in the case of goods. This rule was extended to chores by Bogomolnaia, Moulin, Sandomirskiy, and Yanovskaya. For both goods and chores, the rule produces Pareto optimal and envy-free allocations. In the case of goods, the outcome of the competitive rule can be easily computed. Competitive allocations solve the Eisenberg-Gale convex program; hence the outcome is unique and can be approximately found by standard gradient methods. An exact algorithm that runs in polynomial time in the number of agents and goods was given by Orlin. In the case of chores, the competitive rule does not solve any convex optimization problem; instead, competitive allocations correspond to local minima, local maxima, and saddle points of the Nash social welfare on the Pareto frontier of the set of feasible utilities. The Pareto frontier may contain many such points and, consequently, the outcome of the competitive rule is no longer unique. In this paper, we show that all the outcomes of the competitive rule for chores can be computed in strongly polynomial time if either the number of agents or the number of chores is fixed. The approach is based on a combination of three ideas: all consumption graphs of Pareto optimal allocations can be listed in polynomial time; for a given consumption graph, a candidate for a competitive utility profile can be constructed via an explicit formula; each candidate can be checked for competitiveness and the allocation can be reconstructed using a maximum flow computation. Our algorithm immediately gives an approximately-fair allocation of indivisible chores by the rounding technique of Barman and Krishnamurthy. Funding: This work was supported by National Science Foundation (CNS 1518941); Lady Davis Fellowship Trust, Hebrew University of Jerusalem; H2020 European Research Council (740435); Linde Institute at Caltech. [ABSTRACT FROM AUTHOR]

The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of m linear inequalities in n variables (P):A⊤x≤u when its set of solutions has positive volume. However, when (P) is infeasible, the ellipsoid algorithm has no mechanism for proving that (P) is infeasible. This is in contrast to the other two fundamental algorithms for tackling (P) , namely, the simplex and interior-point methods, each of which can be easily implemented in a way that either produces a solution of (P) or proves that (P) is infeasible by producing a solution to the alternative system (Alt):Aλ=0, u⊤λ<0, λ≥0. This paper develops an oblivious ellipsoid algorithm (OEA) that either produces a solution of (P) or produces a solution of (Alt). Depending on the dimensions and other condition measures, the computational complexity of the basic OEA may be worse than, the same as, or better than that of the standard ellipsoid algorithm. We also present two modified versions of OEA, whose computational complexity is superior to that of OEA when n≪m. This is achieved in the first modified version by proving infeasibility without producing a solution of (Alt) , and in the second version by using more memory. Funding: J. Lamperski and R. M. Freund were supported by the Air Force Office of Scientific Research [Grant FA9550-19-1-0240]. [ABSTRACT FROM AUTHOR]

More than 40 years ago, Lions and Mercier introduced in a seminal paper the Douglas–Rachford algorithm. Today, this method is well-recognized as a classic and highly successful splitting method to find minimizers of the sum of two (not necessarily smooth) convex functions. Whereas the underlying theory has matured, one case remains a mystery: the behavior of the shadow sequence when the given functions have disjoint domains. Building on previous work, we establish for the first time weak and value convergence of the shadow sequence generated by the Douglas–Rachford algorithm in a setting of unprecedented generality. The weak limit point is shown to solve the associated normal problem, which is a minimal perturbation of the original optimization problem. We also present new results on the geometry of the minimal displacement vector. Funding: The research of H. H. Bauschke and W. M. Moursi was partially supported by Discovery Grants of the Natural Sciences and Engineering Research Council of Canada [Grants RGPIN-2018-03703 and RGPIN-2019-04803], respectively. [ABSTRACT FROM AUTHOR]

Model-based methods are popular in derivative-free optimization (DFO). In most of them, a single model function is built to approximate the objective function. This is generally based on the assumption that the objective function is one black box. However, some real-life and theoretical problems show that the objective function may consist of several black boxes. In those problems, the information provided by each black box may not be equal. In this situation, one can build multiple submodels that are then combined to become a final model. In this paper, we analyze the relation between the accuracy of those submodels and the model constructed through their operations. We develop a broad framework that can be used as a theoretical tool in model error analysis and future research in DFO algorithm design. Funding: Y. Chen's research is partially funded by the MITACS Globalink program. All authors research partially supported by NSERC of Canada Discovery [Grant 2018-03865]. [ABSTRACT FROM AUTHOR]