← All problems
Unverified

Fixed-Parameter Tractability of Zonotope Problems

Given a rational generator matrix G∈Qd×nG\in\mathbb Q^{d\times n} with columns g1,…,gng_1,\ldots,g_n, define

Z(G)=∑i=1nconv⁡{0,gi}={∑i=1nλigi:0≤λi≤1}. Z(G)=\sum_{i=1}^n\operatorname{conv}\{0,g_i\} =\left\{\sum_{i=1}^n\lambda_i g_i:0\leq\lambda_i\leq1\right\}.

An algorithm is fixed-parameter tractable in dd if it runs in f(d)nO(1)f(d)n^{O(1)} time for some computable function ff.

  1. Is LpL_p-maximization over dd-zonotopes fixed-parameter tractable with respect to dd for p>1p>1?

  2. Is dd-zonotope containment fixed-parameter tractable with respect to dd? That is, given generator matrices G1,G2G_1,G_2, decide whether Z(G1)⊆Z(G2)Z(G_1)\subseteq Z(G_2) in f(d)nO(1)f(d)n^{O(1)} time.

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu