Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2311.07214 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916305346494464 |
|---|---|
| author | Bach, Eleonore Eisenbrand, Friedrich Rothvoss, Thomas Weismantel, Robert |
| author_facet | Bach, Eleonore Eisenbrand, Friedrich Rothvoss, Thomas Weismantel, Robert |
| contents | Given a convex set $Q \subseteq R^m$ and an integer matrix $W \in Z^{m \times n}$, we consider statements of the form $ \forall b \in Q \cap Z^m$ $\exists x \in Z^n$ s.t. $Wx \leq b$. Such statements can be verified in polynomial time with the algorithm of Kannan and its improvements if $n$ is fixed and $Q$ is a polyhedron. The running time of the best-known algorithms is doubly exponential in~$n$. In this paper, we provide a pseudopolynomial-time algorithm if $m$ is fixed. Its running time is $(m Δ)^{O(m^2)}$, where $Δ= \|W\|_\infty$. Furthermore it applies to general convex sets $Q$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_07214 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Forall-exist statements in pseudopolynomial time Bach, Eleonore Eisenbrand, Friedrich Rothvoss, Thomas Weismantel, Robert Optimization and Control Given a convex set $Q \subseteq R^m$ and an integer matrix $W \in Z^{m \times n}$, we consider statements of the form $ \forall b \in Q \cap Z^m$ $\exists x \in Z^n$ s.t. $Wx \leq b$. Such statements can be verified in polynomial time with the algorithm of Kannan and its improvements if $n$ is fixed and $Q$ is a polyhedron. The running time of the best-known algorithms is doubly exponential in~$n$. In this paper, we provide a pseudopolynomial-time algorithm if $m$ is fixed. Its running time is $(m Δ)^{O(m^2)}$, where $Δ= \|W\|_\infty$. Furthermore it applies to general convex sets $Q$. |
| title | Forall-exist statements in pseudopolynomial time |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2311.07214 |