Vectors in a box

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10125728" target="_blank" >RIV/00216208:11320/12:10125728 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s10107-011-0474-y" target="_blank" >http://dx.doi.org/10.1007/s10107-011-0474-y</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10107-011-0474-y" target="_blank" >10.1007/s10107-011-0474-y</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Vectors in a box

Popis výsledku v původním jazyce

For an integer d a parts per thousand yen 1, let tau(d) be the smallest integer with the following property: if v (1), v (2), . . . , v (t) is a sequence of t a parts per thousand yen 2 vectors in [-1, 1] (d) with , then there is a set of indices, 2 a parts per thousand currency sign |S| a parts per thousand currency sign tau(d), such that . The quantity tau(d) was introduced by Dash, Fukasawa, and Gunluk, who showed that tau(2) = 2, tau(3) = 4, and tau(d) = Omega(2 (d) ), and asked whether tau(d) is finite for all d. Using the Steinitz lemma, in a quantitative version due to Grinberg and Sevastyanov, we prove an upper bound of tau(d) a parts per thousand currency sign d (d+o(d)), and based on a construction of Alon and V, whose main idea goes back toHAyenstad, we obtain a lower bound of tau(d) a parts per thousand yen d (d/2-o(d)). These results contribute to understanding the master equality polyhedron with multiple rows defined by Dash et al. which is a "universal" polyhedron encod

Název v anglickém jazyce

Vectors in a box

Popis výsledku anglicky

For an integer d a parts per thousand yen 1, let tau(d) be the smallest integer with the following property: if v (1), v (2), . . . , v (t) is a sequence of t a parts per thousand yen 2 vectors in [-1, 1] (d) with , then there is a set of indices, 2 a parts per thousand currency sign |S| a parts per thousand currency sign tau(d), such that . The quantity tau(d) was introduced by Dash, Fukasawa, and Gunluk, who showed that tau(2) = 2, tau(3) = 4, and tau(d) = Omega(2 (d) ), and asked whether tau(d) is finite for all d. Using the Steinitz lemma, in a quantitative version due to Grinberg and Sevastyanov, we prove an upper bound of tau(d) a parts per thousand currency sign d (d+o(d)), and based on a construction of Alon and V, whose main idea goes back toHAyenstad, we obtain a lower bound of tau(d) a parts per thousand yen d (d/2-o(d)). These results contribute to understanding the master equality polyhedron with multiple rows defined by Dash et al. which is a "universal" polyhedron encod

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

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

Rok uplatnění

2012

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

Mathematical Programming, Series B

ISSN

0025-5610

e-ISSN

—

Svazek periodika

135

Číslo periodika v rámci svazku

1-2

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

13

Strana od-do

323-335

Kód UT WoS článku

000308647100012

EID výsledku v databázi Scopus

—