Zobrazeno 1 - 10
of 28
pro vyhledávání: '"Stefan Weltge"'
Publikováno v:
Mathematical programming. Springer
The Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that assigns integer values to some varia
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c1da7341d3e2b6ecd1ff548e1b687ace
https://doi.org/10.1007/s10107-020-01600-3
https://doi.org/10.1007/s10107-020-01600-3
Publikováno v:
Integer Programming and Combinatorial Optimization ISBN: 9783031069000
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4fcea5e25807e0d90e55ead90b3763b8
https://doi.org/10.1007/978-3-031-06901-7_28
https://doi.org/10.1007/978-3-031-06901-7_28
Publikováno v:
Integer Programming and Combinatorial Optimization ISBN: 9783031069000
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::261be4d94423b29800f32e586e0e6449
https://doi.org/10.1007/978-3-031-06901-7_12
https://doi.org/10.1007/978-3-031-06901-7_12
We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::dad6631bbdb9a8ddfbb9554b8a81f0d3
http://arxiv.org/abs/2106.05947
http://arxiv.org/abs/2106.05947
Autor:
Andrey Kupavskii, Stefan Weltge
Let $A,B \subseteq \mathbb{R}^d $ both span $\mathbb{R}^d$ such that $\langle a, b \rangle \in \{0,1\}$ holds for all $a \in A$, $b \in B$. We show that $ |A| \cdot |B| \le (d+1) 2^d $. This allows us to settle a conjecture by Bohn, Faenza, Fiorini,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f2432fccb566ea4e449e5d802b6411d0
Publikováno v:
Integer Programming and Combinatorial Optimization ISBN: 9783030457709
IPCO
IPCO
Let G be an n-node graph without two disjoint odd cycles. The algorithm of Artmann, Weismantel and Zenklusen (STOC’17) for bimodular integer programs can be used to find a maximum weight stable set in G in strongly polynomial time. Building on stru
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2a5adb6784a9f2587f5ba3c05af0fba1
https://doi.org/10.1007/978-3-030-45771-6_9
https://doi.org/10.1007/978-3-030-45771-6_9
Publikováno v:
Mathematical Programming. 179:455-468
A classic result of Cook et al. (Math. Program. 34:251–264, 1986) bounds the distances between optimal solutions of mixed-integer linear programs and optimal solutions of the corresponding linear relaxations. Their bound is given in terms of the nu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7feb517e2d516542fd02e52e8403485b
https://doi.org/10.1007/s10107-018-1323-z
https://doi.org/10.1007/s10107-018-1323-z
Publikováno v:
Mathematics of Operations Research. 43:718-725
Let S ⊆ {0, 1}n and R be any polytope contained in [0, 1]n with R ∩ {0, 1}n = S. We prove that R has bounded Chvátal-Gomory rank (CG-rank) provided that S has bounded notch and bounded gap, where the notch is the minimum integer p such that all
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::30cfc3ea6ba9f043fd6b74a3aef37a09
https://doi.org/10.1287/moor.2017.0880
https://doi.org/10.1287/moor.2017.0880
Publikováno v:
Graphs and Combinatorics. 36:177-179
We report a logical error in our article that turns out to be fatal for the main result. The error lies in Lemma 3 for the case of a 3-sum, that is
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7051893b369c9a3e8bd395d0b3350642
https://doi.org/10.1007/s00373-019-02122-2
https://doi.org/10.1007/s00373-019-02122-2
Autor:
Stefan Weltge, Stefan Kober
Kurz and Napel (Optim Lett 10(6):1245–1256, 2015, 10.1007/s11590-015-0917-0) proved that the voting system of the EU council (based on the 2014 population data) cannot be represented as the intersection of six weighted games, i.e., its dimension is
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3b870e5ab05869ec20c8ca993093e8cd
https://mediatum.ub.tum.de/doc/1586271/document.pdf
https://mediatum.ub.tum.de/doc/1586271/document.pdf