Research Topics, Selected Publications and Presentations.

If you are looking for a paper of mine that is not available here, please send me an email and I will send you a copy.


Resource Allocation Problems, Approximation Algorithms.

 

Approximations for Monotone and Non-monotone Submodular Maximization with Knapsack Constraints. 

Mathematics of Operations Research, Joint work with Ariel Kulik and Hadas Shachnai.
Abstract , Journal Version

 

 Online Algorithm for Battery Utilization in Electric Vehicles. 

AAIA 2012 and Applied Artificial Intelligence Journal, Joint work with Ron Adany.
Abstract , Journal version

 

 A Theory and Algorithms for Combinatorial Reoptimization. 

LATIN 2012 and Algorithmica, Joint work with Hadas Shachnai, Gal Tamir and Baruch Schieber.
Abstract , Conference proc. , Journal version

 

 Maximizing Submodular Set Functions Subject to Multiple Linear Constraints. 

SODA 2009, Joint work with Ariel Kulik and Hadas Shachnai.
Abstract , Conference proc.

 

 Approximation Schemes for Packing with Item Fragmentation. 

WAOA 2005 and Theory of Computing Systems , Joint work with Hadas Shachnai and Omer Yehezkely.
Abstract , Journal version

 

Approximation Schemes for Generalized 2-dimensional Vector Packing with Application to Data Placement.
APPROX 2003 and Journal of Discrete Algorithms. Joint work with Hadas Shachnai.
Abstract , Conference proc.

Tight Bounds for Online Class-Constrained Packing.
LATIN 2002 and Theoretical Computer Science. Joint work with Hadas Shachnai.
Abstract , Journal version, Presentation slides  

Class-constrained Resource Allocation Problems.
My Ph.D Thesis Seminar, 2001.
Abstract , Presentation slides 

On Two Class-Constrained Versions of the Multiple Knapsack Problem.
Algorithmica . Joint work with Hadas Shachnai.
 Abstract , Paper
A shorter story-like version of this paper (recommended for children):
Noah Bagels - Some Combinatorial Aspects.
FUN with Algorithms, 1998.
Abstract , Paper  

Polynomial Time Approximation Schemes for Class-Constrained Packing Problems.
APPROX 2000 and Journal of Scheduling.
Joint work with Hadas Shachnai.
Abstract , Paper , Presentation slides
 


Algorithmic Game Theory.

  Race Scheduling Games.
SAGT 2020. Joint work with Shaul Rosner.  
Abstract ,  Conference Proc. ,  Full version

  Equilibrium Inefficiency in Resource Buying Games with Load-Dependent Costs.
SAGT 2020. Joint work with E. Georgoulaki and K. Kollias .  
Abstract ,  Conference Proc. 

  Scheduling Games with Machine-Dependent Priority Lists.
WINE 2019. Joint work with M. Schröder and V.R.Vijayalakshmi.  
Abstract ,  Conference Proc. ,  Full version

 Cost-Sharing Games in Real-Time Scheduling Systems.
WINE 2018.  
Abstract ,  Conference Proc.

 Alternating Reachability Games with Behavioral and Revenue Objectives.
LPAR 2018. Joint work with Orna Kupfernam 
Abstract ,  Conference Proc.

 The Power of One Secret Agent.
FUN with Algorithms 2018 and Theoretical Computer Science.  
Abstract ,  Conference Proc. ,  Journal version

 The Efficiency of Best-Response Dynamics.
SAGT 2017.  Joint work with Michal Feldman and Yuval Snappir. 
Abstract ,  Conference Proc.,  Full version

 Hierarchical Network Formation Games.
TACAS 2017.  Joint work with Orna Kupferman. 
Abstract ,  Conference Proc.

  Resource Allocation Games with Multiple Resource Classes.
WAOA 2016.  Joint work with Roy Ofer. 
Abstract ,  Conference Proc.

Cost-Sharing Scheduling Games on Restricted Unrelated Machines.
SAGT 2015 and Theoretical Computer Science.  Joint work with Guy Avni. 
Abstract ,  Journal version

