We study here the semisupervised k-clustering problem where information is available on whether pairs of objects are in the same or different clusters. This information is available either with certainty or with a limited level of confidence. We introduce the pair-wise confidence constraints clustering (PCCC) algorithm, which iteratively assigns objects to clusters while accounting for the information provided on the pairs of objects. Our algorithm uses integer programming for the assignment of objects, which allows us to include relationships as hard constraints that are guaranteed to be satisfied or as soft constraints that can be violated subject to a penalty. This flexibility distinguishes our algorithm from the state of the art, in which all pair-wise constraints are considered hard or all are considered soft. We developed an enhanced multistart approach and a model-size reduction technique for the integer program that contribute to the effectiveness and efficiency of the algorithm. Unlike existing algorithms, our algorithm scales to large-scale instances with up to 60,000 objects, 100 clusters, and millions of cannot-link constraints (which are the most challenging constraints to incorporate). We compare the PCCC algorithm with state-of-the-art approaches in an extensive computational study. Even though the PCCC algorithm is more general than the state-of-the-art approaches in its applicability, it outperforms the state-of-the-art approaches on instances with all hard or all soft constraints in terms of both run time and various metrics of solution quality. The code of the PCCC algorithm is publicly available on GitHub. History: Accepted by Ram Ramesh, Area Editor for Data Science and Machine Learning. Funding: The research of D. S. Hochbaum was supported by the AI Institute NSF Award [Grant 2112533]. 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.0419 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0419 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Abstract We present machine learning (ML) methods for automatically selecting a “best” performing fast algorithm for the capacitated vehicle routing problem (CVRP) with unit demands. Algorithm selection is to automatically choose among a portfolio of algorithms the one that is predicted to work best for a given problem instance, and algorithm configuration is to automatically select algorithm's parameters that are predicted to work best for a given problem instance. We present a framework incorporating both algorithm selection and configuration for a portfolio that includes the automatically configured “Sweep Algorithm,” the first generated feasible solution of the hybrid genetic search algorithm, and the Clarke and Wright algorithm. The automatically selected algorithm is shown here to deliver high‐quality feasible solutions within very small running times making it highly suitable for real‐time applications and for generating initial feasible solutions for global optimization methods for CVRP. These results bode well to the effectiveness of utilizing ML for improving combinatorial optimization methods.

Abstract We present here classes of integer programming problems that are solvable efficiently and with combinatorial flow algorithms. The problems are characterized by constraints that have either at most two variables per inequality that appear with opposite sign coefficients, or have in addition a third variable that appears only in one constraint. Such integer programs, referred to here as monotone IP2 or IP3, are shown to be solvable in polynomial time for polynomially bounded variables. This article demonstrates the vast applicability of IP2 and IP3 as models for integer programs in multiple scenarios. Since the problems are easily recognized, the knowledge of their structure enables one to determine easily that they are efficiently solvable. The variety of applications, that previously were not known to be solved as efficiently, underlies the importance of recognizing this structure and, if appropriate, formulating problems as monotone IP2 or IP3. Additionally, if there is flexibility in the modeling of an integer programming problem, the formulation choice as monotone IP2 or IP3 leads to efficient algorithms, whereas slightly different modeling choices would lead to NP‐hard problems.

We introduce a novel criterion in clustering that seeks clusters with limited range of values associated with each cluster's elements. In clustering or classification the objective is to partition a set of objects into subsets, called clusters or classes, consisting of similar objects so that different clusters are as dissimilar as possible. We propose a number of objective functions that employ the range of the clusters as part of the objective function. Several of the proposed objectives mimic objectives based on sums of similarities. These objective functions are motivated by image segmentation problems, where the diameter, or range of values associated with objects in each cluster, should be small. It is demonstrated that range‐based problems are in general easier, in terms of their complexity, than the analogous similarity‐sum problems. Several of the problems we present could therefore be viable alternatives to existing clustering problems which are NP‐hard, offering the advantage of efficient algorithms.

Recent large cancer studies have measured somatic alterations in an unprecedented number of tumours. These large datasets allow the identification of cancer-related sets of genetic alterations by identifying relevant combinatorial patterns. Among such patterns, mutual exclusivity has been employed by several recent methods that have shown its effectiveness in characterizing gene sets associated to cancer. Mutual exclusivity arises because of the complementarity, at the functional level, of alterations in genes which are part of a group (e.g., a pathway) performing a given function. The availability of quantitative target profiles, from genetic perturbations or from clinical phenotypes, provides additional information that can be leveraged to improve the identification of cancer related gene sets by discovering groups with complementary functional associations with such targets. In this work we study the problem of finding groups of mutually exclusive alterations associated with a quantitative (functional) target. We propose a combinatorial formulation for the problem, and prove that the associated computational problem is computationally hard. We design two algorithms to solve the problem and implement them in our tool UNCOVER. We provide analytic evidence of the effectiveness of UNCOVER in finding high-quality solutions and show experimentally that UNCOVER finds sets of alterations significantly associated with functional targets in a variety of scenarios. In particular, we show that our algorithms find sets which are better than the ones obtained by the state-of-the-art method, even when sets are evaluated using the statistical score employed by the latter. In addition, our algorithms are much faster than the state-of-the-art, allowing the analysis of large datasets of thousands of target profiles from cancer cell lines. We show that on two such datasets, one from project Achilles and one from the Genomics of Drug Sensitivity in Cancer project, UNCOVER identifies several significant gene sets with complementary functional associations with targets. Software available at: https://github.com/VandinLab/UNCOVER.

