Graph partition problems have been investigated extensively in combinatorial optimization. In this work, we consider an important graph partition problem which has applications in the design of VLSI circuits, namely, ...
详细信息
Graph partition problems have been investigated extensively in combinatorial optimization. In this work, we consider an important graph partition problem which has applications in the design of VLSI circuits, namely, the balanced Max-3-Uncut problem. We formulate the problem as a discrete linear program with complex variables and propose an approximation algorithm with an approximation ratio of 0.3456 using a semidefiniteprogramming rounding technique along with a greedy swapping step afterwards to guarantee the balanced constraint. Our analysis utilizes a bivariate function, rather than the univariate function in previous work.
In this paper, we consider the balanced Max-3-Uncut problem which has several applications in the design of VLSI circuits. We propose a complex discrete linear program for the balanced Max-3-Uncut problem. Applying th...
详细信息
ISBN:
(纸本)9783319087832;9783319087825
In this paper, we consider the balanced Max-3-Uncut problem which has several applications in the design of VLSI circuits. We propose a complex discrete linear program for the balanced Max-3-Uncut problem. Applying the complex semidefinite programming rounding technique, we present a 0.3456-approximation algorithm by further integrating a greedy swapping process after the rounding step. One ingredient in our analysis different from previous work for the traditional Max-3-Cut is the introduction and analysis of a bivariate function rather than a univariate function.
In this paper we study semidefiniteprogramming (SDP) models for a class of discrete and continuous quadratic optimization problems in the complex Hermitian form. These problems capture a class of well-known combinato...
详细信息
In this paper we study semidefiniteprogramming (SDP) models for a class of discrete and continuous quadratic optimization problems in the complex Hermitian form. These problems capture a class of well-known combinatorial optimization problems, as well as problems in control theory. For instance, they include the MAX-3-CUT problem where the Laplacian matrix is positive semidefinite ( in particular, some of the edge weights can be negative). We present a generic algorithm and a unified analysis of the SDP relaxations which allow us to obtain good approximation guarantees for our models. Specifically, we give an (k sin(pi/k))(2)/(4 pi)-approximation algorithm for the discrete problem where the decision variables are k-ary and the objective matrix is positive semidefinite. To the best of our knowledge, this is the first known approximation result for this family of problems. For the continuous problem where the objective matrix is positive semidefinite, we obtain the well-known pi/4 result due to Ben-Tal et al. Math Oper Res 28( 3): 497 - 523, 2003], and independently, Zhang and Huang [SIAM J Optim 16( 3): 871 - 890, 2006]. However, our techniques simplify their analyses and provide a unified framework for treating those problems. In addition, we show for the first time that the gap between the optimal value of the original problem and that of the SDP relaxation can be arbitrarily close to pi/4. We also show that the unified analysis can be used to obtain an Omega(1/log n)approximation algorithm for the continuous problem in which the objective matrix is not positive semidefinite.
In this paper we study semidefiniteprogramming (SDP) models for a class of discrete and continuous quadratic optimization problems in the complex Hermitian form. These problems capture a class of well-known combinato...
详细信息
In this paper we study semidefiniteprogramming (SDP) models for a class of discrete and continuous quadratic optimization problems in the complex Hermitian form. These problems capture a class of well-known combinatorial optimization problems, as well as problems in control theory. For instance, they include the MAX-3-CUT problem where the Laplacian matrix is positive semidefinite ( in particular, some of the edge weights can be negative). We present a generic algorithm and a unified analysis of the SDP relaxations which allow us to obtain good approximation guarantees for our models. Specifically, we give an (k sin(pi/k))(2)/(4 pi)-approximation algorithm for the discrete problem where the decision variables are k-ary and the objective matrix is positive semidefinite. To the best of our knowledge, this is the first known approximation result for this family of problems. For the continuous problem where the objective matrix is positive semidefinite, we obtain the well-known pi/4 result due to Ben-Tal et al. Math Oper Res 28( 3): 497 - 523, 2003], and independently, Zhang and Huang [SIAM J Optim 16( 3): 871 - 890, 2006]. However, our techniques simplify their analyses and provide a unified framework for treating those problems. In addition, we show for the first time that the gap between the optimal value of the original problem and that of the SDP relaxation can be arbitrarily close to pi/4. We also show that the unified analysis can be used to obtain an Omega(1/log n)approximation algorithm for the continuous problem in which the objective matrix is not positive semidefinite.
We consider the complex cut polytope: the convex hull of Hermitian rank 1 matrices xx(H), where the elements of x is an element of C-n aremth unit roots. These polytopes have appli-cations in MAX-3-CUT, digital commun...
详细信息
We consider the complex cut polytope: the convex hull of Hermitian rank 1 matrices xx(H), where the elements of x is an element of C-n aremth unit roots. These polytopes have appli-cations in MAX-3-CUT, digital communication technology, angular synchronizationand more generally, complex quadratic programming. Form=2, the complex cutpolytope corresponds to the well-known cut polytope. We generalize valid cuts for this polytope to cuts for any complex cut poly tope with finitem>2 and provide a frame work to compare them. Further, we consider a second semi definite lifting of thecomplex cut polytope for m=infinity. This lifting is proven to be equivalent to other complex Lasserre-type liftings of the same order proposed in the literature, while beingof smaller size. Our theoretical findings are supported by numerical experiments onvarious optimization problems.
We consider the max hypergraph 3-cut problem with limited unbalance (MH3C-LU). The objective is to divide the vertex set of an edge-weighted hypergraph H = (V, E, w) into three disjoint subsets V-1, V-2, and V-3 such ...
详细信息
We consider the max hypergraph 3-cut problem with limited unbalance (MH3C-LU). The objective is to divide the vertex set of an edge-weighted hypergraph H = (V, E, w) into three disjoint subsets V-1, V-2, and V-3 such that the sum of edge weights cross different parts is maximized subject to parallel to V-i vertical bar - vertical bar V-l parallel to <= B (for all i not equal l not equal l is an element of{1, 2, 3}) fora given parameter B. This problem is NP-hard because it includes some well-known problems like the max 3-section problem and the max 3-cut problem as special cases. We formulate the MH3C-LU as a ternary quadratic program and present a randomized approximation algorithm based on the complex semidefinite programming relaxation technique.
We propose a new method for improving the bound tightness of the popular semidefiniteprogramming (SDP) relaxation for the ACOPF introduced in Lavaei and Low (2012), Molzahn and Hiskens (2019). First, we reformulate t...
详细信息
We propose a new method for improving the bound tightness of the popular semidefiniteprogramming (SDP) relaxation for the ACOPF introduced in Lavaei and Low (2012), Molzahn and Hiskens (2019). First, we reformulate the ACOPF Lagrangian dual as an unconstrained concave maximization problem with a clique decomposition induced sparse structure. We prove that this new formulation has the same optimal value as the SDP relaxation. We then use the solution of the SDP relaxation as a starting point for a tailored structureaware bundle method. This post-processing technique significantly improves the tightness of the SDP bounds computed by the state-of-the-art solver MOSEK, as shown by our computational experiments on large-scale instances from PGLib-OPF v21.07. For ten of the tested instances, our post-processing decreases by more than 50% the optimality gap obtained with MOSEK.
暂无评论