-
作者：Custic, Ante; Sokol, Vladyslav; Punnen, Abraham P.; Bhattacharya, Binay
作者单位：Simon Fraser University; Simon Fraser University
摘要：In this paper we study the bilinear assignment problem (BAP) with size parameters m and n, . BAP is a generalization of the well known quadratic assignment problem and the three dimensional assignment problem and hence NP-hard. We show that BAP cannot be approximated within a constant factor unless P = NP even if the associated quadratic cost matrix Q is diagonal. Further, we show that BAP remains NP-hard if , for some fixed r, but is solvable in polynomial time if . When the rank of Q is fixe...
-
作者：Imbach, Remi; Mathis, Pascal; Schreck, Pascal
作者单位：Universite de Lorraine; Universites de Strasbourg Etablissements Associes; Universite de Strasbourg; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Engineering & Systems Sciences (INSIS)
摘要：The goal of Point Distance Solving Problems is to find 2D or 3D placements of points knowing distances between some pairs of points. The common guideline is to solve them by a numerical iterative method (e.g. Newton-Raphson method). A sole solution is obtained whereas many exist. However the number of solutions can be exponential and methods should provide solutions close to a sketch drawn by the user. Geometric reasoning can help to simplify the underlying system of equations by changing a fe...
-
作者：Boland, Natashia; Dey, Santanu S.; Kalinowski, Thomas; Molinaro, Marco; Rigterink, Fabian
作者单位：University System of Georgia; Georgia Institute of Technology; University of Newcastle; Pontificia Universidade Catolica do Rio de Janeiro
摘要：We investigate how well the graph of a bilinear function can be approximated by its McCormick relaxation. In particular, we are interested in the smallest number c such that the difference between the concave upper bounding and convex lower bounding functions obtained from the McCormick relaxation approach is at most c times the difference between the concave and convex envelopes. Answering a question of Luedtke, Namazifar and Linderoth, we show that this factor c cannot be bounded by a consta...
-
作者：Curtis, Frank E.; Robinson, Daniel P.; Samadi, Mohammadreza
作者单位：Lehigh University; Johns Hopkins University
摘要：We propose a trust region algorithm for solving nonconvex smooth optimization problems. For any , the algorithm requires at most iterations, function evaluations, and derivative evaluations to drive the norm of the gradient of the objective function below any . This improves upon the bound known to hold for some other trust region algorithms and matches the bound for the recently proposed Adaptive Regularisation framework using Cubics, also known as the arc algorithm. Our algorithm, entitled t...
-
作者：Sikora, Jamie; Varvitsiotis, Antonios
作者单位：National University of Singapore; Nanyang Technological University; Nanyang Technological University
摘要：In this work we study the sets of two-party correlations generated from a Bell scenario involving two spatially separated systems with respect to various physical models. We show that the sets of classical, quantum, no-signaling and unrestricted correlations can be expressed as projections of affine sections of appropriate convex cones. As a by-product, we identify a spectrahedral outer approximation to the set of quantum correlations which is contained in the first level of the Navascu,s, Pir...
-
作者：Ye, Jane J.; Zhou, Jinchuan
作者单位：University of Victoria; Shandong University of Technology
摘要：The proximal, regular and limiting normal cones to the second-order cone complementarity set play important roles in studying mathematical programs with second-order cone complementarity constraints, second-order cone programs, and the second-order cone complementarity problems. It is needed in the first-order optimality conditions for mathematical programs with second-order cone complementarity constraint, the second-order subdifferential criteria in characterizing the full stability for seco...
-
作者：Kurpisz, Adam; Leppanen, Samuli; Mastrolilli, Monaldo
作者单位：Universita della Svizzera Italiana
摘要：In this paper we study the complexity of the Min-sum single machine scheduling problem under algorithms from the Sum-of-Squares/Lasserre hierarchy. We prove the first lower bound for this model by showing that the integrality gap is unbounded at level even for a variant of the problem that is solvable in time by the Moore-Hodgson algorithm, namely Min-number of late jobs. We consider a natural formulation that incorporates the objective function as a constraint and prove the result by partiall...
-
作者：Sziklai, Balazs; Fleiner, Tamas; Solymosi, Tamas
作者单位：HUN-REN; HUN-REN Centre for Economic & Regional Studies; Hungarian Academy of Sciences; Corvinus University Budapest; Budapest University of Technology & Economics; Hungarian Academy of Sciences
摘要：We introduce directed acyclic graph (DAG) games, a generalization of standard tree games, to study cost sharing on networks. This structure has not been previously analyzed from a cooperative game theoretic perspective. Every monotonic and subadditive cost game-including monotonic minimum cost spanning tree games-can be modeled as a DAG-game. We provide an efficiently verifiable condition satisfied by a large class of directed acyclic graphs that is sufficient for the balancedness of the assoc...
-
作者：Bernath, Attila; Pap, Gyula
作者单位：Eotvos Lorand University
摘要：The problem of covering minimum cost common bases of two matroids is NP-complete, even if the two matroids coincide, and the costs are all equal to 1. In this paper we show that the following special case is solvable in polynomial time: given a digraph with a designated root node and arc-costs , find a minimum cardinality subset H of the arc set A such that H intersects every minimum c-cost r-arborescence. By an r-arborescence we mean a spanning arborescence of root r. The algorithm we give so...
-
作者：Le Bodic, Pierre; Nemhauser, George
作者单位：Monash University; University System of Georgia; Georgia Institute of Technology
摘要：The selection of branching variables is a key component of branch-and-bound algorithms for solving mixed-integer programming (MIP) problems since the quality of the selection procedure is likely to have a significant effect on the size of the enumeration tree. State-of-the-art procedures base the selection of variables on their LP gains, which is the dual bound improvement obtained after branching on a variable. There are various ways of selecting variables depending on their LP gains. However...
