Ariel Kulik
Senior Lecturer, Industrial Engineering and Management, Ben-Gurion University
Embedded Files
I am a Senior Lecturer in the Department of Industrial Engineering and Management at Ben-Gurion University. Before joining Ben-Gurion, I was a postdoctoral researcher at the Technion, hosted by Roy Schwartz, and at CISPA, hosted by Dániel Marx. I completed my Ph.D. at the Technion under the supervision of Hadas Shachnai.
My research focuses on parameterized approximation algorithms, and polynomial time approximation algorithms for resource allocation (knapsack, bin packing, submodular) problems.
Students:
Students:
Ilan Doron-Arad, Ph.d (Technion, joint supervision with Hadas Shachnai, thesis has been submitted)
Education:
Education:
Ph.D, Computer Science, Technion IIT, Israel, 2021.
Thesis Title: Submodular Maximization with Assignment Constraints and Parameterized Approximations.
Advisoer: Hadas Shachnai.
M.Sc, Summa Cum Laude, Computer Science, Technion IIT, Israel, 2011.
Thesis Title: Submudular and Linear Maximization with Knapsack Constraints.
Advisor: Prof. Hadas Shachnai.
B.A, Summa Cum Laude, Mathematics and Computer Science, The Open University, Israel, 2005.
Journal Publications:
Journal Publications:
T. Cohen, A. Kulik and H. Shachnai, ``Improved Approximation for Two-dimensional Vector Multiple Knapsack ". To appear in Computational Geometry: Theory and Applications.
I. Doron-Arad, A. Kulik and H. Shachnai, ``An FPTAS for Budgeted Laminar Matroid Independent Set". Operation Research Letters, 2023 (arxiv version).
B. Esmer, A. Kulik, D. Marx, P. Schepper and K. Węgrzycki, ``Computing Generalized Convolutions Faster Than Brute Force". Algorithmica, 2023.
Y. Fairstein, A. Kulik, J. Naor, D. Raz, H. Shachnai. ``An Almost Optimal Approximation Algorithm for Monotone Submodular Multiple Knapsack". Journal of Computer and System Sciences. 125: 149-165, 2022.
O. Rottenstreich, A. Kulik, A. Joshi, J. Rexford, G. Retvari and DS. Menasche. ``Data Plane Cooperative Caching with Dependencies". IEEE Transactions on Network and Service Management, 19(3):2092-2106, 2022.
A. Kulik, R. Schwartz and H. Shachnai, ``A Refined Analysis of Submodular Greedy". Operation Research Letters. 49(4):507-514, 2021 (ArXiv version).
A. Kulik, H. Shachnai and G. Tamir. ``On Lagrangian Relaxation for Constrained Maximization and Reoptimization Problems". Discrete Applied Mathematics. 296:164-178, 2021.
M.R. Fellows, A. Kulik, F. Rosamond and H. Shachnai. ``Parameterized approximation via fidelity preserving transformations". Journal of Computer and System Sciences. 93: 30-40, 2018.
A. Kulik, H. Shachnai and T. Tamir. ``Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints". Mathematics of Operations Research. 38(4): 729-739, 2013.
A. Kulik, H. Shachnai, O. Shmueli and R. Sayegh. ``Approximation schemes for deal splitting and covering integer programs with multiplicity constraints". Theoretical Computer Science. 412(52): 7087-7098, 2011.
A. Kulik and H. Shachnai. ``There is no EPTAS for two-dimensional knapsack". Information Processing Letters. 110(16): 707-710, 2010.
Conference Publications:
Conference Publications:
B. Esmer and A. Kulik, ``Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems", 52th International Colloquium on Automata, Languages, and Programming (ICALP), 2025 (Arxiv version).
I. Doron-Arad, F. Grandoni and A. Kulik, ``Unsplittable Flow on a Short Path", to appear in IPEC 2024 (ArXiv version).
I. Doron-Arad, A. Kulik and H. Shachnai, ``An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding". International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2024 (ArXiv version).
I. Doron-Arad, A. Kulik and H. Shachnai, ``Lower Bounds for Matroid Optimization Problems with a Linear Constraint", 51th International Colloquium on Automata, Languages, and Programming (ICALP), 2024 (ArXiv version).
B. Esmer, A. Kulik, D. Marx, D. Neuen, and R. Sharma, ``Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations", ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024 (ArXiv version).
T. Cohen, A. Kulik and H. Shachnai, ``Improved Approximation for Two-dimensional Vector Multiple Knapsack''. International Symposium on Algorithms and Computation (ISAAC), 2023 (ArXiv version).
B. Esmer, A. Kulik, D. Marx, D. Neuen, and R. Sharma, ``Approximate Monotone Local Search for Weighted Problems''. 18th International Symposium on Parameterized and Exact Computation (IPEC), 2023 (ArXiv version).
I. Doron-Arad, A. Kulik and H. Shachnai, ``Budgeted Matroid Maximization: a Parameterized Viewpoint''. 18th International Symposium on Parameterized and Exact Computation (IPEC), 2023 (ArXiv version).
A. Kulik, M. Mnich and H. Shachnai, ``Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding''. Symposium on Foundations of Computer Science (FOCS), 2023 (ArXiv Version).
I. Doron-Arad, A. Kulik and H. Shachnai, ``An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP Rounding''. International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2023 (ArXiv version).
I. Doron-Arad, A. Kulik and H. Shachnai, ``An EPTAS for Budgeted Matching and Budgeted Matroid Intersection". 50th International Colloquium on Automata, Languages, and Programming (ICALP), 2023 (ArXiv version).
I. Doron-Arad, A. Kulik and H. Shachnai, ``An EPTAS for Budgeted Matroid Independent Set''. In Symposium on Simplicity in Algorithms (SOSA), 2023 (ArXiv version).
B. Esmer, A. Kulik, D. Marx, P. Schepper and K. Węgrzycki, ``Computing Generalized Convolutions Faster Than Brute Force". 17th International Symposium on Parameterized and Exact Computation (IPEC), 2022 (ArXiv version).
B. Esmer, A. Kulik, D. Marx, D. Neuen, and R. Sharma, ``Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search''. 30th Annual European Symposium on Algorithms (ESA), 2022 (ArXiv version).
Y. Fairstein, A. Kulik and H. Shachnai, ``Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping". 29th Annual European Symposium on Algorithms (ESA), 2021 (ArXiv version).
Y. Fairstein, A. Kulik, J. Naor and D. Raz ``General Knapsack Problems in a Dynamic Setting". International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2021 (ArXiv version).
I. Doron-Arad, A. Kulik and H. Shachnai, ``An APTAS for Bin Packing with Clique-graph Conflicts". 17th Algorithms and Data Structures Symposium (WADS), 2021 (ArXiv version).
A. Kulik, and H. Shachnai. ``Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations". IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), November, 2020 (arXiv version, conference talk (20 min), frontier of parameterized complexity talk (50 min), technion theory seminar talk (1h)).
O. Rottenstreich, A. Kulik, A. Joshi, J. Rexford, G. Retvari and DS. Menasche. ``Cooperative Rule Caching for SDNs". IEEE International Conference on Cloud Networking (CloudNet), November, 2020.
Y. Fairstein, A. Kulik, J. Naor, D. Raz, H. Shachnai. ``A $(1-e^{-1}-\epsilon)$-Approximation for the Monotone Submodular Multiple Knapsack Problem". 28th Annual European Symposium on Algorithms (ESA), September 2020 (arXiv version, talk).
A. Kulik, K. Sarpatwar, H. Shachnai and B. Schieber. ``Generalized Assignment via Submodular Optimization with Reserved Capacity". 27th Annual European Symposium on Algorithms (ESA), Munich, September 2019 (arXiv version).
M.R. Fellows, A. Kulik, F. Rosamond and H Shachnai. ``Parameterized approximation via fidelity preserving transformations". Automata, Languages, and Programming - 39th International Colloquium (ICALP), Warwick, July 2012.
A. Kulik , H. Shachnai and T. Tamir. ``Maximizing Submodular Set Functions Subject to Multiple Linear Constraints". 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New York, January 2009.
A. Kulik. and H. Shachnai.``On Lagrangian Relaxation and Subset Selection Problems". 6th Workshop on Approximation and Online Algorithms (WAOA), Karlsruhe, September 2008.
Contact Information:
Contact Information:
Email: firstname dot lastname at gmail dot com
Attempting to play the guitar
Attempting to play the guitar
Memories from New-Zealand
Memories from New-Zealand
Page updated
Google Sites
Report abuse