In this paper we describe a cutting plane algorithm to solve max-cut problems on complete graphs. We show that the separation problem over the cut polytope can be reduced to the separation problem over the cut cone an...
详细信息
In this paper we describe a cutting plane algorithm to solve max-cut problems on complete graphs. We show that the separation problem over the cut polytope can be reduced to the separation problem over the cut cone and we give a separation algorithm for a class of inequalities valid over the cut cone:the hypermetric *** results are given.
We study the relationship between the vertices of an up-monotone polyhedron R and those of the polytope P obtained by truncating R with the unit hypercube. When R has binary vertices, we characterize the vertices of P...
详细信息
We study the relationship between the vertices of an up-monotone polyhedron R and those of the polytope P obtained by truncating R with the unit hypercube. When R has binary vertices, we characterize the vertices of P in terms of the vertices of R , show their integrality, and prove that the 1-skeleton of R is an induced subgraph of the 1-skeleton of P . We conclude by applying our findings to settle a claim in the original paper.
作者：
MUROTA, KUNIV TOKYO
DEPT MATH ENGN & INFORMAT PHYSTOKYO 113JAPAN UNIV BONN
DISKRETE MATH FORSCHUNGSINSTW-5300 BONNGERMANY
Let A(x) = (A(ij)(x)) be a square matrix with A(ij) being a polynomial in x. This paper proposes ''combinatorial relaxation-'' type algorithms for computing the degree of the determinant delta(A) = deg...
详细信息
Let A(x) = (A(ij)(x)) be a square matrix with A(ij) being a polynomial in x. This paper proposes ''combinatorial relaxation-'' type algorithms for computing the degree of the determinant delta(A) = deg(x) det A(x) based on its combinatorial upper bound <(delta)over cap>(A), which is defined in terms of the maximum weight of a perfect matching in an associated graph. The graph is bipartite for a general square matrix A and nonbipartite for a skew-symmetric A. The algorithm transforms A to another matrix A', for which delta(A) = delta(A') = <(delta)over cap>(A') with successive elementary operations. The algorithm is efficient, making full use of the fast algorithms for weighted matchings;it is combinatorial in almost all cases (or generically) and invokes algebraic elimination routines only when accidental numerical cancellations occur. It is shown in passing that for a (skew-)symmetric polynomial matrix A(x) there exists a unimodular matrix U(x) such that A'(x) = U(x)A(x)U(x)(T) satisfies delta(A) = delta(A') = <(delta)over cap>(A').
The (combinatorial) diameter of a polytope P subset of R-d is the maximum value of a shortest path between a pair of vertices on the 1-skeleton of P, that is the graph where the nodes are given by the 0-dimensional fa...
详细信息
ISBN:
(纸本)9781538642306
The (combinatorial) diameter of a polytope P subset of R-d is the maximum value of a shortest path between a pair of vertices on the 1-skeleton of P, that is the graph where the nodes are given by the 0-dimensional faces of P, and the edges are given the 1-dimensional faces of P. The diameter of a polytope has been studied from many different perspectives, including a computational complexity point of view. In particular, [Frieze and Teng, 1994] showed that computing the diameter of a polytope is (weakly) NP-hard. In this paper, we show that the problem of computing the diameter is strongly NP-hard even for a polytope with a very simple structure: namely, the fractional matching polytope. We also show that computing a pair of vertices at maximum shortest path distance on the 1-skeleton of this polytope is an APX-hard problem. We prove these results by giving an exact characterization of the diameter of the fractional matching polytope, that is of independent interest.
Given a weighted simple graph, the minimum weighted maximal matching (MWMM) problem is the problem of finding a maximal matching of minimum weight. The MWMM problem is NP-hard in general, but is polynomial-time solvab...
详细信息
Given a weighted simple graph, the minimum weighted maximal matching (MWMM) problem is the problem of finding a maximal matching of minimum weight. The MWMM problem is NP-hard in general, but is polynomial-time solvable in some special classes of graphs. For instance, it has been shown that the MWMM problem can be solved in linear time in trees when all the edge weights are equal to one. In this paper, we show that the convex hull of the incidence vectors of maximal matchings (the maximal matching polytope) in trees is given by the polytope described by the linear programming relaxation of a recently proposed integer programming formulation. This establishes the polynomial-time solvability of the MWMM problem in weighted trees. The question of whether or not the MWMM problem can be solved in linear time in weighted trees is open.
Traffic in communication networks fluctuates heavily over time. Thus, to avoid capacity bottlenecks, operators highly overestimate the traffic volume during network planning. In this article we consider telecommunicat...
详细信息
Traffic in communication networks fluctuates heavily over time. Thus, to avoid capacity bottlenecks, operators highly overestimate the traffic volume during network planning. In this article we consider telecommunication network design under traffic uncertainty, adapting the robust optimization approach of Bertsimas and Sim [Oper Res 52 (2004), 3553]. We present two different mathematical formulations for this problem, provide valid inequalities, study the computational implications, and evaluate the realized robustness. To enhance the performance of the mixed-integer programming solver, we derive robust cutset inequalities generalizing their deterministic counterparts. Instead of a single cutset inequality for every network cut, we derive multiple valid inequalities by exploiting the extra variables available in the robust formulations. We show that these inequalities define facets under certain conditions and that they completely describe a projection of the robust cutset polyhedron if the cutset consists of a single edge. For realistic networks and live traffic measurements, we compare the formulations and report on the speed-up achieved by the valid inequalities. We study the price of robustness and evaluate the approach by analyzing the real network load. The results show that the robust optimization approach has the potential to support network planners better than present methods. (c) 2013 Wiley Periodicals, Inc. NETWORKS, 2013
We present and evaluate a specific way to generate good start solutions for local search. The start solution is computed from a certain LP, which is related to the underlying problem. We consider three optimization pr...
详细信息
We present and evaluate a specific way to generate good start solutions for local search. The start solution is computed from a certain LP, which is related to the underlying problem. We consider three optimization problems: the directed MAX-CUT problem with a source and a sink and two variations of the MAX-k-SAT problem with k = 2 and k = 3. To compare our technique, we run local search repeatedly with random start *** technique produces, consistently, final solutions whose objective values are not too far from the best solutions from repeated random starts. The surprising degree of stability and uniformity of this result throughout all of our experiments on various classes of instances strongly suggests that we have consistently achieved nearly optimal solutions. On the other hand, the runtime of our technique is rather small, so the technique is very efficient and probably quite accurate.
暂无评论