Hadas Shachnai's Publications

On-Line Publications

Approximation Algorithms and Combinatorial Optimization

R. Y Pinter, H. Shachnai and M. Zehavi, `` Deterministic Parameterized Algorithms for the Graph Motif Problem''. Preliminary version in Proc. of MFCS 2014.
H. Shachnai and M. Zehavi, `` Representative Families: A Unified Tradeoff-Based Approach''. Preliminary version in Proc. of ESA 2014.
H. Shachnai and M. Zehavi, `` Parameterized Algorithms for Graph Partitioning Problems''. Accepted to WG 2014.
R. Y. Pinter, H. Shachnai and M. Zehavi, `` Partial Information Network Queries''. Submitted.
R. Y. Pinter, H. Shachnai and M. Zehavi, `` Improved Parameterized Algorithms for Network Query Problems''. Submitted.
S. Albagli-Kim, H. Shachnai and T. Tamir, `` Scheduling Jobs with Dwindling Resource Requirements in Clouds ''. Preliminary version in Proc. of INFOCOM 2014.
M. R. Fellows, D. Hermelin, F. Rosamond and H. Shachnai,`` Tractable Parameterizations for the Minimum Linear Arrangement Problem''. Preliminary version in Proc. of ESA 2013.
V. Nagarajan, B. Schieber and H. Shachnai, `` The Euclidean k-Supplier Problem''. Preliminary version in Proc. of IPCO 2013.
R. Adany, M. Feldman, E. Haramaty, R. Khandekar, B. Schieber, H. Shachnai and T. Tamir, `` All-or-Nothing Generalized Assignment with Application to Scheduling Advertising Campaigns''. Preliminary version in Proc. of IPCO 2013.
S. Albagli-Kim, L. Epstein, H. Shachnai and T. Tamir, `` Packing Resizable Items with Application to Video Delivery over Wireless Networks''. Preliminary version in Proc. of Algosensors 2012.
M. R. Fellows, A. Kulik, F. Rosamond and H. Shachnai,`` Parameterized Approximation via Fidelity Preserving Transformations''. Preliminary version in Proc. of ICALP'12.
B. Schieber, H. Shachnai, G. Tamir and T. Tamir, `` A Theory and Algorithms for Combinatorial Reoptimization''. Preliminary version in Proc. of LATIN'12.
A. Kulik, H. Shachnai and T. Tamir, ``Approximations for Monotone and Non-monotone Submodular Maximization with Knapsack Constraints ''. To appear in Math. of Operations Research. Preliminary version in Proc. of SODA'09.
R. Khandekar, B. Schieber, H. Shachnai and T. Tamir, `` Minimizing Busy Time in Multiple Machine Real-time Scheduling''. Preliminary version in FSTTCS'10.
A. Kulik and H. Shachnai,`` There is No EPTAS for Two-dimensional Knapsack''. In IPL, vol. 110, No. 16, 707--710, 2010.
H. Shachnai, G. Tamir and T. Tamir, `` Minimal Cost Reconfiguration of Data Placement in Storage Area Network''. Preliminary version in WAOA'09.
M. Flammini, G. Monaco, L. Moscardelli, H. Shachnai, M. Shalom, T. Tamir and S. Zaks,`` Minimizing Total Busy Time in Parallel Scheduling with Application to Optical Networks''. Preliminary version in Proc. of IPDPS'09.
H. Shachnai, T. Tamir and O. Yehezkely, ``Approximation Schemes for Packing with Item Fragmentation''. In Theory of Computing Systems (invited WAOA 2005 issue), vol. 43, No. 1, 81--98, 2008.
A. Kulik and H. Shachnai, `` On Lagrangian Relaxation and Subset Selection Problems''. Preliminary version in Proc. of WAOA'08.
M. M. Halldorsson and H. Shachnai, `` Batch Coloring Flat Graphs and Thin''. Preliminary version in Proc. of SWAT'08.
R. Gandhi, M. M. Halldorsson, Guy Kortsarz and H. Shachnai, `` Improved Bounds for Sum Multicoloring and Scheduling Dependent Jobs with Minsum Criteria''. ACM Transactions on Algorithms, vol. 4, No. 1, 2008.
H. Shachnai, L. Zhang and T. Matsui, `` The Master Ring Problem''. In Networks, vol 52, No. 2, 98--107, 2008. Preliminary version in Proc. of AofA'05.
H. Shachnai, and O. Yehezkely, `` Fast Asymptotic FPTAS for Packing Fragmentable Items with Costs''. Preliminary version in Proc. of FCT'07.
H. Shachnai, L. Zhang and T. Matsui, `` On Rank Aggregation of Multiple Orderings in Network Design''. Submited. Preliminary version in Proc. of INOC'07.
H. Shachnai and T. Tamir, `` Polynomial Time Approximation Schemes - A Survey''. In Handbook of Approximation Algorithms and Metaheuristics (Ed. Teofilo F. Gonzalez), Chapman & Hall/CRC Computer and Information Science Series, 2007.
L. Epstein, M. M. Halldorsson, A. Levin and H. Shachnai, `` Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs''. In Algorithmica 55(4): 643-665, 2009. Preliminary version in Proc. of APPROX'06.
J. Sgall, H. Shachnai and T. Tamir, `` Fairness-Free Periodic Scheduling with Vacations''. In Theor. Comput. Sci. 410(47-49), 2009. Preliminary version in Proc. of ESA'05.
A. Kulik, H. Shachnai, O. Shmueli and R. Sayegh, `` Approximation Schemes for Deal Splitting and Covering Integer Programs with Multiplicity Constraints''. Preliminary version in Proc. of WAOA'04.
R. Gandhi, M. M. Halldorsson, Guy Kortsarz and H. Shachnai, `` Improved Results for Data Migration and Open Shop Scheduling''. ACM Transactions on Algorithms, vol. 2, No. 1, 116--129, 2006. Preliminary version in Proc. of ICALP'04 (``Corrigendum'').
H. Shachnai, T. Tamir, `` Approximation Schemes for Generalized 2-dimensional Vector Packing with Application to Data Placement''. Submitted. Preliminary version in Proc. of APPROX'03.
J. Naor, H. Shachnai and T. Tamir, `` Real-time Scheduling with a Budget''. Algorithmica, vol. 47, 343--364, 2007. Preliminary version in Proc. of ICALP'03.
H. Shachnai, T. Tamir and G.J Woeginger, `` Minimizing Makespan and Preemption Costs on a System of Uniform Machines'', in Algorithmica (invited ESA 2002 issue), vol. 42, 309--334, 2005.
H. Shachnai and T. Tamir, `` Multiprocessor Scheduling with Machine Allotment and Parallelism Constraints'', in Algorithmica, vol. 32:4, 651--678, 2002.
A. Bar-Noy A., S. Guha, Y. Katz, J. Naor, B. Schieber and H. Shachnai, ``Throughput Maximization of Real-Time Scheduling with Batching ''. Accepted to ACM Transactions on Algorithms. Preliminary version in Proc. of SODA'02.
R. Bar-Yehuda, M. M. Halldorsson, J. Naor, H. Shachnai and I. Shapira, ``Scheduling Split Intervals ''. SIAM J. on Computing, vol. 36, No. 1, 1--15, 2006. Preliminary version in Proc. of SODA'02.
M. M. Halldorsson, G. Kortarz and H. Shachnai, ``Sum Coloring Interval and k-Claw Free Graphs with Application to Scheduling Dependent Jobs''. Algorithmica, vol. 37, 187--209, 2003. Preliminary version in Proc. of APPROX'01.
H. Shachnai and T. Tamir, ``Polynomial Time Approximation Schemes for Class-Constrained Packing Problems ''. J. of Scheduling (invited CONF 2000 issue), vol. 4:6, 313--338, 2001. Preliminary version in Proc. of APPROX'00.
A. Bar-Noy, M.M. Halldorsson, G. Kortsarz, R. Salman and H. Shachnai, `` Sum Multicoloring of Graphs '', J. of Algorithms, vol. 37:2, 422--450, 2000. Preliminary version in Proc. of ESA'99.
M. M. Halldorsson, G. Kortsarz, A. Proskurowski, R. Salman, H. Shachnai and J. A. Telle, `` Multicoloring Trees ''. Information and Computation, vol. 180, 113--129, 2003. Preliminary version in Proc. of COCOON'99.
H. Shachnai and T. Tamir, `` On Two Class-Constrained Versions of the Multiple Knapsack Problem'', Algorithmica, vol. 29, 442--467, 2001. (An early version: `` Noah Bagels - Some Combinatorial Aspects'', in Proc. of the International Conference on FUN with Algorithms, Isola d'Elba, June 1998.)
A. Bar-Noy, M. Bellare, M. Halldorsson, H. Shachnai, T. Tamir, `` On Chromatic Sums and Distributed Resource Allocation'', Information and Computation, vol. 140, 1998, pp. 183--202. Preliminary version in Proc. of ISTCS'96.
H. Shachnai, J. Turek, `` Multiresource Malleable Task Scheduling'', in IPL, vol. 70, 1999, pp. 47--52.

Online Algorithms

M. M. Halldorsson and H. Shachnai, `` Return of the Boss Problem: Competing Online Against a Non-Adaptive Adversary''. Preliminary version in FUN'10.
U. Th. Bachmann, M. M. Halldorsson and H. Shachnai, ``Online Selection of Intervals and t-Intervals''. Preliminary version in SWAT'10.
H. Attiya, L. Epstein, H. Shachnai and T. Tamir, `` Transactional Contention Management as a Non-Clairvoyant Scheduling Problem''. Algorithmica, vol. 57(1): 44--61, 2010. Preliminary version in Proc. of PODC'06.
A. Gaysinsky, A. Itai and H. Shachnai, `` Strongly Competitive Algorithms for Caching with Pipelined Prefetching''. IPL, vol. 91, 19--27, 2004. Preliminary version in Proc. of ESA'01.
H. Shachnai and Tami Tamir `` Tight Bounds for Online Class-Constrained Packing''. Theoretical Computer Science (invited LATIN 2002 issue), vol. 321, 103--123, 2004.

Probabilistic Analysis of Algorithms

M. Hofri and H. Shachnai, `` Efficient Reorganization of Binary Search Trees '', in Algorithmica, vol. 31, 378--402, 2001.
Itai, M. Rodeh and H. Shachnai, `` The Passport Control Problem or How to Keep a Dynamic Service System Load Balanced ?'', in Theoretical Computer Science (invited FUN'98 issue), vol. 282, 303--318, 2002.
H. Shachnai and M. Hofri, `` The List Update Problem: Improved Bounds for the Counter Scheme'', in Algorithmica (Special issue on Average Case Analysis), vol. 22, 1998, pp. 650--659.
Cohen A., Rabinovich Y., Schuster A., Shachnai H., `` Optimal Bounds on Tail Probabilities - A Simplified Approach'', in Proc. of WRPC'98.
A. Itai and H. Shachnai, `` Adaptive Source Routing in High-Speed Networks '', J. of Algorithms, vol. 20, 1996, pp.218-243.
Hofri M. and Shachnai H., `` The Application of Restricted Counter Schemes to Three Models of Linear Search'', Probability in the Engineering and Informational Sciences, vol. 6, 1992, pp. 371-389.
M. Hofri and H. Shachnai, `` On the Limited Utility of Auxiliary Information in the List Update Problem'', Stochastic Models, vol. 8, 1992, pp. 637-650.
M. Hofri and H. Shachnai, `` Self-Organizing Lists and Independent References - a Statistical Synergy '', J. of Algorithms, vol. 12, 1991, pp. 533-555.
M. Hofri and H. Shachnai, `` On the Optimality of the Counter Scheme for Dynamic Linear Lists '', IPL vol. 37, 1991, pp. 175-179.

Parallel and Distributed Computation

K. Censor-Hillel and H. Shachnai `` Fast Information Spreading in Graphs with a Large Weak Conductance''. Preliminary version in Proc. of SODA'11.
K. Censor-Hillel and H. Shachnai `` Partial Information Spreading with Application to Distributed Maximum Coverage''. Preliminary version in Proc. of PODC'10.
H. Shachnai and A. Srinivasan, ``Finding Large Independent Sets in Graphs and Hypergraphs''. SIAM J. on Discrete Mathematics, vol. 18, 488--500, 2005. Preliminary version in Proc. of SPAA'01.
H. Attiya, H. Shachnai, ``IDA-Based Protocols for Reliable Multicast''. Information and Computation, vol.190, 117--135, 2004. Preliminary version in Proc. of OPODIS'97.
H. Attiya, H. Shachnai, T. Tamir, `` Local Labeling and Resource Allocation Using Preprocessing''. SIAM J. on Computing, Vol. 28, 1999, pp. 1397--1414.
J. Glasgow, H. Shachnai, `` Channel Based Scheduling of Parallelizable Tasks''. In proceedings of MASCOTS'97.
J. Glasgow, H. Shachnai, `` Minimizing the Flow Time for Parallelizable Task Systems'', TR #790, Technion IIT, CS Dept., November 1993.

Modeling and Performance Evaluation

I. Dozorets, I. Gath and H. Shachnai, ``Prototype-Based Approximate Nearest Neighbor Search ''. In Proc. of the 5th WSES Multiconference on Circuits, Systems, Communications and Computers (CSCC 2001).
E. Almog and H. Shachnai, `` Scheduling Memory Accesses through a Shared Bus '', in Performance Evaluation (Special issue on SAPM 2000), vol. 46:2-3, 193--218, 2001.
Y. Hershko, D. Segal and H. Shachnai, `` Self-Tuning Synchronization Mechanisms in Network Operating Systems '', in Proc. of SIGMETRICS'99.
P. Raghavan, H. Shachnai and M. Yaniv, `` Dynamic Schemes for Speculative Execution of Code ''. Performance Evaluation, vol. 53:2, 125--142, 2003. Preliminary version in Proc. of MASCOTS'98.
E. Gelenbe, H. Shachnai, `` On G-Networks and Resource Allocation in Multimedia Systems''. European J. on Operational Research (Special issue on G-Networks), vol. 126:2, 308--318, 2000.
H. Shachnai, P.S. Yu, `` On Analytic Modeling of Multimedia Batching Scheme'', Performance Evaluation, vol. 33, 1998, pp. 201--213.
J.L. Wolf, P.S. Yu, H. Shachnai `` Disk Load Balancing for Video-on-Demand Systems'', ACM Multimedia Systems Journal, vol. 5(6), 1997.
H. Shachnai, P.S. Yu, `` Exploring Wait Tolerance in Effective Batching for Video-on-demand Scheduling'' ''. ACM Multimedia Systems Journal 6: 382--394, 1998.
P.S. Yu, J.L. Wolf, H. Shachnai, `` Design and Analysis of a Look_ahead Scheduling Scheme to Support Pause-Resume Video-on-Demand Applications''. ACM Multimedia Systems Journal, vol. 3, 1995, pp. 137-149.