61 citations · 206 across the 60 of their papers we have counts for
42 papers · 1 filter
Dynamic Algorithms for Matroid Submodular Maximization
Kiarash Banihashem, Leyla Biabani, Samira Goudarzi +3
Submodular maximization under matroid and cardinality constraints are classical problems with a wide range of applications in machine learning, auction theory, and combinatorial op…
Trading Prophets
José Correa, Andrés Cristi, Paul Dütting +3
In this work we initiate the study of buy-and-sell prophet inequalities. We start by considering what is arguably the most fundamental setting. In this setting the online algorithm…
Dynamic Constrained Submodular Optimization with Polylogarithmic Update Time
Kiarash Banihashem, Leyla Biabani, Samira Goudarzi +3
Maximizing a monotone submodular function under cardinality constraint is a core problem in machine learning and database with many basic applications, including video and data…
Weighted Edit Distance Computation: Strings, Trees and Dyck
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +2
Given two strings of length over alphabet , and an upper bound on their edit distance, the algorithm of Myers (Algorithmica'86) and Landau and Vishkin (JCSS'88) computes…
-time Algorithm for Bounded Tree Edit Distance
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +3
Computing the edit distance of two strings is one of the most basic problems in computer science and combinatorial optimization. Tree edit distance is a natural generalization of e…
Optimal Algorithms for Free Order Multiple-Choice Secretary
Mohammad Taghi Hajiaghayi, Dariusz R. Kowalski, Piotr Krysta +1
Suppose we are given integer and boxes labeled by an adversary, each containing a number chosen from an unknown distribution. We have to choose an orde…