Asaf Levin
YOU?
Author Swipe
View article: Tight lower bounds for block-structured integer programs
Tight lower bounds for block-structured integer programs Open
We study fundamental block-structured integer programs called tree-fold and multi-stage IPs. Tree-fold IPs have a constraint matrix with independent blocks linked together by few constraints in a recursive pattern. Transposing this constra…
View article: Semi-online models for cardinality constrained bin packing
Semi-online models for cardinality constrained bin packing Open
We study two semi-online models for bin packing and exhibit them on cardinality constrained bin packing with small values of k . In this variant of the bin packing problem, each bin can have at most k items whose total size does not exceed…
View article: (Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs
(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs Open
We study the general integer programming (IP) problem of optimizing a separable convex function over the integer points of a polytope: $\min \{f(\mathbf{x}) \mid A\mathbf{x} = \mathbf{b}, \, \mathbf{l} \leq \mathbf{x} \leq \mathbf{u}, \, \…
View article: Better and Simpler Reducibility Bounds over the Integers
Better and Simpler Reducibility Bounds over the Integers Open
We study the settings where we are given a function of n variables defined in a given box of integers. We show that in many cases we can replace the given objective function by a new function with a much smaller domain. Our approach allows…
View article: A Brief History of Parameterized Algorithms for Block-Structured Integer Programs (Invited Talk)
A Brief History of Parameterized Algorithms for Block-Structured Integer Programs (Invited Talk) Open
Integer Programming (IP) is a fundamental but computationally hard problem. Still, certain efficiently solvable subclasses have been identified over time, most notably totally unimodular IPs in the 1950s, and fixed-dimension IPs in the 198…
View article: Efficient Approximation Schemes for Scheduling on a Stochastic Number of Machines
Efficient Approximation Schemes for Scheduling on a Stochastic Number of Machines Open
We study three two-stage optimization problems with a similar structure and different objectives. In the first stage of each problem, the goal is to assign input jobs of positive sizes to unsplittable bags. After this assignment is decided…
View article: APTAS for bin packing with general cost structures
APTAS for bin packing with general cost structures Open
We consider the following generalization of the bin packing problem. We are given a set of items each of which is associated with a rational size in the interval [0,1], and a monotone non-decreasing non-negative cost function f defined ove…
View article: Selecting intervals to optimize the design of observational studies subject to fine balance constraints
Selecting intervals to optimize the design of observational studies subject to fine balance constraints Open
Motivated by designing observational studies using matching methods subject to fine balance constraints, we introduce a new optimization problem. This problem consists of two phases. In the first phase, the goal is to cluster the values of…
View article: The Near Exact Bin Covering Problem
The Near Exact Bin Covering Problem Open
We present a new generalization of the bin covering problem that is known to be a strongly NP-hard problem. In our generalization there is a positive constant $$\varDelta $$ , and we are given a set of items each of which has a positive …
View article: Tight Lower Bounds for Block-Structured Integer Programs
Tight Lower Bounds for Block-Structured Integer Programs Open
We study fundamental block-structured integer programs called tree-fold and multi-stage IPs. Tree-fold IPs admit a constraint matrix with independent blocks linked together by few constraints in a recursive pattern; and transposing their c…
View article: EPTAS for parallel identical machine scheduling with time restrictions
EPTAS for parallel identical machine scheduling with time restrictions Open
We consider the non-preemptive scheduling problem on identical machines where there is a parameter B and each machine in every unit length time interval can process up to B different jobs. The goal function we consider is the makespan mini…
View article: Tight Lower Bounds for Block-Structured Integer Programs
Tight Lower Bounds for Block-Structured Integer Programs Open
We study fundamental block-structured integer programs called tree-fold and multi-stage IPs. Tree-fold IPs admit a constraint matrix with independent blocks linked together by few constraints in a recursive pattern; and transposing their c…
View article: Online cardinality constrained scheduling
Online cardinality constrained scheduling Open
In online load balancing problems, jobs arrive over a list. Upon arrival of a job, the algorithm is required to assign it immediately and irrevocably to a machine. We consider such a makespan minimization problem with an additional cardina…
View article: Scheduling with cardinality dependent unavailability periods
Scheduling with cardinality dependent unavailability periods Open
We consider non-preemptive scheduling problems on parallel identical machines where machines change their status from being available to being unavailable and vice versa along the time horizon. The particular form of unavailability we cons…
View article: High-multiplicity N-fold IP via configuration LP
High-multiplicity N-fold IP via configuration LP Open
N -fold integer programs (IPs) form an important class of block-structured IPs for which increasingly fast algorithms have recently been developed and successfully applied. We study high-multiplicity N -fold IPs, which encode IPs succinctl…
View article: EPTAS for the dual of splittable bin packing with cardinality constraint
EPTAS for the dual of splittable bin packing with cardinality constraint Open
The problem considered is the splittable bin packing with cardinality constraint. It is a variant of the bin packing problem where items are allowed to be split into parts but the number of parts in each bin is at most a given upper bound.…
View article: The near exact bin covering problem
The near exact bin covering problem Open
We present a new generalization of the bin covering problem that is known to be a strongly NP-hard problem. In our generalization there is a positive constant $Δ$, and we are given a set of items each of which has a positive size. We would…
View article: Cardinality Constrained Scheduling in Online Models
Cardinality Constrained Scheduling in Online Models Open
Makespan minimization on parallel identical machines is a classical and intensively studied problem in scheduling, and a classic example for online algorithm analysis with Graham’s famous list scheduling algorithm dating back to the 1960s.…
View article: EPTAS for parallel identical machine scheduling with time restrictions
EPTAS for parallel identical machine scheduling with time restrictions Open
We consider the non-preemptive scheduling problem on identical machines where there is a parameter B and each machine in every unit length time interval can process up to B different jobs. The goal function we consider is the makespan mini…
View article: Parameterized complexity of configuration integer programs
Parameterized complexity of configuration integer programs Open
Configuration integer programs (IP) have been key in the design of algorithms for NP-hard high-multiplicity problems. First, we develop fast exact (exponential-time) algorithms for Configuration IP and matching hardness results. Second, we…
View article: EPTAS for load balancing problem on parallel machines with a non-renewable resource
EPTAS for load balancing problem on parallel machines with a non-renewable resource Open
The problem considered is the non-preemptive scheduling of independent jobs that consume a resource (which is non-renewable and replenished regularly) on parallel uniformly related machines. The input defines the speed of machines, size of…
View article: Truly Asymptotic Lower Bounds for Online Vector Bin Packing
Truly Asymptotic Lower Bounds for Online Vector Bin Packing Open
In this work, we consider online d-dimensional vector bin packing. It is known that no algorithm can have a competitive ratio of o(d/log² d) in the absolute sense, although upper bounds for this problem have always been presented in the as…
View article: Algorithms and Complexity for Variants of Covariates Fine Balance
Algorithms and Complexity for Variants of Covariates Fine Balance Open
We study here several variants of the covariates fine balance problem where we generalize some of these problems and introduce a number of others. We present here a comprehensive complexity study of the covariates problems providing polyno…