Hadas Shachnai

Orcid: 0000-0002-6645-4350

Affiliations:
  • Technion - Israel Institute of Technology, Haifa, Israel


According to our database1, Hadas Shachnai authored at least 140 papers between 1991 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
The preemptive resource allocation problem.
J. Sched., February, 2024

Approximations and Hardness of Packing Partially Ordered Items.
CoRR, 2024

Lower Bounds for Matroid Optimization Problems with a Linear Constraint.
Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding.
Proceedings of the Approximation, 2024

Spatial Voting with Incomplete Voter Information.
Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence, 2024

2023
An FPTAS for budgeted laminar matroid independent set.
Oper. Res. Lett., November, 2023

Tight Bounds for Budgeted Maximum Weight Independent Set in Bipartite and Perfect Graphs.
CoRR, 2023

Tight Lower Bounds for Weighted Matroid Problems.
CoRR, 2023

Finding Possible and Necessary Winners in Spatial Voting with Partial Information.
CoRR, 2023

An EPTAS for Budgeted Matching and Budgeted Matroid Intersection.
CoRR, 2023

Approximating Bin Packing with Conflict Graphs via Maximization Techniques.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2023

An EPTAS for Budgeted Matroid Independent Set.
Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Budgeted Matroid Maximization: a Parameterized Viewpoint.
Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

Improved Approximation for Two-Dimensional Vector Multiple Knapsack.
Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

An EPTAS for Budgeted Matching and Budgeted Matroid Intersection via Representative Sets.
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP Rounding.
Proceedings of the Approximation, 2023

2022
An almost optimal approximation algorithm for monotone submodular multiple knapsack.
J. Comput. Syst. Sci., 2022

Bin Packing with Partition Matroid can be Approximated within $o(OPT)$ Bins.
CoRR, 2022

An Asymptotic (4/3+ε)-Approximation for the 2-Dimensional Vector Bin Packing Problem.
CoRR, 2022

2021
A refined analysis of submodular Greedy.
Oper. Res. Lett., 2021

On Lagrangian relaxation for constrained maximization and reoptimization problems.
Discret. Appl. Math., 2021

A Faster Tight Approximation for Submodular Maximization Subject to a Knapsack Constraint.
CoRR, 2021

An APTAS for Bin Packing with Clique-Graph Conflicts.
Proceedings of the Algorithms and Data Structures - 17th International Symposium, 2021

Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping.
Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020
The Euclidean <i>k</i>-Supplier Problem.
Math. Oper. Res., 2020

An APTAS for Bin Packing with Clique-graph Conflicts.
CoRR, 2020

tight approximations for modular and submodular optimization with d-resource multiple knapsack constraints.
CoRR, 2020

Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

