-
作者：Hajiaghayi, Mohammad T.; Kortsarz, Guy; Mirrokni, Vahab S.; Nutov, Zeev
作者单位：Massachusetts Institute of Technology (MIT); Rutgers University System; Rutgers University New Brunswick; Rutgers University Camden; Microsoft; Open University Israel
摘要：Given a graph with costs on the edges, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of the nodes of this graph. Motivated by applications in wireless multihop networks, we consider four fundamental problems under the power minimization criteria: the Min-Power b-Edge-Cover problem (MPb-EC) where the goal is to find amin-power subgraph so that the degree of every node v is at least some given integer b(v), the Min-Power k-node...
-
作者：Gabow, Harold N.
作者单位：University of Colorado System; University of Colorado Boulder
摘要：We discuss extensions of Jain's framework for network design [8] that go beyond undirected graphs. The main problem is approximating a minimum cost set of directed edges that covers a crossing supermodular function. We show that iterated rounding gives a factor 3 approximation, where factor 4 was previously known and factor 2 was conjectured. Our bound is tight for the simplest interpretation of iterated rounding. We also show that (the simplest version of) iterated rounding has unbounded appr...
-
作者：Jeyakumar, V.; Rubinov, A. M.; Wu, Z. Y.
作者单位：University of New South Wales Sydney; Federation University Australia; Chongqing Normal University
摘要：In this paper, we first examine how global optimality of non-convex constrained optimization problems is related to Lagrange multiplier conditions. We then establish Lagrange multiplier conditions for global optimality of general quadratic minimization problems with quadratic constraints. We also obtain necessary global optimality conditions, which are different from the Lagrange multiplier conditions for special classes of quadratic optimization problems. These classes include weighted least ...
-
作者：Ng, Kung Fu; Tan, Lu Lin
作者单位：Chinese University of Hong Kong
摘要：We study the Clarke-Rockafellar directional derivatives of the regularized gap functions (and of some modified ones) for the variational inequality problem (VIP) defined by a locally Lipschitz but not necessarily differentiable function on a closed convex set in an Euclidean space. As applications we show that, under the strong monotonicity assumption, the regularized gap functions have fractional exponent error bounds and consequently that the sequences provided by an algorithm of Armijo type...
-
作者：Gvozdenovic, Nebojsa; Laurent, Monique
作者单位：Centrum Wiskunde & Informatica (CWI)
摘要：Lovasz and Schrijver (SIAM J. Optim. 1:166-190, 1991) have constructed semidefinite relaxations for the stable set polytope of a graph G = (V,E) by a sequence of lift-and-project operations; their procedure finds the stable set polytope in at most alpha(G) steps, where alpha(G) is the stability number of G. Two other hierarchies of semidefinite bounds for the stability number have been proposed by Lasserre (SIAM J. Optim. 11:796-817, 2001; Lecture Notes in Computer Science, Springer, Berlin He...
-
作者：Haarala, Napsu; Miettinen, Kaisa; Makela, Marko M.
作者单位：University of Witwatersrand; Aalto University; University of Jyvaskyla
摘要：Many practical optimization problems involve nonsmooth (that is, not necessarily differentiable) functions of thousands of variables. In the paper [Haarala, Miettinen, Makela, Optimization Methods and Software, 19, (2004), pp. 673-692] we have described an efficient method for large-scale nonsmooth optimization. In this paper, we introduce a new variant of this method and prove its global convergence for locally Lipschitz continuous objective functions, which are not necessarily differentiable...
-
作者：Grosso, Andrea; Locatelli, Marco; Schoen, Fabio
作者单位：University of Florence; University of Turin
摘要：When dealing with extremely hard global optimization problems, i.e. problems with a large number of variables and a huge number of local optima, heuristic procedures are the only possible choice. In this situation, lacking any possibility of guaranteeing global optimality for most problem instances, it is quite difficult to establish rules for discriminating among different algorithms. We think that in order to judge the quality of new global optimization methods, different criteria might be a...
-
作者：Rendl, Franz; Sotirov, Renata
作者单位：University of Klagenfurt; University of Melbourne
摘要：Semidefinite programming (SDP) has recently turned out to be a very powerful tool for approximating some NP-hard problems. The nature of the quadratic assignment problem (QAP) suggests SDP as a way to derive tractable relaxations. We recall some SDP relaxations of QAP and solve them approximately using a dynamic version of the bundle method. The computational results demonstrate the efficiency of the approach. Our bounds are currently among the strongest ones available for QAP. We investigate ...
-
作者：Munson, Todd
作者单位：United States Department of Energy (DOE); Argonne National Laboratory
摘要：Meshes containing elements with bad quality can result in poorly conditioned systems of equations that must be solved when using a discretization method, such as the finite-element method, for solving a partial differential equation. Moreover, such meshes can lead to poor accuracy in the approximate solution computed. In this paper, we present a nonlinear fractional program that relocates the vertex coordinates of a given mesh to optimize the average element shape quality as measured by the in...
-
作者：So, Anthony Man-Cho; Zhang, Jiawei; Ye, Yinyu
作者单位：Stanford University; New York University; Stanford University
摘要：In this paper we study semidefinite programming (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...