Several leading supervised and unsupervised machine learning algorithms require as input similarities between objects in a data set. Since the number of pairwise similarities grows quadratically with the size of the data set, it is computationally prohibitive to compute all pairwise similarities for large-scale data sets. The recently introduced methodology of “sparse computation” resolves this issue by computing only the relevant similarities instead of all pairwise similarities. To identify the relevant similarities, sparse computation efficiently projects the data onto a low-dimensional space where a similarity is considered relevant if the corresponding objects are close in this space. The relevant similarities are then computed in the original space. Sparse computation identifies close pairs by partitioning the low-dimensional space into grid blocks, and considering objects close if they fall in the same or adjacent grid blocks. This guarantees that all pairs of objects that are within a specified L∞distance are identified as well as some pairs that are within twice this distance. For very large data sets, sparse computation can have high runtime due to the enumeration of pairs of adjacent blocks. We propose here new geometric algorithms that eliminate the need to enumerate adjacent blocks. Our empirical results on data sets with up to 10 million objects show that the new algorithms achieve a significant reduction in runtime. The algorithms have applications in large-scale computational geometry and (approximate) nearest neighbor search. Python implementations of the proposed algorithms are publicly available.

Machine learning techniques that rely on pairwise similarities have proven to be leading algorithms for classification. Despite their good and robust performance, similarity-based techniques are rarely chosen for largescale data mining because the time required to compute all pairwise similarities grows quadratically with the size of the data set. To address this issue of scalability, we introduced a method called sparse computation, which efficiently generates a sparse similarity matrix that contains only significant similarities. Sparse computation achieves significant reductions in running time with minimal and often no loss in accuracy. However, for massively-large data sets even such a sparse similarity matrix may lead to considerable running times. In this paper, we propose an extension of sparse computation called sparse-reduced computation that not only avoids computing very low similarities but also avoids computing similarities between highly-similar or identical objects by compressing them to a single object. Our computational results show that sparse-reduced computation allows highly-accurate classification of data sets with millions of objects in seconds.

Leading machine learning techniques rely on inputs in the form of pairwise similarities between objects in the data set. The number of pairwise similarities grows quadratically in the size of the data set which poses a challenge in terms of scalability. One way to achieve practical efficiency for similarity-based techniques is to sparsify the similarity matrix. However, existing sparsification approaches consider the complete similarity matrix and remove some of the non-zero entries. This requires quadratic time and storage and is thus intractable for large-scale data sets. We introduce here a method called sparse computation that generates a sparse similarity matrix which contains only relevant similarities without computing first all pairwise similarities. The relevant similarities are identified by projecting the data onto a low-dimensional space in which groups of objects that share the same grid neighborhood are deemed of potential high similarity whereas pairs of objects that do not share a neighborhood are considered to be dissimilar and thus their similarities are not computed. The projection is performed efficiently even for massively large data sets. We apply sparse computation for the K-nearest neighbors algorithm (KNN), for graph-based machine learning techniques of supervised normalized cut and K-supervised normalized cut (SNC and KSNC) and for support vector machines with radial basis function kernels (SVM), on realworld classification problems. Our empirical results show that the approach achieves a significant reduction in the density of the similarity matrix, resulting in a substantial reduction in tuning and testing times, while having a minimal effect (and often none) on accuracy. The low-dimensional projection is of further use in massively large data sets where the grid structure allows to easily identify groups of “almost identical” objects. Such groups of objects are then replaced by representatives, thus reducing the size of the matrix. This approach is effective, as illustrated here for data sets comprising up to 8.5 million objects.

