-
作者：Avella, Pasquale; Sassano, Antonio; Vasil'ev, Igor
作者单位：University of Sannio; Sapienza University Rome; University of Salerno; Irkutsk Science Centre of the Russian Academy of Sciences; Russian Academy of Sciences; Matrosov Institute for System Dynamics & Control Theory SB RAS
摘要：Given a directed graph G(V,A), the p-Median problem consists of determining p nodes (the median nodes) minimizing the total distance from the other nodes of the graph. We present a Branch-and-Cut-and-Price algorithm yielding provably good solutions for instances with vertical bar V vertical bar <= 3795. Key ingredients of the algorithm are a delayed column-and-row generation technique, exploiting the special structure of the formulation, to solve the LP-relaxation, and cutting planes to streng...
-
作者：Pap, Gyula
作者单位：Eotvos Lorand University
摘要：Even factors and square-free 2-factors are restricted matching problems for which it seems to be difficult to generalize Edmonds' matching algorithm directly. Here, we present a slight modification of Edmonds' algorithm, which adapts to these restricted matching problems. Thus, we construct algorithms for these problems which do not use alternating forests.
-
作者：Grigoriev, Alexander; Sviridenko, Maxim; Uetz, Marc
作者单位：Maastricht University; International Business Machines (IBM); IBM USA
摘要：We consider machine scheduling on unrelated parallel machines with the objective to minimize the schedule makespan. We assume that, in addition to its machine dependence, the processing time of any job is dependent on the usage of a discrete renewable resource, e.g. workers. A given amount of that resource can be distributed over the jobs in process at any time, and the more of that resource is allocated to a job, the smaller is its processing time. This model generalizes the classical unrelat...
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：Laurent, Monique
摘要：We consider the problem of minimizing a polynomial over a set defined by polynomial equations and inequalities. When the polynomial equations have a finite set of complex solutions, we can reformulate this problem as a semidefinite programming problem. Our semidefinite representation involves combinatorial moment matrices, which are matrices indexed by a basis of the quotient vector space R[x(1), . . . ,x(n) ]/I, where I is the ideal generated by the polynomial equations in the problem. Moreov...