Congestion Games with Multisets of Resources and Applications in Synthesis.
FSTTCS 2015.   Joint work with Guy Avni and Orna Kupferman. 
Abstract ,  Conference Proc.

Network-Formation Games with Regular Objectives
FoSSaCS 2014 and Information and Computation.  Joint work with Guy Avni and Orna Kupferman. 
Abstract ,  Conference proc. , Journal version (©Elsevier)

Load Rebalancing Games in Dynamic Systems with Migration Costs
SAGT 2013 and Theoretical Computer Science.  Joint work with Sofia Belikovetsky. 
Abstract ,  Journal version

Approximate Strong Equilibria in Job Scheduling Games: an Analysis for Two Uniformly Related Machines.
Discrete Applied Mathematics.  Joint work with M. Feldman. L. Epstein, L. Witkowski and M. Witkowski.
Abstract ,  Journal version

Convergence of Best-Response Dynamics in Games with Conflicting Congestion Effects
WINE 2012 and Information Processing Letters.  Joint work with Michal Feldman. 
Abstract ,  Journal version

Coping with Selfish On-going Behaviors.
LPAR 2010 and Information and Computation.  Joint work with Orna Kupferman. 
Abstract Conference proc , Journal version

Conflicting Congestion Effects in Resource Allocation Games.
WINE 2008 and Journal of Operation Research.  Joint work with Michal Feldman. 
Abstract , Conference proc. , Journal version

Approximate Strong Equilibrium in Job Scheduling Games.
SAGT 2008 and Journal of Artificial Intelligence Research.  Joint work with Michal Feldman. 
Abstract , Journal version

Beyond VCG: Frugality of Truthful Mechanisms.
FOCS 2005.  Joint work with Anna Karlin and  David Kempe. 
Abstract , Conference proc. 

 


Scheduling Algorithms

Analysis and Experimental Study of Heuristics for Job Scheduling Reoptimization Problems.

WCO 2016 and Studies in Computational Intelligence, Joint with Elad Iwanir.

Abstract, Journal version

 

Real-Time k-bounded Preemptive Scheduling.

ALENEX 2016, Joint with Sivan Albagli-Kim, Baruch Schieber and Hadas Shachnai.

Abstract, Conference proc.

 

Scheduling Jobs with Dwindling Resource Requirements in Clouds.

INFOCOM 2014, Joint with Sivan Albagli-Kim and Hadas Shachnai.

Abstract, Conference proc.

 

Reoptimization of the Minimum Total Flow-Time Scheduling Problem.

MedAlg 2012 and Sustainable Computing, Informatics and Systems. Joint with Guy Baram

Abstract , Conference proc, Journal version

 

Minimizing Busy Time in Multiple Machine Real-time Scheduling.

FSTTCS 2010. Joint with Rohit Khandekar, Baruch Schieber and Hadas Shachnai

Abstract , Conference proc, Journal version

 

Scheduling with Bully Selfish Jobs.

FUN with Algorithms 2010 and Theory of Computing Systems.
Abstract , Conference proc. , Journal version

 

Minimizing Total Busy Time in Parallel Scheduling with Application to Optical Networks.

IPDPS 2009 and Theoretical Computer Science. Joint work with  M. Flammini, G. Monaco,  L. Moscardelli , H. Shachnai, M. Shalom, and S. Zaks.

Abstract , Conference proc.

 

Transactional Contention Management as a Non-Clairvoyant Scheduling Problem.

PODC 2006 and Algorithmica.  Joint work with Hagit Attiya, Hadas Shachnai, and Leah Epstein.
Abstract , Conference proc. Journal version

 

Periodic Scheduling with Obligatory Vacations.

ESA 2005 and Theoretical Computer Science.  Joint work with Jiri Sgall and Hadas Shachnai.
Abstract , Conference proc., Journal version

 

Windows Scheduling of Arbitrary Length Jobs on Parallel Machines.