Several leading data mining and clustering algorithms rely on inputs in the form of pairwise similarities. Yet, since the number of potential pairwise similarities grows quadratically in the size of the data set, it is computationally prohibitive to apply such algorithms to large data sets. This paper addresses this challenge with a novel method of sparse computation that computes only the relevant similarities instead of the complete similarity matrix. The method employs an efficient algorithm that provides an “approximate Principal Component Analysis”. In the low-dimensional space generated, the concept of grid neighborhoods is applied in order to identify groups of objects with potentially high similarity. Unlike known sparsification approaches that generate first the full set of pairwise similarities and thus take at least quadratic time, the sparse computation method generates only the relevant similarities. Sparse computation can be utilized in any data mining or clustering algorithm that requires pairwise similarities, such as the k-nearest neighbors algorithm or the spectral method. This approach is contrasted with that of grid-based clustering algorithms in that grid neighborhoods proximity is used only to determine the entries in the sparse similarity matrix, not to identify the clusters. Indeed objects can belong to the same grid neighborhood while ending up in different clusters, or conversely, belong to different neighborhoods yet get clustered jointly. The applicability of sparse computation for binary classification is demonstrated here for the recently devised supervised normalized cut (SNC). Our empirical results show that the approach achieves a significant reduction in the density of the similarity matrix, resulting in a substantial reduction in running time, while having a minimal effect (and often none) on accuracy as compared to inputs using a complete similarity matrix.

The detection of illicit nuclear materials is a major tool in preventing and deterring nuclear terrorism. The detection task is extremely difficult because of physical limitations of nuclear radiation detectors, shielding by intervening cargo materials, and the presence of background noise. We aim at enhancing the capabilities of detectors with algorithmic methods specifically tailored for nuclear data. This paper describes a novel graph-theory-based methodology for this task. This research considers for the first time the utilization of supervised normalized cut (SNC) for data mining and classification of measurements obtained from plastic scintillation detectors that are of particularly low resolution. Specifically, the situation considered here is for when both energy spectra and the time dependence of such data are acquired. We present here a computational study, comparing the supervised normalized cut method with alternative classification methods based on support vector machine (SVM), specialized feature-reducing SVMs (i.e., 1-norm SVM, recursive feature elimination SVM, and Newton linear program SVM), and linear discriminant analysis (LDA). The study evaluates the performance of the suggested method in binary and multiple classification problems of nuclear data. The results demonstrate that the new approach is on par or superior in terms of accuracy and much better in computational complexity to SVM (with or without dimension or feature reduction) and LDA with principal components analysis as preprocessing. For binary and multiple classifications, the SNC method is more accurate, more robust, and is computationally more efficient by a factor of 2–80 than the SVM-based and LDA methods.

Key in the efforts to deter and prevent nuclear terrorism is the ability to detect the presence of possible nuclear threats in a given area. Resources capable of detecting such threats are limited, expensive, and only capable of scanning a certain total area in a given amount of time. This limit on the ability to detect nuclear threats makes imperative the development of efficient deployment strategies of the detection resources. In this work, we propose a Stackelberg game-based model to determine the optimal patrolling strategy of security assets over a network in the presence of a strategic adversary that seeks to place a nuclear threat on edges of the network. To efficiently solve this model, we introduce a novel decomposition of the problem which requires the solution of a multivehicle rural Chinese postman problem (CPP). Our theoretical contributions present hardness and approximation results for the k-vehicle rural CPP. Our computational results demonstrate the benefit of this decomposition for the nuclear threat detection security problem. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(3), 181–191 2014

Abstract The pseudoflow algorithm for solving the maximum flow and minimum cut problems was devised in Hochbaum (2008). The complexity of the algorithm was shown in (2008) to be O(nm log n). Chandran and Hochbaum, (2009) demonstrated that the pseudoflow algorithm is very efficient in practice, and that the highest label version of the algorithm tends to perform best. Here, we improve the running time of the highest label pseudoflow algorithm to O(n3) using simple data structures and to O(nm log (n2/m)) using the dynamic trees data structure. Both these algorithms use a new form of Depth‐First‐Search implementation that is likely to be fast in practice as well. In addition, we give a new simpler description of the pseudoflow algorithm by relating it to the simplex algorithm as applied to the maximum preflow problem defined here. The interpretation of the generic pseudoflow algorithm as a simplex‐like algorithm for the maximum preflow problem motivates the pseudoflow algorithm and highlights differences between the pseudoflow algorithm and the preflow‐push algorithm of Goldberg and Tarjan. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

Finding a largest Order-Preserving SubMatrix, OPSM, is an important problem arising in the discovery of patterns in gene expression. Ben-Dor et al. formulated the problem in Ben-Dor et al. [2003]. They further showed that the problem is NP-complete and provided a greedy heuristic for the problem. The complement of the OPSM problem, called MinOPSM, is to delete the least number of entries in the matrix so that the remaining submatrix is order preserving. We devise a 5-approximation algorithm for the MinOPSM based on a formulation of the problem as a quadratic, nonseparable set cover problem. An alternative formulation combined with a primal-dual algorithm improves the approximation factor to 3. The complexity of both algorithms for a matrix of size m × n is O ( m 2 n ). We further comment on the related biclustering problem.

MOTIVATION: The recent development of high-throughput drug profiling (high content screening or HCS) provides a large amount of quantitative multidimensional data. Despite its potentials, it poses several challenges for academia and industry analysts alike. This is especially true for ranking the effectiveness of several drugs from many thousands of images directly. This paper introduces, for the first time, a new framework for automatically ordering the performance of drugs, called fractional adjusted bi-partitional score (FABS). This general strategy takes advantage of graph-based formulations and solutions and avoids many shortfalls of traditionally used methods in practice. We experimented with FABS framework by implementing it with a specific algorithm, a variant of normalized cut-normalized cut prime (FABS-NC(')), producing a ranking of drugs. This algorithm is known to run in polynomial time and therefore can scale well in high-throughput applications. RESULTS: We compare the performance of FABS-NC(') to other methods that could be used for drugs ranking. We devise two variants of the FABS algorithm: FABS-SVM that utilizes support vector machine (SVM) as black box, and FABS-Spectral that utilizes the eigenvector technique (spectral) as black box. We compare the performance of FABS-NC(') also to three other methods that have been previously considered: center ranking (Center), PCA ranking (PCA), and graph transition energy method (GTEM). The conclusion is encouraging: FABS-NC(') consistently outperforms all these five alternatives. FABS-SVM has the second best performance among these six methods, but is far behind FABS-NC('): In some cases FABS-NC(') produces over half correctly predicted ranking experiment trials than FABS-SVM. AVAILABILITY: The system and data for the evaluation reported here will be made available upon request to the authors after this manuscript is accepted for publication.

We consider the problem of energy-efficient transmission in multi-flow multihop cooperative wireless networks. Although the performance gains of cooperative approaches are well known, the combinatorial nature of these schemes makes it difficult to design efficient polynomial-time algorithms for joint routing, scheduling and power control. This becomes more so when there is more than one flow in the network. It has been conjectured by many authors, in the literature, that the multiflow problem in cooperative networks is an NP-hard problem. In this paper, we formulate the problem, as a combinatorial optimization problem, for a general setting of k-flows, and formally prove that the problem not only NP-hard but it is o(n1/7-ε) inapproxmiable. To our knowledge, the results in this paper provide the first such inapproxmiablity proof in the context of multiflow cooperative wireless networks. We further prove that for a special case of k = 1 the solution is a simple path, and offer a polynomial time algorithm for jointly optimizing routing, scheduling and power control.

Abstract The input to an inverse shortest path lengths problem (ISPL) consists of a graph G with arc weights, and a collection of source‐sink pairs with prescribed distances that do not necessarily conform to the shortest path lengths in G. The goal is to modify the arc weights, subject to a penalty on the deviation from the given weights, so that the shortest path lengths are equal to the prescribed values. We show that although ISPL is an NP‐hard problem, several ISPL classes are polynomially solvable. These cases include ISPL where the collection of the pairs share a single source and all other nodes as destinations (the single‐source all‐sink problem SAISPL). For the case where the collection contains a single node pair (the single‐source single‐sink problem SSISPL), we identify conditions on the uniformity of the penalty functions and on the original arc weights, which make SSISPL polynomially solvable. These results cannot be strengthened significantly as the general single‐source ISPL is NP‐hard and the all‐sink case, with more than one source, is also NP‐hard. We further provide a convex programming formulation for a relaxation of ISPL in which the shortest path lengths are only required to be no less than the given values (LBISPL). It is demonstrated how this compact formulation leads to efficient algorithms for ISPL. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

In partitioning, clustering, and grouping problems, a typical goal is to group together similar objects, or pixels in the case of image processing. At the same time, another goal is to have each group distinctly dissimilar from the rest and possibly to have the group size fairly large. These goals are often combined as a ratio optimization problem. One example of such a problem is a variant of the normalized cut problem, another is the ratio regions problem. We devise here the first polynomial time algorithms solving optimally the ratio region problem and the variant of normalized cut, as well as a few other ratio problems. The algorithms are efficient and combinatorial, in contrast with nonlinear continuous approaches used in the image segmentation literature, which often employ spectral techniques. Such techniques deliver solutions in real numbers which are not feasible to the discrete partitioning problem. Furthermore, these continuous approaches are computationally expensive compared to the algorithms proposed here. The algorithms presented here use as a subroutine a minimum s,t-cut procedure on a related graph which is of polynomial size. The output consists of the optimal solution to the respective ratio problem, as well as a sequence of nested solutions with respect to any relative weighting of the objectives of the numerator and denominator.

This paper is focused on the Co-segmentation problem [1] - where the objective is to segment a similar object from a pair of images. The background in the two images may be arbitrary; therefore, simultaneous segmentation of both images must be performed with a requirement that the appearance of the two sets of foreground pixels in the respective images are consistent. Existing approaches [1, 2] cast this problem as a Markov Random Field (MRF) based segmentation of the image pair with a regularized difference of the two histograms - assuming a Gaussian prior on the foreground appearance [1] or by calculating the sum of squared differences [2]. Both are interesting formulations but lead to difficult optimization problems, due to the presence of the second (histogram difference) term. The model proposed here bypasses measurement of the histogram differences in a direct fashion; we show that this enables obtaining efficient solutions to the underlying optimization model. Our new algorithm is similar to the existing methods in spirit, but differs substantially in that it can be solved to optimality in polynomial time using a maximum flow procedure on an appropriately constructed graph. We discuss our ideas and present promising experimental results.

Abstract The facility terminal cover problem is a generalization of the vertex cover problem. The problem is to “cover” the edges of an undirected graphG= (V,E) where each edgeeis associated with a non‐negative demandde. An edgee=u,vis covered if at least one of its endpoint vertices is allocated capacity of at leastde. Each vertexvis associated with a non‐negative weightwv. The goal is to allocate capacitycv≥ 0 to each vertexvso that all edges are covered and the total allocation cost,$\sum\limits_{v\in V}w_{v}c_{v}$, is minimized. A recent paper by Xu et al. [Networks 50 (2007), 118‐126], studied this problem, and presented a 2e‐ approximation algorithm for this problem forethe base of the natural logarithm. We generalize here the facility terminal cover problem to the multi‐integer set cover, and relate that problem to the set cover problem, which it generalizes, and the multi‐cover problem. We present a Δ‐approximation algorithm for the multi‐integer set cover problem, for Δ the maximum coverage. This demonstrates that even though the multi‐integer set cover problem generalizes the set cover problem, the same approximation ratio holds. In the special case of the facility terminal cover problem this yields a 2‐approximation algorithm, and with run time dominated by the sorting of the edge demands. This approximation algorithm improves considerably on the result of Xu et al. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

Abstract Motivated by a problem arising in the design of telecommunications networks using the SONET standard, we consider the problem of covering all edges of a graph using subgraphs that contain at most k edges with the objective of minimizing the total number of vertices in the subgraphs. We show that the problem is 𝒩 𝒫 ‐hard when k ≥ 3 and present a linear‐time ‐approximation algorithm. For even k values, we present an approximation scheme with a reduced ratio but with increased complexity. © 2002 Wiley Periodicals, Inc.

Many applications in the area of production and statistical estimation are problems of convex optimization subject to ranking constraints that represent a given partial order. This problem, which we call the convex cost closure (CCC) problem, is a generalization of the known maximum (or minimum) closure problem and the isotonic regression problem. For a CCC problem on n variables and m constraints we describe an algorithm that has the complexity of the minimum cut problem plus the complexity of finding the minima of up to n convex functions. Since the CCC problem is a generalization of both minimum cut and minimization of n convex functions, this complexity is the fastest one possible. For the quadratic problem the complexity of our algorithm is strongly polynomial, $O(mn\log {\frac{n^2}{m}})$. For the isotonic regression problem the complexity is O(n log U,) for U the largest range for a variable value.

Abstract The minimax problem is a new optimization problem which substitutes maximum for addition in the constraint inequalities of a linear program. We show how a problem with n variables and m constraints can be reduced to a set cover problem with nm variables and m constraints. We define the mountain property on the coefficients in each column of the constraint matrix of a minimax problem and its generalization—the bitonic property. It is shown that these are equivalent, respectively, to set cover problems with consecutive 1's in each column or circular 1's in each column thus solving the periodic scheduling problem. We present a shortest path algorithm to solve a minimax problem with the mountain property in time O(mn + log m). For bitonic matrix problems, we present an algorithm of complexity O(m2(n + log n)). The same algorithms are used to solve a set cover problem on v sets and r elements to be covered in O(v + r log r) for a problem with consecutive 1's in each column and in O(v(v + r log r)) for a problem with circular 1's in each column. We further establish that r is at least \documentclass{article}\pagestyle{empty} \begin{document}$\Omega(\sqrt{v})$\end{document} and at most O(v). We also provide an efficient algorithm for recognizing bitonic matrices in O(mn log m) time. © 2002 Wiley Periodicals, Inc.

We consider the bounded cycle-cover problem, which is to find a minimum cost cycle cover of a two-connected graph such that no cycle in the cover contains more than a prescribed numbered of edges. This problem arises in the design of fiber-optic telecommunications networks that employ multiple self-healing rings to provide routing for communication traffic, even in the event of a fiber cut or other type of link failure. We present this problem, along with several related problems, and develop heuristic algorithms that find near optimal solutions for the bounded cycle-cover problem based on solution techniques for these related problems. Empirical results of these algorithms, applied to randomly generated problem instances, are presented and discussed.

Problems of statistical inference involve the adjustment of sample observations so they fit some a priori rank requirements, or order constraints. In such problems, the objective is to minimize thedeviation costfunction that depends on the distance between the observed value and the modify value. In Markov random field problems, there is also a pairwise relationship between the objects. The objective in Markov random field problem is to minimize the sum of the deviation cost function and a penalty function that grows with the distance between the values of related pairs---separation function.We discuss Markov random fields problems in the context of a representative application---theimage segmentationproblem. In this problem, the goal is to modify color shades assigned to pixels of an image so that the penalty function consisting of one term due to the deviation from the initial color shade and a second term that penalizes differences in assigned values to neighboring pixels is minimized. We present here an algorithm that solves the problem in polynomial time when the deviation function is convex and separation function is linear; and in strongly polynomial time when the deviation cost function is linear, quadratic or piecewise linear convex with few pieces (where “few” means a number exponential in a polynomial function of the number of variables and constraints). The complexity of the algorithm for a problem onnpixels or variables,madjacency relations or constraints, and range of variable values (colors)U, isO(T(n,m) +nlogU) whereT(n,m) is the complexity of solving the minimum s, t cut problem on a graph withnnodes andmarcs. Furthermore, other algorithms are shown to solve the problem with convex deviation and convex separation in running timeO(mnlognlognU) and the problem with nonconvex deviation and convex separation in running timeO(T(nU, mU). The nonconvex separation problem is NP-hard even for fixed value ofU.For the family of problems with convex deviation functions and linear separation function, the algorithm described here runs in polynomial time which is demonstrated to be fastest possible.

Abstract We present an algorithm for solving the minimum‐cut problem on closure graphs without maintaining flow values. The algorithm is based on an optimization algorithm for the open‐pit mining problem that was presented in 1964 (and published in 1965) by Lerchs and Grossmann. The Lerchs—Grossmann algorithm (LG algorithm) solves the maximum closure which is equivalent to the minimum‐cut problem. Yet, it appears substantially different from other algorithms known for solving the minimum‐cut problem and does not employ any concept of flow. Instead, it works with sets of nodes that have a natural interpretation in the context of maximum closure in that they have positive total weight and are closed with respect to some subgraph. We describe the LG algorithm and study its features and the new insights it reveals for the maximum‐closure problem and the maximum‐ flow problem. Specifically, we devise a linear time procedure that evaluates a feasible flow corresponding to any iteration of the algorithm. We show that while the LG algorithm is pseudopolynomial, our variant algorithms have complexity of O ( mn log n ), where n is the number of nodes and m is the number of arcs in the graph. Modifications of the algorithm allow for efficient sensitivity and parametric analysis also running in time O ( mn log n ). © 2001 John Wiley & Sons, Inc.

The bottleneck graph partition problem is to partition the nodes of a graph into two equally sized sets, so that the maximum edge weight in the cut separating the two sets is minimum. Whereas the graph partition problem, where the sum of the edge weights in the cut is to be minimized, is NP-hard, the bottleneck version is polynomial. This paper describes an O(n2 log n) algorithm for the bottleneck graph partition problem, where n is the number of nodes in the graph. We point out two interesting issues related to dynamic algorithms. We also generalize our polynomiality result (for fixed k) to the bottleneck k-cut problem with specified vertices and bounded components. © 1996 John Wiley & Sons, Inc.

The problem of covering edges and vertices in a graph (or in a hypergraph) was motivated by a problem arising in the context of the component assembly problem. The problem is as follows: given a graph and a clique size k, find the minimum number of k-cliques such that all edges and vertices of the graph are covered by (included in) the cliques. This paper provides a collection of approximation algorithms for various clique sizes with proven worst-case bounds. The problem has a natural extension to hypergraphs, for which we consider one particular class. The k-clique covering problem can be formulated as a set coveringg problem. It is shown that the algorithms we design, which exploit the structure of this special set covering problem, have better performance than those derived from direct applications of general purpose algorithms for the set covering. In particular, these special classes of set covering problems can be solved with better worst-case bounds and/or complexity than if treated as general set covering problems.

The problem of optimal test compression is to derive, from a given set of test vectors, a smallest possible subset of test vectors that still test for the same collection of faults. This achieves optimal compression and largest reduction possible in test time relative to the original set of test vectors. We present a new approach based on the modeling of the problem as the Set Cover problem. Additionally, the approach implies an ordering of the faults according to the difficulty of covering them with the given set of test vectors. As such it can be used to facilitate the finding of a solution to the ultimate smallest test-set-the compression of the set of all possible test vectors. Our approach highlights the potential usefulness of integer programming techniques in testing and design.

Article An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane Share on Authors: Naveen Garg Department of Computer Science and Engineering, Indian Institute of Technology, Delhi Department of Computer Science and Engineering, Indian Institute of Technology, DelhiView Profile , Dorit S. Hochbaum Industrial Engineering and Operations Research, University of California, Berkeley, CA Industrial Engineering and Operations Research, University of California, Berkeley, CAView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 432–438https://doi.org/10.1145/195058.195218Online:23 May 1994Publication History 14citation425DownloadsMetricsTotal Citations14Total Downloads425Last 12 Months11Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The authors present an $O(mn^2 \log m)$ algorithm for solving feasibility in linear programs with up to two variables per inequality which is derived directly from the Fourier–Motzkin elimination method. (The number of variables and inequalities are denoted by n and m, respectively.) The running time of the algorithm dominates that of the best known algorithm for the problem, and is far simpler. Integer programming on monotone inequalities, i.e., inequalities where the coefficients are of opposite sign, is then considered. This problem includes as a special case the simultaneous approximation of a rational vector with specified accuracy, which is known to be NP-complete. However, it is shown that both a feasible solution and an optimal solution with respect to an arbitrary objective function can be computed in pseudo-polynomial time.

The polynomiality of nonlinear separable convex (concave) optimization problems, on linear constraints with a matrix with “small” subdeterminants, and the polynomiality of such integer problems, provided the inteter linear version of such problems ins polynomial, is proven. This paper presents a general-purpose algorithm for converting procedures that solves linear programming problems. The conversion is polynomial for constraint matrices with polynomially bounded subdeterminants. Among the important corollaries of the algorithm is the extension of the polynomial solvability of integer linear programming problems with totally unimodular constraint matrix, to integer-separable convex programming. An algorithm for finding a ε-accurate optimal continuous solution to the nonlinear problem that is polynomial in log(1/ε) and the input size and the largest subdeterminant of the constraint matrix is also presented. These developments are based on proximity results between the continuous and integral optimal solutions for problems with any nonlinear separable convex objective function. The practical feature of our algorithm is that is does not demand an explicit representation of the nonlinear function, only a polynomial number of function evaluations on a prespecified grid.

The matching problem is to find a maximum collection of mutually nonadjacent edges in a graph. An algorithm is presented that delivers a perfect matching in a random graph almost surely. The expected running time of this algorithm is $O( n \log_e (1/p) + n)$, where n is the number of vertices in the graph and where p is the probability of an edge. This running time is faster than $O(n \log_e n)$, the expected running time of the best randomized algorithm of Angluin and Valiant.

The k-cut problem is to find a partition of a graph into k nonempty components, such that the number of edges between components is minimum. A random graph in $\mathcal{G}_{n,p}$ is a simple graph on n vertices with each pair of vertices connected by an edge with probability p. It is proved that, when k is fixed, a k-cut of almost every graph from $\mathcal{G}_{n,p} $ consists of $k - 1$ isolated vertices and one component on the remaining $n - k + 1$ vertices. An important outcome of this property is a linear algorithm that derives the minimum k-cut in such graphs, almost certainly.

Abstract This article addresses a problem that comes up frequently in network design, and routing. A source is to distribute flows to nodes in the network. Sending flow along an arc involves a fixed cost for using the arc and a variable cost for each ujnit of flow. We show tht the problem of finding a minimum cost collection of arcs along which flows will be directed is an NP‐hard problem. We describe a procedure of solving the problem to optimality and several heuristics. In particular, we conclude that the use of polynomially derived Lagrange multipliers yields good quality solutions and bounds and can be implemented in a distributed processing mode in the network.

The k-cut problem is to find a partition of an edge weighted graph into k nonempty components, such that the total edge weight between components is minimum. This problem is NP-complete for arbitrary k and its version involving fixing a vertex in each component is NP hard even for k=3. A polynomial algorithm for the case of a fixed k is presented.>

We present a polynomial approximation scheme for the minimum makespan problem on uniform parallel processors. More specifically, the problem is to find a schedule for a set of independent jobs on a collection of machines of different speeds so that the last job to finish is completed as quickly as possible. We give a family of polynomial-time algorithms $\{ {A_\varepsilon } \}$ such that $A_\varepsilon $ delivers a solution that is within a relative error $\varepsilon $ of the optimum. This is a dramatic improvement over previously known algorithms; the best performance guarantee previously proved for a polynomial-time algorithm ensured a relative error no more than 40 percent. The technique employed is the dual approximation approach, where infeasible but superoptimal solutions for a related (dual) problem are converted to the desired feasible but possibly suboptimal solution.

The problem of scheduling a set of n jobs on m identical machines so as to minimize the makespan time is perhaps the most well-studied problem in the theory of approximation algorithms for NP-hard optimization problems. In this paper the strongest possible type of result for this problem, a polynomial approximation scheme, is presented. More precisely, for each ε, an algorithm that runs in time O (( n /ε) 1/ε 2 ) and has relative error at most ε is given. In addition, more practical algorithms for ε = 1/5 + 2 - k and ε = 1/6 + 2 - k , which have running times O ( n ( k + log n )) and O ( n ( km 4 + log n )) are presented. The techniques of analysis used in proving these results are extremely simple, especially in comparison with the baroque weighting techniques used previously. The scheme is based on a new approach to constructing approximation algorithms, which is called dual approximation algorithms, where the aim is to find superoptimal, but infeasible, solutions, and the performance is measured by the degree of infeasibility allowed. This notion should find wide applicability in its own right and should be considered for any optimization problem where traditional approximation algorithms have been particularly elusive.

In this paper a powerful, and yet simple, technique for devising approximation algorithms for a wide variety of NP-complete problems in routing, location, and communication network design is investigated. Each of the algorithms presented here delivers an approximate solution guaranteed to be within a constant factor of the optimal solution. In addition, for several of these problems we can show that unless P = NP, there does not exist a polynomial-time algorithm that has a better performance guarantee.

The problem of scheduling a set of n jobs on m identical machines so as to minimize the makespan time is perhaps the most well-studied problem in the theory of approximation algorithms for NP-hard optimization problems. In this paper we present the strongest possible type of result for this problem, a polynomial approximation scheme. More precisely, for each ε, we give an algorithm that runs in time O((n/ε)1/ε2) and has relative error at most ε. For algorithms that are polynomial in n and m, the strongest previously-known result was that the MULTIFIT algorithm delivers a solution with no worse than 20% relative error. In addition, we present a refinement of our scheme in the case where the performance guarantee is equal to that of MUL-TIFIT, that yields an algorithm that is both more efficient and easier to analyze than MULTIFIT. In this case, in order to guarantee a maximum relative error of 1/5+2-k, the algorithm runs in O(n(k+logn)) time. The scheme is based on a new approach to constructing approximation algorithms, which we call dual approximation algorithms, where the aim is find superoptimal, but infeasible solutions, and the performance is measured by the degree of infeasibility allowed. This notion should find wide applicability in its own right, and should be considered for any optimization problem where traditional approximation algorithms have been particularly elusive.

A unified and powerful approach is presented for devising polynomial approximation schemes for many strongly NP-complete problems. Such schemes consist of families of approximation algorithms for each desired performance bound on the relative error ε > Ο, with running time that is polynomial when ε is fixed. Though the polynomiality of these algorithms depends on the degree of approximation ε being fixed, they cannot be improved, owing to a negative result stating that there are no fully polynomial approximation schemes for strongly NP-complete problems unless NP = P. The unified technique that is introduced here, referred to as the shifting strategy, is applicable to numerous geometric covering and packing problems. The method of using the technique and how it varies with problem parameters are illustrated. A similar technique, independently devised by B. S. Baker, was shown to be applicable for covering and packing problems on planar graphs.

In this paper we investigate a powerful, and yet simple, technique for devising approximation algorithms for a wide variety of NP-complete problems in routing, location, and communication network design. Each of the algorithms presented here delivers an approximate solution guaranteed to be within a constant factor of the optimal solution. In addition, for several of these problems we can show that unless P=NP, there does not exist a polynomial-time algorithm that has a better performance guarantee.

We propose a heuristic that delivers in $O(n^3 )$ steps a solution for the set covering problem the value of which does not exceed the maximum number of sets covering an element times the optimal value.

Recent years have wRnessed an increasing number of systems of computers that are distributed geographically and connected by high-capacRy commumcauons channels in designing and managing such a network one must decide where to place copies of the various databases available to the users of the system This decision must trade off the cost of accessing a database, which ~s reduced by additional copies, against the cost of storing and updating the additional copies An optimizing algorithm for a general model of this problem ms described, and successful computational experience with large real examples is reported KEY WORDS AND PHRASES database location, mathematical programming models CR CATEGORIES 3 72, 4 33 IntroducuonRecent years have witnessed an increasing number of systems of computers that are distributed geographically and connected by high-capacity commumcations channels.The best known example is the network developed under the sponsorship of the Advanced Research Projects Agency (ARPA).These computer networks provide a number of benefits.They make possible the sharing of expensive specialized hardware, software, and databases, and they facilitate collaboration between geographically separated researchers studying the same problem.A number of difficult location problems arise in the design and management of such networks, including the problem of where to place copies of the various databases available to the users of the system.This decision must trade off the cost of accessing a database, which is reduced by additional copies, against the cost of storing and updating the additional copies.Other performance characteristics of the system are also affected by the positioning of database copies, including reliability of the system and opportumties for the parallel processing of requests against the database in order to reduce response time.This problem has received substantial attention.Previous literature (see Elam and Stutz [4] and Levin [13] for critical reviews) has been principally concerned with formulating appropriate models of the problem.Virtually all of these models are integer or mixedinteger linear programs.The more realistic models also belong to the notoriously difficult class of NP-hard problems, so we would expect the computation of an optimal solution to be a challenging task.Nevertheless, there has been little attention given to algorithm development in previous research.Computational experience with the few simple algorithms that have been proposed has been scant and limited to very small problems.This paper is intended to correct this gap in previous research.We describe an opumizing