Ballad
发表于 2025-3-28 15:43:42
Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)/2-approximation for this problem. It is also known, via a reduction from the max-.-cover problem, that there is no (1 − 1/. + .)-approximation for any constant .> 0, unless . = . . In this paper, we improve the 1/2-approximation to a (1 − 1/.)-approximation, when . is a sum of weighted rank
Crohns-disease
发表于 2025-3-28 20:13:01
On a Generalization of the Master Cyclic Group Polyhedronxplicit characterization of the nontrivial facet-defining inequalities for MEP. This result generalizes similar results for the Master Cyclic Group Polyhedron by Gomory and for the Master Knapsack Polyhedron by Araoz . Furthermore, this characterization also gives a polynomial time algorithm
分离
发表于 2025-3-28 23:32:03
http://reply.papertrans.cn/47/4683/468248/468248_43.png
半圆凿
发表于 2025-3-29 05:23:48
On the Exact Separation of Mixed Integer Knapsack Cuts However, no such class has had as much practical success as the MIR inequality when used in cutting plane algorithms for general mixed integer programming problems. In this work we analyze this empirical observation by developing an algorithm which takes as input a point and a single-row mixed inte
游行
发表于 2025-3-29 07:34:44
http://reply.papertrans.cn/47/4683/468248/468248_45.png
掺和
发表于 2025-3-29 13:46:01
Matching Problems in Polymatroids Without Double Circuitsl, then a partition-type min-max formula characterizes the size of a maximum matching. We provide applications of this result to parity constrained orientations and to a rigidity problem..A polynomial time algorithm is constructed by generalizing the principle of shrinking blossoms used in Edmonds’ matching algorithm .
acrobat
发表于 2025-3-29 17:02:29
A Framework to Derive Multidimensional Superadditive Lifting Functions and Its Applicationsroblem can be expressed or approximated through the single-dimensional lifting function of some of its components. We then apply our approach to two variants of classical models and show that it yields an efficient procedure to derive strong valid inequalities.
euphoria
发表于 2025-3-29 21:57:44
Orbital Branchingt suite of symmetric integer programs, the question as to the most effective orbit on which to base the branching decision is investigated. The resulting method is shown to be quite competitive with a similar method known as . and significantly better than a state-of-the-art commercial solver on symmetric integer programs.
中世纪
发表于 2025-3-30 02:07:34
http://reply.papertrans.cn/47/4683/468248/468248_49.png
消瘦
发表于 2025-3-30 07:10:08
On the Exact Separation of Mixed Integer Knapsack Cutsntire closure of single-row systems allows us to establish natural benchmarks by which to evaluate specific classes of knapsack cuts. Using these benchmarks on Miplib 3.0 instances we analyze the performance of MIR inequalities. Computations are performed in exact arithmetic.