In this paper, we introduce a new class of hybrid inertial and contraction proximal point algorithm for the variational inclusion problem of the sum of two mappings in Hilbert spaces. We prove that the proposed algori...
详细信息
In this paper, we introduce a new class of hybrid inertial and contraction proximal point algorithm for the variational inclusion problem of the sum of two mappings in Hilbert spaces. We prove that the proposed algorithm converges strongly to a solution of the variational inclusion problem whenever its solution set is nonempty and the single-valued mapping f is Lipschitz continuous, monotone, and the set-valued mapping A is maximal monotone in infinite-dimensional real Hilbert spaces. Our work generalize and extend some related existing results in the literature. Finally, we illustrate the numerical performance of our algorithm 1 and we give an application to the split feasibility problem.
In this study, we develop a branch-and-cut algorithm for the vehicle routing problem with twodimensional loading constraints. A separation algorithm is proposed to simultaneously identify infeasible set inequalities a...
详细信息
In this study, we develop a branch-and-cut algorithm for the vehicle routing problem with twodimensional loading constraints. A separation algorithm is proposed to simultaneously identify infeasible set inequalities and weak capacity inequalities for fractional solutions. Classic capacitated vehicle routing problem (CVRP) inequalities are adopted as well. A branch-and-cut (B&C) algorithm is built to solve the problem. Experimental results illustrate that the algorithm is competitive. In particular, we solve 6 instances to optimality for the first time. Extensive computational analysis is also conducted to reveal the impact of infeasible set inequalities, the branching strategy, and the packing algorithms on the B&C algorithm. (c) 2022 Elsevier B.V. All rights reserved.
In the k-cut problem, we want to find the lowest-weight set of edges whose deletion breaks a given (multi)graph into k connected components. algorithms of Karger and Stein can solve this in roughly O(n(2)k) time. Howe...
详细信息
In the k-cut problem, we want to find the lowest-weight set of edges whose deletion breaks a given (multi)graph into k connected components. algorithms of Karger and Stein can solve this in roughly O(n(2)k) time. However, lower bounds from conjectures about the k-clique problem imply that Omega(n((1-o(1))k)) time is likely needed. Recent results of Gupta, Lee, and Li have given new algorithms for general k-cut in n(1.98k)(+O) (1) time, as well as specialized algorithms with better performance for certain classes of graphs (e.g., for small integer edge weights). In this work, we resolve the problem for general graphs. We show that the contraction algorithm of Karger outputs any fixed k-cut of weight alpha lambda k with probability Omega(k) (n(k)), where lambda k denotes the minimiun k-cut weight. This also gives an extremal bound of O-k(n(k)) on the number of minimum k-cuts and an algorithm to compute lambda(k) with roughly n(k) polylog(n) runtime. Both are tight up to lower-order factors, with the algorithmic lower bound assuming hardness of max-weight k-clique. The first main ingredient in our result is an extremal bound on the number of cuts of weight less than 2 lambda(k)/k, using the Sunflower lemma. The second ingredient is a fine-grained analysis of how the graph shrinks-and how the average degree evolves-in the Karger process.
Minimum cut problems are among the most classical problems in Combinatorial Optimization and are used in a wide set of applications. Some of the best-known efficiently solvable variants include global mininmum cuts, m...
详细信息
Minimum cut problems are among the most classical problems in Combinatorial Optimization and are used in a wide set of applications. Some of the best-known efficiently solvable variants include global mininmum cuts, minimum s-t cuts, and minimum odd cuts in undirected graphs. We study a problem class that can be seen to generalize the above variants, namely finding congruency-constrained minimum cuts, i.e., we consider cuts whose number of vertices is congruent to r modulo m, for some integers r and m. Apart from being a natural generalization of odd cuts, congruency-constrained minimum cuts exhibit an interesting link to a long-standing open problem in Integer Programming, namely whether integer programs described by an integer constraint matrix with bounded subdeterminants can be solved efficiently. We develop a new contraction technique inspired by Karger's celebrated contraction algorithm for minimum cuts, which, together with further insights, leads to a polynomial time randomized approximation scheme for congruency-constrained minimum cuts for any constant modulus m. Instead of contracting edges of the original graph, we use splitting-off techniques to create an auxiliary graph on a smaller vertex set, which is used for performing random edge contractions. This way, a well-structured distribution of candidate pairs of vertices to be contracted is obtained, where the involved pairs are generally not connected by an edge. As a byproduct, our technique reveals new structural insights into near-minimum odd cuts, and, more generally, near-minimum congruency-constrained cuts.
Karger (SIAM Journal on Computing, 1999) developed the first fully-polynomial approximation scheme to estimate the probability that a graph G becomes disconnected, given that its edges are removed independently with p...
详细信息
Karger (SIAM Journal on Computing, 1999) developed the first fully-polynomial approximation scheme to estimate the probability that a graph G becomes disconnected, given that its edges are removed independently with probability p. This algorithm runs in n5+o(1)E-3 time to obtain an estimate within relative error E. We improve this run-time through algorithmic and graph-theoretic advances. First, there is a certain key sub-problem encountered by Karger, for which a generic estimation procedure is employed;we show that this has a special structure for which a much more efficient algorithm can be used. Second, we show better bounds on the number of edge cuts which are likely to fail. Here, Karger's analysis uses a variety of bounds for various graph parameters;we show that these bounds cannot be simultaneously tight. We describe a new graph parameter, which simultaneously influences all the bounds used by Karger, and obtain much tighter estimates of the cut structure of G. These techniques allow us to improve the runtime to n3+o(1)E-2;our results also rigorously prove certain experimental observations of Karger and Tai (Proc. ACM-SIAM Symposium on Discrete algorithms, 1997). Our rigorous proofs are motivated by certain non-rigorous differential-equation approximations which, however, provably track the worst-case trajectories of the relevant parameters. A key driver of Karger's approach (and other cut-related results) is a bound on the number of small cuts: we improve these estimates when the min-cut size is small and odd, augmenting, in part, a result of Bixby (Bulletin of the AMS, 1974).
暂无评论