Compact linear programs for 2SAT

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10398318" target="_blank" >RIV/00216208:11320/19:10398318 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=k1V2.tW8sm" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=k1V2.tW8sm</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ejc.2018.02.011" target="_blank" >10.1016/j.ejc.2018.02.011</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Compact linear programs for 2SAT

Popis výsledku v původním jazyce

For each integer n we present an explicit formulation of a compact linear program, with O(n(3)) variables and constraints, which determines the satisfiability of any 2SAT formula with n boolean variables by a single linear optimization. This contrasts with the fact that the natural polytope for this problem, formed from the convex hull of all satisfiable formulas and their satisfying assignments, has superpolynomial extension complexity. Our formulation is based on multicommodity flows. We also discuss connections of these results to the stable matching problem. (C) 2018 Elsevier Ltd. All rights reserved.

Název v anglickém jazyce

Compact linear programs for 2SAT

Popis výsledku anglicky

For each integer n we present an explicit formulation of a compact linear program, with O(n(3)) variables and constraints, which determines the satisfiability of any 2SAT formula with n boolean variables by a single linear optimization. This contrasts with the fact that the natural polytope for this problem, formed from the convex hull of all satisfiable formulas and their satisfying assignments, has superpolynomial extension complexity. Our formulation is based on multicommodity flows. We also discuss connections of these results to the stable matching problem. (C) 2018 Elsevier Ltd. All rights reserved.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA15-11559S" target="_blank" >GA15-11559S: Rozšířené formulace polytopů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

European Journal of Combinatorics

ISSN

0195-6698

e-ISSN

—

Svazek periodika

80

Číslo periodika v rámci svazku

Srpen

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

6

Strana od-do

17-22

Kód UT WoS článku

000474675900003

EID výsledku v databázi Scopus

2-s2.0-85045549902