On the public citation graph

Extended formulations for combinatorial polytopes

https://doi.org/10.25673/3850
0 signed · 86 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/net.10010openalex-snapshot
A linear‐size zero—one programming model for the minimum spanning tree problem in planar graphs
inferredcites →https://doi.org/10.1002/net.3230150206openalex-snapshot
Minimum cuts, modular functions, and matroid polyhedra
inferredcites →https://doi.org/10.1006/eujc.1999.0326openalex-snapshot
Upper Bounds on the Maximal Number of Facets of 0/1-Polytopes
inferredcites →https://doi.org/10.1007/3-540-27477-4_15openalex-snapshot
Communication Complexity
inferredcites →https://doi.org/10.1007/978-3-540-73208-2_21openalex-snapshot
Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
inferredcites →https://doi.org/10.1007/978-3-642-13036-6_11openalex-snapshot
Symmetry Matters for the Sizes of Extended Formulations
inferredcites →https://doi.org/10.1007/978-3-642-13036-6_14openalex-snapshot
Branched Polyhedral Systems
inferredcites →https://doi.org/10.1007/978-3-642-20807-2_23openalex-snapshot
Constructing Extended Formulations from Reflection Relations
inferredcites →https://doi.org/10.1007/bf01580113openalex-snapshot
Matching, Euler tours and the Chinese postman
inferredcites →https://doi.org/10.1007/bf01580600openalex-snapshot
On cuts and matchings in planar graphs
inferredcites →https://doi.org/10.1007/bf01584082openalex-snapshot
Matroids and the greedy algorithm
inferredcites →https://doi.org/10.1007/bf02579338openalex-snapshot
Sorting inc logn parallel steps
inferredcites →https://doi.org/10.1007/bf02592023openalex-snapshot
On the cut polytope
inferredcites →https://doi.org/10.1007/s00454-012-9421-9openalex-snapshot
Extended Formulations for Polygons
inferredcites →https://doi.org/10.1007/s00493-012-2746-4openalex-snapshot
A counterexample to the Alon-Saks-Seymour conjecture and related problems
inferredcites →https://doi.org/10.1007/s10107-014-0755-3openalex-snapshot
Extended formulations, nonnegative factorizations, and randomized communication protocols
inferredcites →https://doi.org/10.1007/s10479-012-1269-0openalex-snapshot
Extended formulations in combinatorial optimization
inferredcites →https://doi.org/10.1016/0012-365x(75)90003-5openalex-snapshot
On defining sets of vertices of the hypercube by linear inequalities
inferredcites →https://doi.org/10.1016/0012-365x(75)90058-8openalex-snapshot
On the ratio of optimal integral and fractional covers
inferredcites →https://doi.org/10.1016/0022-0000(91)90024-yopenalex-snapshot
Expressing combinatorial optimization problems by Linear Programs
inferredcites →https://doi.org/10.1016/0167-6377(91)90028-nopenalex-snapshot
Using separation algorithms to generate mixed integer model reformulations
inferredcites →https://doi.org/10.1016/0167-6377(91)90038-qopenalex-snapshot
Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus
inferredcites →https://doi.org/10.1016/0196-6774(89)90006-0openalex-snapshot
The graph genus problem is NP-complete
inferredcites →https://doi.org/10.1016/j.disc.2012.09.015openalex-snapshot
Combinatorial bounds on nonnegative rank and extended formulations
inferredcites →https://doi.org/10.1016/j.endm.2010.05.128openalex-snapshot
On the Convex Hull of Huffman Trees
inferredcites →https://doi.org/10.1016/j.jcss.2006.04.007openalex-snapshot
Strong computational lower bounds via parameterized complexity
inferredcites →https://doi.org/10.1016/j.laa.2012.06.038openalex-snapshot
On the geometric interpretation of the nonnegative rank
inferredcites →https://doi.org/10.1016/s0012-365x(96)00124-0openalex-snapshot
Covering a graph by complete bipartite graphs
inferredcites →https://doi.org/10.1016/s0166-218x(98)00136-xopenalex-snapshot
Disjunctive programming: Properties of the convex hull of feasible points
inferredcites →https://doi.org/10.1016/s0167-6377(03)00052-xopenalex-snapshot
A compact linear program for testing optimality of perfect matchings
inferredcites →https://doi.org/10.1016/s0196-8858(03)00093-9openalex-snapshot
Combinatorial optimization in geometry
inferredcites →https://doi.org/10.1016/s0304-0208(08)73429-7openalex-snapshot
Trees and Cuts
inferredcites →https://doi.org/10.1016/s0304-0208(08)x7063-xopenalex-snapshot
Graphs, Groups and Surfaces
inferredcites →https://doi.org/10.1016/s0304-3975(96)00062-xopenalex-snapshot
A comparison of two lower-bound methods for communication complexity
inferredcites →https://doi.org/10.1090/dimacs/001openalex-snapshot
Polyhedral Combinatorics
inferredcites →https://doi.org/10.1112/blms/23.5.505openalex-snapshot
REFLECTION GROUPS AND COXETER GROUPS (Cambridge Studies in Advanced Mathematics 29)
inferredcites →https://doi.org/10.1137/0219054openalex-snapshot
The Spatial Complexity of Oblivious k -Probe Hash Functions
inferredcites →https://doi.org/10.1137/070709967openalex-snapshot
On the Complexity of Nonnegative Matrix Factorization
inferredcites →https://doi.org/10.1137/s0097539702407345openalex-snapshot
Nondeterministic Quantum Query and Communication Complexities
inferredcites →https://doi.org/10.1137/s0895480192238482openalex-snapshot
Fractional Covers and Communication Complexity
inferredcites →https://doi.org/10.1137/s089548019630978xopenalex-snapshot
Bounded Stable Sets: Polytopes and Colorings
inferredcites →https://doi.org/10.1145/210332.210337openalex-snapshot
Color-coding
inferredcites →https://doi.org/10.1145/828.1884openalex-snapshot
Storing a Sparse Table with 0 (1) Worst Case Access Time
inferredcites →https://doi.org/10.1287/moor.26.2.193.10561openalex-snapshot
On Polyhedral Approximations of the Second-Order Cone
inferredcites →https://doi.org/10.1287/opre.38.1.127openalex-snapshot
Polyhedral Characterization of Discrete Dynamic Programming
inferredcites →https://doi.org/10.2307/2118652openalex-snapshot
A Characterization of Ideal Polyhedra in Hyperbolic 3-Space
inferredcites →https://doi.org/10.2307/2314023openalex-snapshot
Finite Permutation Groups.
inferredcites →https://doi.org/10.4007/annals.2003.158.977openalex-snapshot
Y -systems and generalized associahedra
inferredcites →https://doi.org/10.48550/arxiv.1105.0036openalex-snapshot
Some 0/1 polytopes need exponential size extended formulations
inferredcites →https://doi.org/10.48550/arxiv.1105.4127openalex-snapshot
Extended formulations, non-negative factorizations and randomized communication protocols
inferredcites →https://doi.org/10.48550/arxiv.1109.0815openalex-snapshot
Finding Descriptions of Polytopes via Extended Formulations and Liftings
inferredcites →https://doi.org/10.6028/jres.069b.013openalex-snapshot
Maximum matching and a polyhedron with 0,1-vertices

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1002/net.21849openalex-snapshot
A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”
inferred← citeshttps://doi.org/10.1007/978-3-030-17953-3_4openalex-snapshot
Extended Formulations from Communication Protocols in Output-Efficient Time
inferred← citeshttps://doi.org/10.1007/978-3-319-33461-5_29openalex-snapshot
Strong Reductions for Extended Formulations
inferred← citeshttps://doi.org/10.1007/978-3-662-48350-3_17openalex-snapshot
Enumeration of 2-Level Polytopes
inferred← citeshttps://doi.org/10.1007/s00453-016-0132-0openalex-snapshot
Common Information and Unique Disjointness
inferred← citeshttps://doi.org/10.1007/s00454-018-9988-xopenalex-snapshot
Euclidean Distance Matrices and Separations in Communication Complexity Theory
inferred← citeshttps://doi.org/10.1007/s10107-015-0862-9openalex-snapshot
Uncapacitated flow-based extended formulations
inferred← citeshttps://doi.org/10.1007/s10107-015-0867-4openalex-snapshot
Worst-case results for positive semidefinite rank
inferred← citeshttps://doi.org/10.1007/s10107-016-0989-3openalex-snapshot
Average case polyhedral complexity of the maximum stable set problem
inferred← citeshttps://doi.org/10.1007/s10107-017-1221-9openalex-snapshot
Affine reductions for LPs and SDPs
inferred← citeshttps://doi.org/10.1007/s10107-018-1316-yopenalex-snapshot
Strong reductions for extended formulations
inferred← citeshttps://doi.org/10.1007/s10107-020-01535-9openalex-snapshot
Extended formulations from communication protocols in output-efficient time
inferred← citeshttps://doi.org/10.1007/s10107-021-01652-zopenalex-snapshot
Ideal, non-extended formulations for disjunctive constraints admitting a network representation
inferred← citeshttps://doi.org/10.1007/s12532-018-0145-6openalex-snapshot
Enumeration of 2-level polytopes
inferred← citeshttps://doi.org/10.1007/s12532-024-00262-yopenalex-snapshot
Local elimination in the traveling salesman problem
inferred← citeshttps://doi.org/10.1016/j.dam.2019.03.016openalex-snapshot
Polynomial size linear programs for problems in P
inferred← citeshttps://doi.org/10.1016/j.ipl.2017.05.009openalex-snapshot
Fooling sets and the Spanning Tree polytope
inferred← citeshttps://doi.org/10.1016/j.orl.2015.01.004openalex-snapshot
Hidden vertices in extensions of polytopes
inferred← citeshttps://doi.org/10.1016/j.orl.2018.03.008openalex-snapshot
On the combinatorial lower bound for the extension complexity of the Spanning Tree polytope
inferred← citeshttps://doi.org/10.1016/j.orl.2021.03.006openalex-snapshot
Pitch, extension complexity, and covering problems
inferred← citeshttps://doi.org/10.1109/allerton.2015.7447134openalex-snapshot
Information theory and polyhedral combinatorics
inferred← citeshttps://doi.org/10.1109/focs.2012.10openalex-snapshot
Approximation Limits of Linear Programs (Beyond Hierarchies)
inferred← citeshttps://doi.org/10.1109/focs.2013.45openalex-snapshot
Approximate Constraint Satisfaction Requires Large LP Relaxations
inferred← citeshttps://doi.org/10.1109/focs.2015.73openalex-snapshot
No Small Linear Program Approximates Vertex Cover within a Factor 2 -- e
inferred← citeshttps://doi.org/10.1109/tit.2015.2465864openalex-snapshot
The Matching Problem Has No Fully Polynomial Size Linear Programming Relaxation Schemes
inferred← citeshttps://doi.org/10.1137/1.9781611973730.57openalex-snapshot
The matching polytope does not admit fully-polynomial size relaxation schemes
inferred← citeshttps://doi.org/10.1145/2746539.2746550openalex-snapshot
Inapproximability of Combinatorial Problems via Small LPs and SDPs
inferred← citeshttps://doi.org/10.48550/arxiv.1204.0957openalex-snapshot
Approximation Limits of Linear Programs (Beyond Hierarchies)
inferred← citeshttps://doi.org/10.48550/arxiv.1305.4600openalex-snapshot
Worst-Case Results For Positive Semidefinite Rank
inferred← citeshttps://doi.org/10.48550/arxiv.1306.3119openalex-snapshot
Uncapacitated Flow-based Extended Formulations
inferred← citeshttps://doi.org/10.48550/arxiv.1404.2752openalex-snapshot
Hidden Vertices in Extensions of Polytopes
inferred← citeshttps://doi.org/10.48550/arxiv.1609.05374openalex-snapshot
Online Learning of Combinatorial Objects via Extended Formulation
inferred← citeshttps://doi.org/10.48550/arxiv.1712.08559openalex-snapshot
An Approximate Shapley-Folkman Theorem
inferred← citeshttps://doi.org/10.48550/arxiv.1811.08529openalex-snapshot
Extended formulations from communication protocols in output-efficient time
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.