5 papers
Dynamic Pattern Matching with Wildcards
Arshia Ataee Naeini, Amir-Parsa Mobed, Masoud Seddighin +1
We study the fully dynamic pattern matching problem where the pattern may contain up to kwildcard symbols, each matching any symbol of the alphabet. Both the text and the pattern a…
Fair Assignment of Indivisible Chores to Asymmetric Agents
Masoud Seddighin, Saeed Seddighin
We consider the problem of assigning indivisible chores to agents with different entitlements in the maximin share value (\MMS) context. While constant-\MMS\ allocations/assignment…
Quantum Pattern Matching with Wildcards
Masoud Seddighin, Saeed Seddighin
Pattern matching is one of the fundamental problems in Computer Science. Both the classic version of the problem as well as the more sophisticated version where wildcards can also…
Lower Bound for Online MMS Assignment of Indivisible Chores
Masoud Seddighin, Saeed Seddighin
We consider the problem of online assignment of indivisible chores under \MMS\ criteria. The previous work proves that any deterministic online algorithm for chore division has a c…
Beating the Logarithmic Barrier for the Subadditive Maximin Share Problem
Masoud Seddighin, Saeed Seddighin
We study the problem of fair allocation of indivisible goods for subadditive agents. While constant-\textsf{MMS} bounds have been given for additive and fractionally subadditive ag…