19 citations · 25 across the 15 of their papers we have counts for
20 papers
On the Metric Distortion of the Minimum Spanning Tree Problem
Kian Ghassemi, Masoud Seddighin, Saeed Seddighin
We study the metric distortion of the minimum spanning tree (MST) problem when numerical edge weights are unavailable and each vertex reports only a ranking of the other vertices i…
Massively Parallel Algorithms for Huffman Coding
Masoud Seddighin, Saeed Seddighin
Huffman coding is one of the oldest and most fundamental problems in computer science. Given a string of length $\TextLength$ over a general alphabet, the goal is to assign a binar…
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…
Improved Weighted Maximin Share Guarantees for Indivisible Chores
Masoud Seddighin, Saeed Seddighin
We consider the problem of assigning indivisible chores to agents with different entitlements in the maximin share (\MMS) context. While constant-\MMS\ allocations are guaranteed t…
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…
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…
Almost Envy-free Allocation of Indivisible Goods: A Tale of Two Valuations
Alireza Kaviani, Masoud Seddighin, AmirMohammad Shahrezaei
The existence of allocations stands as one of the main challenges in discrete fair division.In this paper, we present symmetrical results on the existence of $\texts…
Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations
Hannaneh Akrami, Kurt Mehlhorn, Masoud Seddighin +1
We consider the problem of guaranteeing maximin-share (MMS) when allocating a set of indivisible items to a set of agents with fractionally subadditive (XOS) valuations. For XOS va…
Rainbow Cycle Number and EFX Allocations: (Almost) Closing the Gap
Shayan Chashm Jahan, Masoud Seddighin, Seyed-Mohammad Seyed-Javadi +1
Recently, some studies on the fair allocation of indivisible goods notice a connection between a purely combinatorial problem called the Rainbow Cycle problem and a fairness notion…
An EF2X Allocation Protocol for Restricted Additive Valuations
Hannaneh Akrami, Rojin Rezvan, Masoud Seddighin
We study the problem of fairly allocating a set of indivisible goods to a set of agents. Envy-freeness up to any good (EFX) criteria -- which requires that no agent prefers…
Almost Envy-freeness, Envy-rank, and Nash Social Welfare Matchings
Alireza Farhadi, MohammadTaghi Hajiaghayi, Mohamad Latifian +2
Envy-free up to one good (EF1) and envy-free up to any good (EFX) are two well-known extensions of envy-freeness for the case of indivisible items. It is shown that EF1 can always…
Approximating LCS in Linear Time: Beating the Barrier
MohammadTaghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin +1
Longest common subsequence (LCS) is one of the most fundamental problems in combinatorial optimization. Apart from theoretical importance, LCS has enormous applications in bioinfor…
On the Distortion Value of the Elections with Abstention
Mohammad Ghodsi, Mohamad Latifian, Masoud Seddighin
In Spatial Voting Theory, distortion is a measure of how good the winner is. It is proved that no deterministic voting mechanism can guarantee a distortion better than , even fo…
Fair Allocation of Indivisible Items With Externalities
Mohammad Ghodsi, Hamed Saleh, Masoud Seddighin
One of the important yet insufficiently studied subjects in fair allocation is the externality effect among agents. For a resource allocation problem, externalities imply that a bu…
Fair Allocation of Indivisible Goods to Asymmetric Agents
Alireza Farhadi, Mohammad Ghodsi, MohammadTaghi Hajiaghayi +5
We study fair allocation of indivisible goods to agents with unequal entitlements. Fair allocation has been the subject of many studies in both divisible and indivisible settings.…
Fair Allocation of Indivisible Goods: Improvement and Generalization
Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Masoud Seddighin +2
We study the problem of fair allocation for indivisible goods. We use the the maxmin share paradigm introduced by Budish as a measure for fairness. Procaccia and Wang (EC'14) were…
Approximate Minimum Diameter
Mohammad Ghodsi, Hamid Homapour, Masoud Seddighin
We study the minimum diameter problem for a set of inexact points. By inexact, we mean that the precise location of the points is not known. Instead, the location of each point is…