Zobrazeno 1 - 10
of 3 507
pro vyhledávání: '"A. Rohwedder"'
Autor:
Rohwedder, Lars, Węgrzycki, Karol
Integer linear programs $\min\{c^T x : A x = b, x \in \mathbb{Z}^n_{\ge 0}\}$, where $A \in \mathbb{Z}^{m \times n}$, $b \in \mathbb{Z}^m$, and $c \in \mathbb{Z}^n$, can be solved in pseudopolynomial time for any fixed number of constraints $m = O(1)
Externí odkaz:
http://arxiv.org/abs/2409.03681
Autor:
Rohwedder, Lars, Węgrzycki, Karol
Integer Linear Programming with $n$ binary variables and $m$ many $0/1$-constraints can be solved in time $2^{\tilde O(m^2)} \text{poly}(n)$ and it is open whether the dependence on $m$ is optimal. Several seemingly unrelated problems, which include
Externí odkaz:
http://arxiv.org/abs/2409.03675
We consider the problem of allocating indivisible resources to players so as to maximize the minimum total value any player receives. This problem is sometimes dubbed the Santa Claus problem and its different variants have been subject to extensive r
Externí odkaz:
http://arxiv.org/abs/2407.04824
We consider the problem of finding a basis of a matroid with weight exactly equal to a given target. Here weights can be discrete values from $\{-\Delta,\ldots,\Delta\}$ or more generally $m$-dimensional vectors of such discrete values. We resolve th
Externí odkaz:
http://arxiv.org/abs/2404.03747
Local search is a widely used technique for tackling challenging optimization problems, offering significant advantages in terms of computational efficiency and exhibiting strong empirical behavior across a wide range of problem domains. In this pape
Externí odkaz:
http://arxiv.org/abs/2401.05956
A prominent problem in scheduling theory is the weighted flow time problem on one machine. We are given a machine and a set of jobs, each of them characterized by a processing time, a release time, and a weight. The goal is to find a (possibly preemp
Externí odkaz:
http://arxiv.org/abs/2308.06209
Traditional minutiae-based fingerprint representations consist of a variable-length set of minutiae. This necessitates a more complex comparison causing the drawback of high computational cost in one-to-many comparison. Recently, deep neural networks
Externí odkaz:
http://arxiv.org/abs/2307.08615
In this paper we study the relation of two fundamental problems in scheduling and fair allocation: makespan minimization on unrelated parallel machines and max-min fair allocation, also known as the Santa Claus problem. For both of these problems the
Externí odkaz:
http://arxiv.org/abs/2307.08453
We consider box-constrained integer programs with objective $g(Wx) + c^T x$, where $g$ is a "complicated" function with an $m$ dimensional domain. Here we assume we have $n \gg m$ variables and that $W \in \mathbb Z^{m \times n}$ is an integer matrix
Externí odkaz:
http://arxiv.org/abs/2303.02474
Publikováno v:
ACS Omega, Vol 9, Iss 36, Pp 38107-38115 (2024)
Externí odkaz:
https://doaj.org/article/98fa55f6cfa74801b57ed52f722dc731
