Titlebook: Integer Programming and Combinatorial Optimization; 14th International C Friedrich Eisenbrand,F. Bruce Shepherd Conference proceedings 2010

奇思怪想

intercede

Eigenvalue Techniques for Convex Objective, Nonconvex Optimization Problems, that even if we can efficiently optimize over the convex hull of the feasible region, the optimum will likely lie in the interior of a high dimensional face, “far away” from any feasible point, yielding weak bounds. We present theory and implementation for an approach that relies on (a) the S-lemma

极深

Restricted ,-Matchings in Degree-Bounded Graphs,ch the degree of each node is at most . + 1, find a maximum .-matching containing no member of a list . of forbidden .. and .. subgraphs. An analogous problem for bipartite graphs without degree bounds was solved by Makai [15], while the special case of finding a maximum square-free 2-matching in a

冲击力

Zero-Coefficient Cuts,here . ≥ 0 is the vector of non-basic variables and . ≥ 0. For a point . of the linear relaxation, we call ... ≥ 1 a . wrt. . if ., since this implies .. = 0 when .. We consider the following problem: Given a point . of the linear relaxation, find a basis, and a zero-coefficient cut wrt. . derived f

Pessary

Prize-Collecting Steiner Network Problems,bgraph . of . that contains .. edge-disjoint paths for all .,. ∈ .. In . problems we do not need to satisfy all requirements, but are given a . for violating the connectivity requirements, and the goal is to find a subgraph . that minimizes the cost plus the penalty. The case when .. ∈ {0,1} is the

得罪人

drusen

atopic

sacrum

可互换

Symmetry Matters for the Sizes of Extended Formulations, variables and constraints that is bounded subexponentially in .. Here, symmetric means that the formulation remains invariant under all permutations of the nodes of ... It was also conjectured in [17] that “asymmetry does not help much,” but no corresponding result for general extended formulations