Copertina

Complexity of polytope diameters via perfect matchings

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Nöbel, Christian, Steiner, Raphael
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Optimization and Control Discrete Mathematics Data Structures and Algorithms Combinatorics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Separable convex optimization over indegree polytopes
di: Borsik, Nóra A., et al.
Pubblicazione: (2025)

Integer programs with nearly totally unimodular matrices: the cographic case
di: Aprile, Manuel, et al.
Pubblicazione: (2024)

Totally $Δ$-modular IPs with two non-zeros in most rows
di: Kober, Stefan
Pubblicazione: (2024)

Vertex-ordering and arc-partitioning problems
di: Borsik, Nóra A., et al.
Pubblicazione: (2025)

Max-Min and 1-Bounded Space Algorithms for the Bin Packing Problem
di: Fujiwara, Hiroshi, et al.
Pubblicazione: (2025)

Integer programs with bounded subdeterminants and two nonzeros per row
di: Fiorini, Samuel, et al.
Pubblicazione: (2021)

Prefix-bounded matrices
di: Borsik, Nóra A., et al.
Pubblicazione: (2025)

On the Congruency-Constrained Matroid Base
di: Liu, Siyue, et al.
Pubblicazione: (2023)

Total Matching and Subdeterminants
di: Ferrarini, Luca, et al.
Pubblicazione: (2023)

A Θ(m^9) ternary minimum-cost network flow LP model of the Assignment Problem polytope with applications to hard combinatorial optimization problems
di: Diaby, Moustapha
Pubblicazione: (2016)

Deterministic approximation for the volume of the truncated fractional matching polytope
di: Guo, Heng, et al.
Pubblicazione: (2024)

On the time complexity of finding a well-spread perfect matching in bridgeless cubic graphs
di: Ghanbari, Babak, et al.
Pubblicazione: (2025)

Traversing combinatorial 0/1-polytopes via optimization
di: Merino, Arturo, et al.
Pubblicazione: (2023)

Efficient approximation schemes for scheduling on a stochastic number of machines
di: Epstein, Leah, et al.
Pubblicazione: (2024)

Algorithmic aspects of semistability of quiver representations
di: Iwamasa, Yuni, et al.
Pubblicazione: (2024)

NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
di: Kar, Prem Nigam, et al.
Pubblicazione: (2024)

Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack
di: Schade, Jamico, et al.
Pubblicazione: (2023)

Parameterized complexity of isometric path partition: treewidth and diameter
di: Chakraborty, Dibyayan, et al.
Pubblicazione: (2025)

Clique-free t-matchings in degree-bounded graphs
di: Paluch, Katarzyna, et al.
Pubblicazione: (2024)

Generalized Cuts and Grothendieck Covers: a Primal-Dual Approximation Framework Extending the Goemans--Williamson Algorithm
di: Proença, Nathan Benedetto, et al.
Pubblicazione: (2024)

New Sequence-Independent Lifting Techniques for Cutting Planes and When They Induce Facets
di: Prasad, Siddharth, et al.
Pubblicazione: (2024)

Efficient Local and Tabu Search Strategies for Large-Scale Quadratic Integer Programming
di: Wang, Haibo, et al.
Pubblicazione: (2024)

Flow Shop Scheduling with Stochastic Reentry
di: von Aspern, Maximilian, et al.
Pubblicazione: (2026)

A 1/2-Approximation for Budgeted $k$-Submodular Maximization
di: Wang, Chenhao
Pubblicazione: (2025)

A Primal-Dual Extension of the Goemans--Williamson Algorithm for the Weighted Fractional Cut-Covering Problem
di: Proença, Nathan Benedetto, et al.
Pubblicazione: (2023)

ResQue Greedy: Rewiring Sequential Greedy for Improved Submodular Maximization
di: Gallart, Joan Vendrell, et al.
Pubblicazione: (2025)

Multiplicative assignment with upgrades
di: Armbruster, Alexander, et al.
Pubblicazione: (2025)

Probabilistic estimates of the diameters of the Rubik's Cube groups
di: Hirata, So
Pubblicazione: (2024)

The Central Spanning Tree Problem
di: Sanmartín, Enrique Fita, et al.
Pubblicazione: (2024)

The Complexity of Homomorphism Reconstruction Revisited
di: Gervens, Timo, et al.
Pubblicazione: (2026)

Markovian protocols and an upper bound on the extension complexity of the matching polytope
di: Szusterman, M.
Pubblicazione: (2026)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
di: Deligkas, Argyrios, et al.
Pubblicazione: (2025)

Periodic trajectories in P-time event graphs and the non-positive circuit weight problem
di: Zorzenon, Davide, et al.
Pubblicazione: (2021)

Difference of Submodular Minimization via DC Programming
di: Halabi, Marwa El, et al.
Pubblicazione: (2023)

Thin Trees via $k$-Respecting Cut Identities
di: Daga, Mohit
Pubblicazione: (2025)

Generalising the maximum independent set algorithm via Boolean networks
di: Gadouleau, Maximilien, et al.
Pubblicazione: (2024)

Dvorak-Dell-Grohe-Rattan theorem via an asymptotic argument
di: Kozachinskiy, Alexander
Pubblicazione: (2025)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
di: Korhonen, Tuukka, et al.
Pubblicazione: (2024)

Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
di: Ameli, Afrouz Jabal, et al.
Pubblicazione: (2026)

Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
di: Jeronimo, Fernando Granha, et al.
Pubblicazione: (2022)