-
作者：Freund, Robert M.; Ordonez, Fernando; Toh, Kim-Chuan
作者单位：University of Southern California; Massachusetts Institute of Technology (MIT); National University of Singapore; Singapore-MIT Alliance for Research & Technology Centre (SMART); Massachusetts Institute of Technology (MIT); Nanyang Technological University
摘要：We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the (Renegar-) condition measure C(d) of the data instance, (iii) a measure of the near-absence of strict complementarity of the o...
-
作者：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.
-
作者：So, Anthony Man-Cho; Ye, Yinyu
作者单位：Stanford University; Stanford University
摘要：We analyze the semidefinite programming (SDP) based model and method for the position estimation problem in sensor network localization and other Euclidean distance geometry applications. We use SDP duality and interior-point algorithm theories to prove that the SDP localizes any network or graph that has unique sensor positions to fit given distance measures. Therefore, we show, for the first time, that these networks can be localized in polynomial time. We also give a simple and efficient cr...
-
作者：Krokhmal, Pavlo A.; Grundel, Don A.; Pardalos, Panos M.
作者单位：University of Iowa; United States Department of Defense; United States Air Force; State University System of Florida; University of Florida
摘要：The Multidimensional Assignment Problem (MAP) is a higher-dimensional version of the Linear Assignment Problem that arises in the areas of data association, target tracking, resource allocation, etc. This paper elucidates the question of asymptotical behavior of the expected optimal value of the large-scale MAP whose assignment costs are independent identically distributed random variables with a prescribed probability distribution. We demonstrate that for a broad class of continuous distribut...
-
作者：Kocvara, Michal; Stingl, Michael
作者单位：Czech Academy of Sciences; Institute of Information Theory & Automation of the Czech Academy of Sciences; Czech Technical University Prague; University of Erlangen Nuremberg
摘要：The limiting factors of second-order methods for large-scale semidefinite optimization are the storage and factorization of the Newton matrix. For a particular algorithm based on the modified barrier method, we propose to use iterative solvers instead of the routinely used direct factorization techniques. The preconditioned conjugate gradient method proves to be a viable alternative for problems with a large number of variables and modest size of the constrained matrix. We further propose to a...
-
作者：Dukanovic, Igor; Rendl, Franz
作者单位：University of Klagenfurt; University of Maribor
摘要：The semidefinite programming formulation of the Lovasz theta number does not only give one of the best polynomial simultaneous bounds on the chromatic number chi(G) or the clique number omega(G) of a graph, but also leads to heuristics for graph coloring and extracting large cliques. This semidefinite programming formulation can be tightened toward either chi(G) or omega(G) by adding several types of cutting planes. We explore several such strengthenings, and show that some of them can be comp...
-
作者：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...
