Ariel Kulik
Postdoctoral Researcher, The Technion
I am a postdoctoral researcher at the Technion, hosted by Roy Schwartz. Previously, I was a postdoc at CISPA, hosted by Dániel Marx. I joined CISPA after the completion of my Ph.D at the Technion, where I was working 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.
Here is my CV.
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:
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:
I. Doron-Arad, A. Kulik and H. Shachnai, ``An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding", to appear in 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:
Computer Science Department, The Technion, Haifa, Israel
Email: firstname dot lastname at gmail dot com
Attempting to play the guitar
