8 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…
Improved Maximin Share Guarantee for Additive Valuations
Ehsan Heidari, Alireza Kaviani, Masoud Seddighin +1
The maximin share () is the most prominent share-based fairness notion in the fair allocation of indivisible goods. Recent years have seen significant efforts to impr…
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…
Improved Approximate EFX Guarantees for Multigraphs
Alireza Kaviani, Alireza Keshavarz, Masoud Seddighin +1
In recent years, a new line of work in fair allocation has focused on EFX allocations for \((p, q)\)-bounded valuations, where each good is relevant to at most \(p\) agents, and an…
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…