-
作者：Braun, Gabor; Brown-Cohen, Jonah; Huq, Arefin; Pokutta, Sebastian; Raghavendra, Prasad; Roy, Aurko; Weitz, Benjamin; Zink, Daniel
作者单位：University System of Georgia; Georgia Institute of Technology; University of California System; University of California Berkeley
摘要：Yannakakis (Proceedings of the STOC, pp 223-228, 1988; J Comput Syst Sci 43(3):441-466, 1991. doi:10.1016/0022-0000(91)90024-Y) showed that the matching problem does not have a small symmetric linear program. Rothvoss (Proceedings of the STOC, pp 263-272, 2014) recently proved that any, not necessarily symmetric, linear program also has exponential size. In light of this, it is natural to ask whether the matching problem can be expressed compactly in a framework such as semidefinite programmin...
-
作者：Chen, Chen; Atamturk, Alper; Oren, Shmuel S.
作者单位：University of California System; University of California Berkeley
摘要：We develop a spatial branch-and-cut approach for nonconvex quadratically constrained quadratic programs with bounded complex variables (CQCQP). Linear valid inequalities are added at each node of the search tree to strengthen semidefinite programming relaxations of CQCQP. These valid inequalities are derived from the convex hull description of a nonconvex set of positive semidefinite Hermitian matrices subject to a rank-one constraint. We propose branching rules based on an alternative to the ...
-
作者：Chopra, Sunil; Filipecki, Bartosz; Lee, Kangbok; Ryu, Minseok; Shim, Sangho; Van Vyve, Mathieu
作者单位：Northwestern University; Universite Catholique Louvain; Pohang University of Science & Technology (POSTECH); University of Michigan System; University of Michigan; Robert Morris University
摘要：We introduce a strong extended formulation of the convex recoloring problem on a tree, which has an application in analyzing phylogenetic trees. The extended formulation has only a polynomial number of constraints, but dominates the conventional formulation and the exponentially many valid inequalities introduced by Camplo et al. (Math Progr 156:303-330, 2016). We show that all valid inequalities introduced by Camplo et al. can be derived from the extended formulation. We also show that the na...
-
作者：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...
-
作者：Liu, Hongcheng; Yao, Tao; Li, Runze; Ye, Yinyu
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Stanford University
摘要：This paper concerns the folded concave penalized sparse linear regression (FCPSLR), a class of popular sparse recovery methods. Although FCPSLR yields desirable recovery performance when solved globally, computing a global solution is NP-complete. Despite some existing statistical performance analyses on local minimizers or on specific FCPSLR-based learning algorithms, it still remains open questions whether local solutions that are known to admit fully polynomial-time approximation schemes (F...
-
作者：Basu, Amitabh; Hildebrand, Robert; Koppe, Matthias
作者单位：Johns Hopkins University; International Business Machines (IBM); IBM USA; University of California System; University of California Davis
摘要：We develop foundational tools for classifying the extreme valid functions for the k-dimensional infinite group problem. In particular, we present the general regular solution to Cauchy's additive functional equation on restricted lower-dimensional convex domains. This provides a k-dimensional generalization of the so-called Interval Lemma, allowing us to deduce affine properties of the function from certain additivity relations. Next, we study the discrete geometry of additivity domains of pie...
-
作者：Sitters, Rene
作者单位：Vrije Universiteit Amsterdam; Centrum Wiskunde & Informatica (CWI)
摘要：We show that minimizing the average job completion time on unrelated machines is -hard if preemption of jobs is allowed. This provides one of the last missing pieces in the complexity classification of machine scheduling with (weighted) sum of completion times objective. The proof is based on a mixed integer linear program. This means that verification of the reduction is partly done by an ILP-solver. This gives a concise proof which is easy to verify. In addition, we give a deterministic 1.69...
-
作者：Le Bodic, Pierre; Nemhauser, George
作者单位：Monash University; University System of Georgia; Georgia Institute of Technology
