We introduce a method for proving Sum-of-Squares (SoS)/Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study ...
详细信息
ISBN:
(纸本)9783319334615;9783319334608
We introduce a method for proving Sum-of-Squares (SoS)/Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study of the positive semidefiniteness to the analysis of "well-behaved" univariate polynomial inequalities. We illustrate the technique on two problems, one unconstrained and the other with constraints. More precisely, we give a short elementary proof of Grigoriev/Laurent lower bound for finding the integer cut polytope of the complete graph. We also show that the SoS hierarchy requires a non-constant number of rounds to improve the initial integrality gap of 2 for the Min-Knapsack linear program strengthened with cover inequalities.
In 1971, Balas introduced intersection cuts as a method for generating cutting planes in integeroptimization. these cuts are derived from convex S-free sets, and inclusion-wise maximal S-free sets yield the strongest...
详细信息
ISBN:
(纸本)9783031327254;9783031327261
In 1971, Balas introduced intersection cuts as a method for generating cutting planes in integeroptimization. these cuts are derived from convex S-free sets, and inclusion-wise maximal S-free sets yield the strongest intersection cuts. When S is a lattice, maximal S-free sets are well-studied. In this work, we provide a new characterization of maximal S-free sets, for arbitrary S, based on sequences that 'expose' inequalities defining the S-free set;these exposing sequences generalize the notion of blocking points when S is a lattice. We then apply our characterization to partially characterize maximal S-free polyhedra when S is defined by a homogeneous quadratic inequality. Our results generate new families of maximal quadratic-free sets and considerably generalize some of the constructions by Munoz and Serrano (ipco 2020), who first introduced maximal quadratic-free sets.
We derive the first performance guarantees for a combinatorial online algorithm that schedules stochastic, nonpreemptive jobs on unrelated machines to minimize the expectation of the total weighted completion time. Pr...
详细信息
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592503;9783319592497
We derive the first performance guarantees for a combinatorial online algorithm that schedules stochastic, nonpreemptive jobs on unrelated machines to minimize the expectation of the total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case, and required sophisticated linear or convex programming relaxations for the assignment of jobs to machines. Our algorithm is purely combinatorial, and therefore it also works for the online setting. As to the techniques applied, this paper shows how the dual fitting technique can be put to work for stochastic and nonpreemptive scheduling problems.
We consider a robust formulation, introduced by Krause et al. (2008), of the classic cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results....
详细信息
ISBN:
(纸本)9783319334615;9783319334608
We consider a robust formulation, introduced by Krause et al. (2008), of the classic cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results. the robustness considered is w.r.t. adversarial removal of a given number of elements from the chosen set. In particular, for the fundamental case of single element removal, we show that one can approximate the problem up to a factor (1 - 1/e) - epsilon by making O(n(1/epsilon)) queries, for arbitrary epsilon > 0. the ideas are also extended to more general settings.
We provide an efficient algorithm for computing the nucleolus for an instance of a weighted cooperative matching game. this resolves a long-standing open question posed in [Faigle, Kern, Fekete, Hochstattler, Mathemat...
详细信息
ISBN:
(纸本)9783030179533;9783030179526
We provide an efficient algorithm for computing the nucleolus for an instance of a weighted cooperative matching game. this resolves a long-standing open question posed in [Faigle, Kern, Fekete, Hochstattler, Mathematical programming, 1998].
In this paper we consider a variant of the betweenness problem occurring in computational biology. We present a new polyhedral approach which incorporates the solution of consecutive ones problems and show that it sup...
详细信息
ISBN:
(纸本)354064590X
In this paper we consider a variant of the betweenness problem occurring in computational biology. We present a new polyhedral approach which incorporates the solution of consecutive ones problems and show that it supersedes an earlier one. A particular feature of this new branch-and-cut algorithm is that it is not based on an explicit integerprogramming formulation of the problem and makes use of automatically generated facet-defining inequalities.
We investigate the semigroup of integer points inside a convex cone. We extend classical results in integer linear programming to integer conic programming. We show that the semigroup associated with nonpolyhedral con...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
We investigate the semigroup of integer points inside a convex cone. We extend classical results in integer linear programming to integer conic programming. We show that the semigroup associated with nonpolyhedral cones can sometimes have a notion of finite generating set. We show this is true for the cone of positive semidefinite matrices (PSD) and the second-order cone (SOC). Both cones have a finite generating set of integer points, similar in spirit to Hilbert bases, under the action of a finitely generated group. We also extend notions of total dual integrality, Gomory-Chv ' atal closure, and Carath ' eodory rank to integer points in arbitrary cones.
We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integerprogramming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and n item...
详细信息
ISBN:
(纸本)9783031327254;9783031327261
We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integerprogramming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and n items. the objective is to select some items to pack into the first knapsack such that the maximum profit attainable from packing some of the remaining items into the second knapsack is minimized. We present a combinatorial branch-and-bound algorithm which outperforms the current state-of-the-art solution method in computational experiments by 4.5 times on average for all instances reported in the literature. On many of the harder instances, our algorithm is hundreds of times faster, and we solved 53 of the 72 previously unsolved instances. Our result relies fundamentally on a new dynamic programming algorithm which computes very strong lower bounds. this dynamic program solves a relaxation of the problem from bilevel to 2n-level where the items are processed in an online fashion. the relaxation is easier to solve but approximates the original problem surprisingly well in practice. We believe that this same technique may be useful for other interdiction problems.
A clutter is identically self-blocking if it is equal to its blocker. We prove that every identically self-blocking clutter different from {{a}} is nonideal. Our proofs borrow tools from Gauge Duality and Quadratic Pr...
详细信息
ISBN:
(数字)9783030179533
ISBN:
(纸本)9783030179533;9783030179526
A clutter is identically self-blocking if it is equal to its blocker. We prove that every identically self-blocking clutter different from {{a}} is nonideal. Our proofs borrow tools from Gauge Duality and Quadratic programming. Along the way we provide a new lower bound for the packing number of an arbitrary clutter.
We generalize the reduction mechanism between linear programming problems from [1] in two ways (1) relaxing the requirement of affineness, and (2) extending to fractional optimization problems. As applications we prov...
详细信息
ISBN:
(纸本)9783319334615;9783319334608
We generalize the reduction mechanism between linear programming problems from [1] in two ways (1) relaxing the requirement of affineness, and (2) extending to fractional optimization problems. As applications we provide several new LP-hardness and SDP-hardness results, e.g., for the SparsestCut problem, the BalancedSeparator problem, the MaxCut problem and the Matching problem on 3-regular graphs. We also provide a new, very strong Lasserre integrality gap for the IndependentSet problem, which is strictly greater than the best known LP approximation, showing that the Lasserre hierarchy does not always provide the tightest SDP relaxation.
暂无评论