-
作者：Lu, Zhaosong; Nemirovski, Arkadi; Monteiro, Renato D. C.
作者单位：Simon Fraser University; University System of Georgia; Georgia Institute of Technology
摘要：In this paper, we first demonstrate that positive semidefiniteness of a large well-structured sparse symmetric matrix can be represented via positive semidefiniteness of a bunch of smaller matrices linked, in a linear fashion, to the matrix. We derive also the dual counterpart of the outlined representation, which expresses the possibility of positive semidefinite completion of a well-structured partially defined symmetric matrix in terms of positive semidefiniteness of a specific bunch of ful...
-
作者：Karakostas, George; Viglas, Anastasios
作者单位：University of Sydney; McMaster University
摘要：We consider the problem of characterizing user equilibria and optimal solutions for selfish routing in a given network. We extend the known models by considering malicious behavior. While selfish users follow a strategy that minimizes their individual cost, a malicious user will use his flow through the network in an effort to cause the maximum possible damage to the overall cost. We define a generalized model, present characterizations of flows at equilibrium and prove bounds for the ratio of...
-
作者：Nemirovski, Arkadi
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Let B-i be deterministic real symmetric m x m matrices, and xi (i) be independent random scalars with zero mean and of order of one (e.g., xi(i) similar to N(o,1)). We are interested to know under what conditions typical norm of the random matrix S-N = Sigma(N)(i=1) xi B-i(i) is of order of 1. An evident necessary condition is E{S-N(2)} less than or similar to O(1)I, which, essentially, translates to Sigma(N)(i=1) B-i(2) less than or similar to I; a natural conjecture is that the latter condit...
-
作者：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...
-
作者：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...
