We show that assuming the Exponential Time Hypothesis, the Partial Minimum Branching Program Size Problem (MBPSP∗) requires superpolynomial time. This result also applies to the partial minimization problems for many interesting subclasses of branching pro ...
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2025
Approximate integer programming is the following: For a given convex body K subset of R-n, either determine whether K boolean AND Z(n) is empty, or find an integer point in the convex body 2 center dot (K - c)+ c which is K, scaled by 2 from its center of ...
Dedicated bus lanes provide a low cost and easily implementable strategy to improve transit service by minimizing congestion-related delays. Identifying the best spatial distribution of bus-only lanes in order to maximize traffic performance of an urban ne ...
In this paper, we resolve the complexity problem of spectral graph sparcification in dynamic streams up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses (O) over tilde (n) space, and with high probability, recover ...
The support of a vector is the number of nonzero components. We show that given an integral mxn matrix A, the integer linear optimization problem max {c(T) x : Ax = b, x >= 0, x is an element of Z(n)} has an optimal solution whose support is bounded by 2m ...
What-if analysis is a data-intensive exploration to inspect how changes in a set of input parameters of a model influence some outcomes. It is motivated by a user trying to understand the sensitivity of a model to a certain parameter in order to reach a se ...
