Asaf Levin

CoRR, January, 2025

Sparse Integer Programming Is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

Friedrich Eisenbrand

Math. Oper. Res., 2025

Lower Bounds for Several Standard Bin Packing Algorithms in the Random Order Model.

[BibT_eX]

[DOI]

Proceedings of the 19th International Symposium on Algorithms and Data Structures, 2025

An Efficient Polynomial Time Approximation Scheme for Minimizing the Total Weighted Completion Time on Uniformly Related Machines.

[BibT_eX]

[DOI]

Proceedings of the 19th International Symposium on Algorithms and Data Structures, 2025

Efficient Approximation Schemes for Scheduling on a Stochastic Number of Machines.

[BibT_eX]

[DOI]

Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, 2025

An EPTAS for Minimizing the Total Weighted Completion Time of Jobs with Release Dates on Uniformly Related Machines.

[BibT_eX]

[DOI]

Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, 2025

(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs.

[BibT_eX]

[DOI]

Martin Koutecký

Tung Anh Vu

Proceedings of the Integer Programming and Combinatorial Optimization, 2025

2024

The Near Exact Bin Covering Problem.

[BibT_eX]

[DOI]

Algorithmica, June, 2024

Selecting intervals to optimize the design of observational studies subject to fine balance constraints.

[BibT_eX]

[DOI]

J. Comb. Optim., April, 2024

EPTAS for parallel identical machine scheduling with time restrictions.

[BibT_eX]

[DOI]

J. Comb. Optim., March, 2024

Scheduling with cardinality dependent unavailability periods.

[BibT_eX]

[DOI]

Eur. J. Oper. Res., 2024

APTAS for bin packing with general cost structures.

[BibT_eX]

[DOI]

CoRR, 2024

Tight Lower Bounds for Block-Structured Integer Programs.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2024

2023

EPTAS for the dual of splittable bin packing with cardinality constraint.

[BibT_eX]

[DOI]

Theor. Comput. Sci., November, 2023

Reducibility bounds of objective functions over the integers.

[BibT_eX]

[DOI]

Friedrich Eisenbrand

Oper. Res. Lett., November, 2023

Online cardinality constrained scheduling.

[BibT_eX]

[DOI]

Oper. Res. Lett., September, 2023

Online Minimization of the Maximum Starting Time: Migration Helps.

[BibT_eX]

[DOI]

Algorithmica, August, 2023

Online bin covering with limited migration.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., June, 2023

Weighted throughput in a single machine preemptive scheduling with continuous controllable processing times.

[BibT_eX]

[DOI]

Tal Shusterman

Acta Informatica, June, 2023

EPTAS for load balancing problem on parallel machines with a non-renewable resource.

[BibT_eX]

[DOI]

Discret. Optim., May, 2023

High-multiplicity N-fold IP via configuration LP.

[BibT_eX]

[DOI]

Math. Program., 2023

Algorithms and Complexities of Matching Variants in Covariate Balancing.

[BibT_eX]

[DOI]

Xu Rao

Oper. Res., 2023

2022

Comparing the costs of Any Fit algorithms for bin packing.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2022

Lower bounds for batched bin packing.

[BibT_eX]

[DOI]

J. Comb. Optim., 2022

Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2022

Approximate separable multichoice optimization over monotone systems.

[BibT_eX]

[DOI]

Discret. Optim., 2022

Starting time minimization for the maximum job variant.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2022

Approximation Schemes for the Generalized Extensible Bin Packing Problem.

[BibT_eX]

[DOI]

Algorithmica, 2022

Cardinality Constrained Scheduling in Online Models.

[BibT_eX]

[DOI]

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

2021

More on ordered open end bin packing.

[BibT_eX]

[DOI]

János Balogh

J. Sched., 2021

Parameterized complexity of configuration integer programs.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2021

Complexity, algorithms and applications of the integer network flow with fractional supplies problem.

[BibT_eX]

[DOI]

Xu Rao

Oper. Res. Lett., 2021

A New Lower Bound for Classic Online Bin Packing.

[BibT_eX]

[DOI]

Algorithmica, 2021

Truly Asymptotic Lower Bounds for Online Vector Bin Packing.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

A note on a variant of the online open end bin packing problem.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2020

Online bin packing with cardinality constraints resolved.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2020

Algorithms and Complexity for Variants of Covariates Fine Balance.

[BibT_eX]

[DOI]

Xu Rao

CoRR, 2020

Truly asymptotic lower bounds for online vector bin packing.

[BibT_eX]

[DOI]

János Balogh

CoRR, 2020

2019

Deadline TSP.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2019

Lower bounds for online bin covering-type problems.

[BibT_eX]

[DOI]

János Balogh

J. Sched., 2019

Lower Bounds for Several Online Variants of Bin Packing.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2019

On the performance guarantee of First Fit for sum coloring.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2019

Hypergraphic Degree Sequences are Hard.

[BibT_eX]

[DOI]

Bull. EATCS, 2019

Robust algorithms for total completion time.

[BibT_eX]

[DOI]

Discret. Optim., 2019

Multitype Integer Monoid Optimization and Applications.

[BibT_eX]

[DOI]

CoRR, 2019

An Algorithmic Theory of Integer Programming.

[BibT_eX]

[DOI]

Friedrich Eisenbrand

CoRR, 2019

A Unified Framework for Designing EPTAS for Load Balancing on Parallel Machines.

[BibT_eX]

[DOI]

Ishai Kones

Algorithmica, 2019

2018

Optimization over Degree Sequences.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2018

Online-bounded analysis.

[BibT_eX]

[DOI]

J. Sched., 2018

The benefit of preemption with respect to the ℓp norm.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2018

Weighted matching with pair restrictions.

[BibT_eX]

[DOI]

Optim. Lett., 2018

Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem.

[BibT_eX]

[DOI]

J. Comb. Optim., 2018

Min-Sum Bin Packing.

[BibT_eX]

[DOI]

David S. Johnson

J. Comb. Optim., 2018

Improved bounds for randomized preemptive online matching.

[BibT_eX]

[DOI]

Inf. Comput., 2018

Discounted Reward TSP.

[BibT_eX]

[DOI]

Algorithmica, 2018

Batch Coloring of Graphs.

[BibT_eX]

[DOI]

Algorithmica, 2018

A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs.

[BibT_eX]

[DOI]

Martin Koutecký

Shmuel Onn

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

A New and Improved Algorithm for Online Bin Packing.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

A Unified Framework for Designing EPTAS's for Load Balancing on Parallel Machines.

[BibT_eX]

[DOI]

Ishai Kones

Proceedings of the Sailing Routes in the World of Computation, 2018

2017

Power of Preemption for Minimizing Total Completion Time on Uniform Parallel Machines.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2017

An AFPTAS for variable sized bin packing with general activation costs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2017

Maximum coverage problem with group budget constraints.

[BibT_eX]

[DOI]

J. Comb. Optim., 2017

On nonlinear multi-covering problems.

[BibT_eX]

[DOI]

J. Comb. Optim., 2017

Approximate Shifted Combinatorial Optimization.

[BibT_eX]

[DOI]

CoRR, 2017

2016

Approximation Schemes for Makespan Minimization.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Shifted matroid optimization.

[BibT_eX]

[DOI]

Shmuel Onn

Oper. Res. Lett., 2016

The benefit of preemption for single machine scheduling so as to minimize total weighted completion time.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2016

A Unified Approach to Truthful Scheduling on Related Machines.

[BibT_eX]

[DOI]

Math. Oper. Res., 2016

Vertex Cover Meets Scheduling.

[BibT_eX]

[DOI]

Algorithmica, 2016

2015

The benefit of adaptivity in stochastic packing problems with probing.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Offline black and white bin packing.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Min-max cover of a graph with a small number of parts.

[BibT_eX]

[DOI]

Discret. Optim., 2015

Lexicographic Matroid Optimization.

[BibT_eX]

[DOI]

Shmuel Onn

CoRR, 2015

The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases.

[BibT_eX]

[DOI]

Algorithmica, 2015

Online File Caching with Rejection Penalties.

[BibT_eX]

[DOI]

Algorithmica, 2015

2014

Adaptivity in the stochastic blackjack knapsack problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2014

An efficient polynomial time approximation scheme for load balancing on uniformly related machines.

[BibT_eX]

[DOI]

Math. Program., 2014

Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees.

[BibT_eX]

[DOI]

Uri Yovel

J. Comb. Optim., 2014

Minimum total weighted completion time: Faster approximation schemes.

[BibT_eX]

[DOI]

CoRR, 2014

Robust Algorithms for Preemptive Scheduling.

[BibT_eX]

[DOI]

Algorithmica, 2014

2013

Approximation Algorithms for a Minimization Variant of the Order-Preserving Submatrices and for Biclustering Problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2013

Robust Approximation Schemes for Cube Packing.

[BibT_eX]

[DOI]

SIAM J. Optim., 2013

Nonoblivious 2-Opt heuristics for the traveling salesman problem.

[BibT_eX]

[DOI]

Uri Yovel

Networks, 2013

The benefit of adaptivity in the stochastic knapsack problem with dependence on the state of nature.

[BibT_eX]

[DOI]

Discret. Optim., 2013

Bin covering with cardinality constraints.

[BibT_eX]

[DOI]

Csanád Imreh

Discret. Appl. Math., 2013

Online Clustering with Variable Sized Clusters.

[BibT_eX]

[DOI]

Algorithmica, 2013

Improved Bounds for Online Preemptive Matching.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

2012

On the max coloring problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2012

Universal Sequencing on an Unreliable Machine.

[BibT_eX]

[DOI]

Alberto Marchetti-Spaccamela

SIAM J. Comput., 2012

Bin packing with general cost structures.

[BibT_eX]

[DOI]

Math. Program., 2012

Approximation Schemes for Packing Splittable Items with Cardinality Constraints.

[BibT_eX]

[DOI]

Algorithmica, 2012

On Equilibria for ADM Minimization Games.

[BibT_eX]

[DOI]

Algorithmica, 2012

2011

Uniform unweighted set cover: The power of non-oblivious local search.

[BibT_eX]

[DOI]

Uri Yovel

Theor. Comput. Sci., 2011

Max-min Online Allocations with a Reordering Buffer.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2011

Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2011

Graph coloring with rejection.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2011

Selfish bin coloring.

[BibT_eX]

[DOI]

J. Comb. Optim., 2011

Online variable-sized bin packing with conflicts.

[BibT_eX]

[DOI]

Lene M. Favrholdt

Discret. Optim., 2011

On Variants of File Caching.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Covering the edges of bipartite graphs using K2, 2 graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

Improved randomized results for the interval selection problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

Class constrained bin packing revisited.

[BibT_eX]

[DOI]

Csanád Imreh

Theor. Comput. Sci., 2010

Tight results for Next Fit and Worst Fit with resource augmentation.

[BibT_eX]

[DOI]

Joan Boyar

Theor. Comput. Sci., 2010

AFPTAS Results for Common Variants of Bin Packing: A New Method for Handling the Small Items.

[BibT_eX]

[DOI]

SIAM J. Optim., 2010

Class Constrained Bin Covering.

[BibT_eX]

[DOI]

Csanád Imreh

Theory Comput. Syst., 2010

Randomized algorithms for online bounded bidding.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2010

On the sum minimization version of the online bin covering problem.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2010

Minimization of SONET ADMs in ring networks revisited.

[BibT_eX]

[DOI]

Betzalel Menahem

Computing, 2010

How to allocate review tasks for robust ranking.

[BibT_eX]

[DOI]

Acta Informatica, 2010

Finding mobile data under delay constraints with searching costs.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Universal Sequencing on a Single Machine.

[BibT_eX]

[DOI]

Alberto Marchetti-Spaccamela

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

2009

A generalized minimum cost k-clustering.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2009

Approximating the minimum quadratic assignment problems.

[BibT_eX]

[DOI]

Maxim Sviridenko

ACM Trans. Algorithms, 2009

Online Capacitated Interval Coloring.

[BibT_eX]

[DOI]

Thomas Erlebach

SIAM J. Discret. Math., 2009

The multi-integer set cover and the facility terminal cover problem.

[BibT_eX]

[DOI]

Networks, 2009

A robust APTAS for the classical bin packing problem.

[BibT_eX]

[DOI]

Math. Program., 2009

Monotone Covering Problems with an Additional Covering Constraint.

[BibT_eX]

[DOI]

José R. Correa

Math. Oper. Res., 2009

Better bounds for minimizing SONET ADMs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2009

Approximation algorithms for maximum latency and partial cycle cover.

[BibT_eX]

[DOI]

Shlomi Rubinstein

Discret. Optim., 2009

AFPTAS results for common variants of bin packing: A new method to handle the small items

[BibT_eX]

[DOI]

CoRR, 2009

Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs.

[BibT_eX]

[DOI]

Magnús M. Halldórsson

Hadas Shachnai

Algorithmica, 2009

Variable Sized Online Interval Coloring with Bandwidth.

[BibT_eX]

[DOI]

Thomas Erlebach

Algorithmica, 2009

2008

Online unit clustering: Variations on a theme.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2008

On Bin Packing with Conflicts.

[BibT_eX]

[DOI]

SIAM J. Optim., 2008

Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2008

An APTAS for Generalized Cost Variable-Sized Bin Packing.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

A Faster, Better Approximation Algorithm for the Minimum Latency Problem.

[BibT_eX]

[DOI]

Aaron Archer

David P. Williamson

SIAM J. Comput., 2008

The computational complexity of graph contractions II: Two tough polynomially solvable cases.

[BibT_eX]

[DOI]

Daniël Paulusma

Networks, 2008

The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases.

[BibT_eX]

[DOI]

Daniël Paulusma

Networks, 2008

Asymptotic fully polynomial approximation schemes for variants of open-end bin packing.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2008

Approximation algorithm for minimizing total latency in machine scheduling with deliveries.

[BibT_eX]

[DOI]

Michal Penn

Discret. Optim., 2008

More on online bin packing with two item sizes.

[BibT_eX]

[DOI]

Discret. Optim., 2008

A PTAS for delay minimization in establishing wireless conference calls.

[BibT_eX]

[DOI]

Discret. Optim., 2008

Two-dimensional packing with conflicts.

[BibT_eX]

[DOI]

Acta Informatica, 2008

Improved Randomized Results for That Interval Selection Problem.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2008

2007

Approximation and heuristic algorithms for minimum-delay application-layer multicast trees.

[BibT_eX]

[DOI]

Eli Brosh

Yuval Shavitt

IEEE/ACM Trans. Netw., 2007

The finite horizon investor problem with a budget constraint.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2007

Flow trees for vertex-capacitated networks.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2007

SONET ADMs Minimization with Divisible Paths.

[BibT_eX]

[DOI]

Algorithmica, 2007

Covering the Edges of Bipartite Graphs Using K 2, 2 Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms, 5th International Workshop, 2007

Minimum Weighted Sum Bin Packing.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms, 5th International Workshop, 2007

Multi-dimensional Packing with Conflicts.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007

Approximating min-max k-clustering.

[BibT_eX]

[DOI]

Proceedings of the Fair Division, 24.06. - 29.06.2007, 2007

2006

Partial multicuts in trees.

[BibT_eX]

[DOI]

Danny Segev

Theor. Comput. Sci., 2006

The conference call search problem in wireless networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2006

The minimum generalized vertex cover problem.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2006

Optimizing over Consecutive 1's and Circular 1's Constraints.

[BibT_eX]

[DOI]

SIAM J. Optim., 2006

The constrained minimum weighted sum of job completion times problem.

[BibT_eX]

[DOI]

Math. Program., 2006

Methodologies and Algorithms for Group-Rankings Decision.

[BibT_eX]

[DOI]

Manag. Sci., 2006

Approximations for minimum and min-max vehicle routing problems.

[BibT_eX]

[DOI]

Esther M. Arkin

J. Algorithms, 2006

Real time scheduling with a budget: Parametric-search is better than binary search.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2006

Cyclical scheduling and multi-shift scheduling: Complexity and approximation algorithms.

[BibT_eX]

[DOI]

Discret. Optim., 2006

Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms, 4th International Workshop, 2006

The k-Allocation Problem and Its Variants.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms, 4th International Workshop, 2006

2005

The chord version for SONET ADMs minimization.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem.

[BibT_eX]

[DOI]

Jochen Könemann

Amitabh Sinha

Algorithmica, 2005

Approximation Algorithms for Quickest Spanning Tree Problems.

[BibT_eX]

[DOI]

Algorithmica, 2005

An Approximation Algorithm for the Minimum Latency Set Cover Problem.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2005

Tracking mobile users.

[BibT_eX]

[DOI]

Proceedings of the Algorithms for Optimization with Incomplete Information, 2005

2004

An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection.

[BibT_eX]

[DOI]

SIAM J. Comput., 2004

Strongly polynomial-time approximation for a class of bicriteria problems.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2004

A better approximation algorithm for the budget prize collecting tree problem.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2004

Synthesis of 2-Commodity Flow Networks.

[BibT_eX]

[DOI]

Math. Oper. Res., 2004

Minimum restricted diameter spanning trees.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2004

2003

The SONET edge-partition problem.

[BibT_eX]

[DOI]

Networks, 2003

Minimum spanning tree with hop restrictions.

[BibT_eX]

[DOI]

J. Algorithms, 2003

Lexicographic local search and the p.

[BibT_eX]

[DOI]

Dana Morad

Eur. J. Oper. Res., 2003

Subgraphs decomposable into two trees and k-edge-connected subgraphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2003

The Complexity of Graph Contractions.

[BibT_eX]

[DOI]

Daniël Paulusma

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2003

2002

Approximation algorithms for constructing wavelength routing networks.

[BibT_eX]

[DOI]