A (1-e<sup>-1</sup>-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem.
Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Maximizing Throughput in Flow Shop Real-Time Scheduling.
Proceedings of the Approximation, 2020

2019
Constrained submodular maximization via greedy local search.
Oper. Res. Lett., 2019

Improved Parameterized Algorithms for Network Query Problems.
Algorithmica, 2019

Flexible Resource Allocation to Interval Jobs.
Algorithmica, 2019

Generalized Assignment via Submodular Optimization with Reserved Capacity.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018
Flexible bandwidth assignment with application to optical networks.
J. Sched., 2018

Parameterized approximation via fidelity preserving transformations.
J. Comput. Syst. Sci., 2018

Complexity and inapproximability results for the Power Edge Set problem.
J. Comb. Optim., 2018

A Theory and Algorithms for Combinatorial Reoptimization.
Algorithmica, 2018

Brief Announcement: Approximation Algorithms for Preemptive Resource Allocation.
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, 2018

Generalized Assignment of Time-Sensitive Item Groups.
Proceedings of the Approximation, 2018

Polynomial Time Approximation Schemes.
Proceedings of the Handbook of Approximation Algorithms and Metaheuristics, 2018

2017
Parameterized Algorithms for Graph Partitioning Problems.
Theory Comput. Syst., 2017

Optimizing bandwidth allocation in elastic optical networks with application to scheduling.
J. Discrete Algorithms, 2017

A multivariate framework for weighted FPT algorithms.
J. Comput. Syst. Sci., 2017

Fast Distributed Approximation for Max-Cut.
Proceedings of the Algorithms for Sensor Systems, 2017

2016
Tractable Parameterizations for the Minimum Linear Arrangement Problem.
ACM Trans. Comput. Theory, 2016

Constructing minimum changeover cost arborescenses in bounded treewidth graphs.
Theor. Comput. Sci., 2016

All-Or-Nothing Generalized Assignment with Application to Scheduling Advertising Campaigns.
ACM Trans. Algorithms, 2016

Representative families: A unified tradeoff-based approach.
J. Comput. Syst. Sci., 2016

Deterministic parameterized algorithms for the Graph Motif problem.
Discret. Appl. Math., 2016

Flexible Resource Allocation for Clouds and All-Optical Networks.
CoRR, 2016

Brief Announcement: Flexible Resource Allocation for Clouds and All-Optical Networks.
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, 2016

Real-Time k-bounded Preemptive Scheduling.
Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments, 2016

2015
Real-time scheduling to minimize machine busy times.
J. Sched., 2015

Partial Information Network Queries.
J. Discrete Algorithms, 2015

On Lagrangian Relaxation and Reoptimization Problems.
CoRR, 2015

A Multivariate Approach for Weighted FPT Algorithms.
Proceedings of the Algorithms - ESA 2015, 2015

The Container Selection Problem.
Proceedings of the Approximation, 2015

2014
Packing resizable items with application to video delivery over wireless networks.
Theor. Comput. Sci., 2014

FPT Algorithms for Weighted Graphs Can be (Almost) as Efficient as for Unweighted.
CoRR, 2014

Faster Computation of Representative Families for Uniform Matroids with Applications.
CoRR, 2014

Tighter Bounds for Makespan Minimization on Unrelated Machines.
CoRR, 2014

Flexible Bandwidth Assignment with Application to Optical Networks - (Extended Abstract).
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Optimizing Bandwidth Allocation in Flex-Grid Optical Networks with Application to Scheduling.
Proceedings of the 2014 IEEE 28th International Parallel and Distributed Processing Symposium, 2014

Scheduling jobs with dwindling resource requirements in clouds.
Proceedings of the 2014 IEEE Conference on Computer Communications, 2014

2013
Corrigendum: Improved results for data migration and open shop scheduling.
ACM Trans. Algorithms, 2013

Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints.
Math. Oper. Res., 2013

Online selection of intervals and t-intervals.
Inf. Comput., 2013

The Euclidean k-Supplier Problem.
Proceedings of the Integer Programming and Combinatorial Optimization, 2013

2012
Minimal cost reconfiguration of data placement in a storage area network.
Theor. Comput. Sci., 2012

Fast Information Spreading in Graphs with Large Weak Conductance.
SIAM J. Comput., 2012

Approximation schemes for generalized two-dimensional vector packing with application to data placement.
J. Discrete Algorithms, 2012

A Theory and Algorithms for Combinatorial Reoptimization.
Proceedings of the LATIN 2012: Theoretical Informatics, 2012

2011
Approximation schemes for deal splitting and covering integer programs with multiplicity constraints.
Theor. Comput. Sci., 2011

Packing and Scheduling Algorithms for Information and Communication Services (Dagstuhl Seminar 11091).
Dagstuhl Reports, 2011

Approximations for Monotone and Non-monotone Submodular Maximization with Knapsack Constraints
CoRR, 2011

2010
Minimizing total busy time in parallel scheduling with application to optical networks.
Theor. Comput. Sci., 2010

There is no EPTAS for two-dimensional knapsack.
Inf. Process. Lett., 2010

Transactional Contention Management as a Non-Clairvoyant Scheduling Problem.
Algorithmica, 2010

Online Selection of Intervals and <i>t</i>-Intervals.
Proceedings of the Algorithm Theory, 2010

Partial information spreading with application to distributed maximum coverage.
Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Return of the Boss Problem: Competing Online against a Non-adaptive Adversary.
Proceedings of the Fun with Algorithms, 5th International Conference, 2010

Minimizing Busy Time in Multiple Machine Real-time Scheduling.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

2009
Periodic scheduling with obligatory vacations.
Theor. Comput. Sci., 2009

Throughput maximization of real-time scheduling with batching.
ACM Trans. Algorithms, 2009

A note on generalized rank aggregation.
Inf. Process. Lett., 2009

Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs.
Algorithmica, 2009

Maximizing submodular set functions subject to multiple linear constraints.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008
Improved bounds for scheduling conflicting jobs with minsum criteria.
ACM Trans. Algorithms, 2008

Exact algorithms for the master ring problem.
Networks, 2008

Approximation Schemes for Packing with Item Fragmentation.
Theory Comput. Syst., 2008

On Lagrangian Relaxation and Subset Selection Problems.
Proceedings of the Approximation and Online Algorithms, 6th International Workshop, 2008

Batch Coloring Flat Graphs and Thin.
Proceedings of the Algorithm Theory, 2008

2007
Polynomial-Time Approximation Schemes.
Proceedings of the Handbook of Approximation Algorithms and Metaheuristics., 2007

Real-Time Scheduling with a Budget.
Algorithmica, 2007

Fast Asymptotic FPTAS for Packing Fragmentable Items with Costs.
Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007

2006
Improved results for data migration and open shop scheduling.
ACM Trans. Algorithms, 2006

Scheduling Split Intervals.
SIAM J. Comput., 2006

2005
Minimizing Makespan and Preemption Costs on a System of Uniform Machines.
Algorithmica, 2005

Fairness-Free Periodic Scheduling with Vacations.
Proceedings of the Algorithms, 2005

2004
Tight bounds for online class-constrained packing.
Theor. Comput. Sci., 2004

Finding Large Independent Sets in Graphs and Hypergraphs.
SIAM J. Discret. Math., 2004

Strongly competitive algorithms for caching with pipelined prefetching.
Inf. Process. Lett., 2004

Tight bounds for FEC-based reliable multicast.
Inf. Comput., 2004

Approximation Schemes for Deal Splitting and Covering Integer Programs with Multiplicity Constraints.
Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

Improved Bounds for Sum Multicoloring and Scheduling Dependent Jobs with Minsum Criteria.
Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

2003
Dynamic schemes for speculative execution of code.
Perform. Evaluation, 2003

Multicoloring trees.
Inf. Comput., 2003

Sum Coloring Interval and k-Claw Free Graphs with Application to Scheduling Dependent Jobs.
Algorithmica, 2003

Approximation Schemes for Generalized 2-Dimensional Vector Packing with Application to Data Placement.
Proceedings of the Approximation, 2003

2002
The passport control problem or how to keep a dynamic service system load balanced?
Theor. Comput. Sci., 2002

Multiprocessor Scheduling with Machine Allotment and Parallelism Constraints.
Algorithmica, 2002

2001
Scheduling memory accesses through a shared bus.
Perform. Evaluation, 2001

On Two Class-Constrained Versions of the Multiple Knapsack Problem.
Algorithmica, 2001

Efficient Reorganization of Binary Search Trees.
Algorithmica, 2001

Finding large independent sets of hypergraphs in parallel.
Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 2001

Minimizing Average Completion of Dedicated Tasks and Interval Graphs.
Proceedings of the Approximation, 2001

2000
Sum Multicoloring of Graphs.
J. Algorithms, 2000

On G-networks and resource allocation in multimedia systems.
Eur. J. Oper. Res., 2000

Polynominal time approximation schemes for class-constrained packing problem.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999
Local Labeling and Resource Allocation Using Preprocessing.
SIAM J. Comput., 1999

Multiresource Malleable Task Scheduling to Minimize Response Time.
Inf. Process. Lett., 1999

Self-Tuning Synchronization Mechanisms in Network Operating Systems.
Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, 1999

Sum Multi-coloring of Graphs.
Proceedings of the Algorithms, 1999

Multi-coloring Trees.
Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

1998
On Analytic Modeling of Multimedia Batching Schemes.
Perform. Evaluation, 1998

Exploring Wait Tolerance in Effective Batching for Video-on-Demand Scheduling.
Multim. Syst., 1998

On Chromatic Sums and Distributed Resource Allocation.
Inf. Comput., 1998

The List Update Problem: Improved Bounds for the Counter Scheme.
Algorithmica, 1998

Optimal Bounds on Tail Probabilities - A Simplified Approach.
Proceedings of the Parallel and Distributed Processing, 10 IPPS/SPDP'98 Workshops Held in Conjunction with the 12th International Parallel Processing Symposium and 9th Symposium on Parallel and Distributed Processing, Orlando, Florida, USA, March 30, 1998

1997
Disk Load Balancing for Video-On-Demand Systems.
Multim. Syst., 1997

IDABased Protocols for Reliable Multicast.
Proceedings of the On Principles Of Distributed Systems, 1997

Channel Based Scheduling of Parallelizable Task.
Proceedings of the MASCOTS 1997, 1997

1996
Adaptive Source Routing in High-Speed Networks.
J. Algorithms, 1996

On Chromatic Sums and Distributed Resource Allocation.
Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996

1995
Design and Analysis of a Look-Ahead Scheduling Scheme to Support Pause-Resume for Video-on-Demand Applications.
Multim. Syst., 1995

DASD Dancing: A Disk Load Balancing Optimization Scheme for Video-on-Demand Computer.
Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, 1995

1991
Self-Organizing Lists and Independent References: A Statistical Synergy.
J. Algorithms, 1991

On the Optimality of the Counter Scheme for Dynamic Linear Lists.
Inf. Process. Lett., 1991


  Loading...