SPAA 2005 and Journal of Scheduling. Joint work with Amotz Bar-Noy,  Richard Ladner, and Tammy VanDeGrift.
Abstract , Conference proc. , Journal version

 Real-time Scheduling with a Budget.
ICALP 2003 and Algorithmica. Joint work with Hadas Shachnai and Seffi Naor.
Abstract , Conference proc., Journal version

 Minimizing Makespan and Preemption Costs on a System of Uniform Machines.
ESA 2002 and Algorithmica. Joint work with Hadas Shachnai and Gerhard Woeginger.
Abstract , Conference proc. , Journal version

Multiprocessor Scheduling with Machine Allotment and Parallelism Constraints.
Algorithmica. Joint work with Hadas Shachnai.
Abstract , Journal version.


Resource Allocation and Local Labeling in Distributed Systems.

Local Labeling and Resource Allocation Using Preprocessing.
WDAG 1994 and SIAM J. on Computing.
Joint work with Hagit Attiya and Hadas Shachnai.
Abstract, Journal version
 

On Chromatic Sums and Distributed Resource Allocation.
ISTCS 1996 and Information and Computation.
Joint work with Amotz Bar-Noy, Mihir Bellare, Magnus Halldorsson, and Hadas Shachnai.
Abstract , Journal version
 


Multimedia on Demand.  

 

Packing Resizable Items with Application to Video Delivery over Wireless Networks.

ALGOSENSORS 2012. Joint work with Sivan Albagli-Kim, Leah Epstein, and Hadas Shachnai.
Abstract

 

Minimal Cost Reconfiguration of Data Placement in Storage Area Network.

WAOA 2009 and Theoretical Computer Science. Joint work with Hadas Shachnai and Gal Tamir.
Abstract , Conference proc., Journal version

 

Algorithms for Storage Allocation Based on Client Preferences.

CO 2008 and Journal of Combinatorial Optimization. Joint work with Benny Vaksendiser.
Abstract , Journal version

 

Optimal Delay for Media-on-Demand with Pre-loading and Pre-buffering.

SIROCCO 2006 and Theoretical Computer Science. Joint work with Amotz Bar-Noy and Richard Ladner.
Abstract , Conference proc.  Journal version

 

A General Buffer Scheme for the Windows Scheduling Problem.

WEA 2005 and ACM Journal of Experimental Algorithmics. Joint work with Amotz Bar-Noy,  Richard Ladner, and Jacob Christensen.
Abstract , Conference proc , Journal version

Windows Scheduling as a Restricted Version of Bin-packing.
SODA 2004 and Transactions on Algorithms. Joint work with Amotz Bar-noy and Richard Ladner.
Abstract , Conference proc. , Journal version

Scheduling Techniques for Media on Demand.
SODA 2003 and Algorithmica. Joint work with Amotz Bar-noy and Richard Ladner.
Abstract , Conference proc., Journal version , Presentation slides

Storage Management for Continuous Media Data.
A preliminary version appeared in ISCIS 98 (An invited talk). 
The version below was presented in IBM Almaden research center, April 2001.

Abstract , Presentation slides
 


Other

Properties and Utilization of Capacitated Automata.
FSTTCS 2014. Joint work with Orna Kupferman.
Abstract , Conference proc.

Polynomial Time Approximation Schemes - A Survey.
Chapter 9 in Approximation Algorithms and Metaheuristics. Editor: Teofilo F. Gonzalez. Joint work with Hadas Shachnai. 
Book chapter.

Paging with Request Sets.
SWAT 2006 and Theory of Computing Systems.  Joint work with Leah Epstein and  Rob van Stee. 
Abstract Conference proc , Journal version.

 Semi-Matchings for Bipartite Graphs and Load Balancing.
WADS 2003 and Journal of Algorithms. Joint work with Nick Harvey, Richard Ladner, and Laszlo Lovasz.
Abstract , Journal version


 

A full list of my publications appears in my CV.

Back to  Home Page