Author name cluster

Mohammad Ghodsi

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

18 papers

2 author rows

TCS Journal 2025 Journal Article

Visibility extension via reflection

Arash Vaezi
Bodhayan Roy
Mohammad Ghodsi

This paper studies a variant of the Art Gallery problem in which the “walls” can be replaced by reflecting edges, which allows the guards to see further and thereby see a larger portion of the gallery. Given a simple polygon P, first, we consider one guard as a point viewer, and we intend to use reflection to add a certain amount of area to the visibility polygon of the guard. We study visibility with specular and diffuse reflections where the specular type of reflection is the mirror-like reflection, and in the diffuse type of reflection, the angle between the incident and reflected ray may assume all possible values between 0 and π. Lee and Aggarwal already proved that several versions of the general Art Gallery problem are NP -hard. We show that several cases of adding an area to the visible area of a given point guard are NP -hard, too. Second, 1 we assume that all edges are reflectors, and we intend to decrease the minimum number of guards required to cover the whole gallery. Chao Xu proved that even considering r specular reflections, one may need ⌊ n 3 ⌋ guards to cover the polygon, let r be the maximum number of reflections of a guard's visibility ray. In this work, we prove that considering r diffuse reflections, the minimum number of vertex or boundary guards required to cover a given simple polygon P decreases to ⌈ α 1 + ⌊ r 8 ⌋ ⌉, where α indicates the minimum number of guards required to cover the polygon without reflection. We also generalize the O ( log ⁡ n ) -approximation ratio algorithm of the vertex guarding problem to work in the presence of reflection.

Details DOI

AIJ Journal 2022 Journal Article

Fair allocation of indivisible goods: Beyond additive valuations

Mohammad Ghodsi
MohammadTaghi Hajiaghayi
Masoud Seddighin
Saeed Seddighin
Hadi Yami

We conduct a study on the problem of fair allocation of indivisible goods when maximin share [1] is used as the measure of fairness. Most of the current studies on this notion are limited to the case that the valuations are additive. In this paper, we go beyond additive valuations and consider the cases that the valuations are submodular, fractionally subadditive, and subadditive. We give constant approximation guarantees for agents with submodular and XOS valuations, and a logarithmic bound for the case of agents with subadditive valuations. Furthermore, we complement our results by providing close upper bounds for each class of valuation functions. Finally, we present algorithms to find such allocations for submodular and XOS settings in polynomial time.

Details DOI

JAIR Journal 2021 Journal Article

On the Distortion Value of Elections with Abstention

Masoud Seddighin
Mohammad Latifian
Mohammad Ghodsi

In Spatial Voting Theory, distortion is a measure of how good the winner is. It has been proved that no deterministic voting mechanism can guarantee a distortion better than 3, even for simple metrics such as a line. In this study, we wish to answer the following question: how does the distortion value change if we allow less motivated agents to abstain from the election? We consider an election with two candidates and suggest an abstention model, which is a general form of the abstention model proposed by Kirchgässner. Our results characterize the distortion ¨ value and provide a rather complete picture of the model.

PDF Details DOI

TCS Journal 2020 Journal Article

Clearing an orthogonal polygon to find the evaders

Salma Sadat Mahdavi
Mohammad Ghodsi

In a multi-robot system, a number of autonomous robots would sense, communicate, and decide to move within a given domain to achieve a common goal. In the pursuit-evasion problem, a polygonal region is given and a robot called a pursuer tries to find some mobile targets called evaders. The goal of this problem is to design a motion strategy for the pursuer such that it can detect all the evaders. In this paper, we consider a new variant of the pursuit-evasion problem in which the robots (pursuers) each moves back and forth along an orthogonal line segment inside a simple orthogonal polygon P. We assume that P includes unpredictable, moving evaders that have bounded speed. We propose the first motion-planning algorithm for a group of robots, assuming that they move along the pre-located line segments with a constant speed to detect all the evaders with bounded speed. Also, we prove an upper bound for the length of the paths that all pursuers move in the proposed algorithm.

Details DOI

TCS Journal 2020 Journal Article

Covering orthogonal polygons with sliding k-transmitters

Salma Sadat Mahdavi
Saeed Seddighin
Mohammad Ghodsi

In this paper, we consider a new variant of covering in an orthogonal art gallery problem where each guard is a sliding k-transmitter. Such a guard can travel back and forth along an orthogonal line segment, say s, inside the polygon. A point p is covered by this guard if there exists a point q ∈ s such that p q ‾ is a line segment normal to s, and has at most k intersections with the boundary walls of the polygon. The objective is to minimize the sum of the lengths of the sliding k-transmitters to cover the entire polygon. In other words, the goal is to find the minimum total length of trajectories on which the guards can travel to cover the entire polygon. We prove that this problem is NP-hard when k = 2, and present a 2-approximation algorithm for any fixed k ≥ 2. The proposed algorithm also works well for an orthogonal polygon where the edges have thickness.

Details DOI

STOC Conference 2019 Conference Paper

1+ ε approximation of tree edit distance in quadratic time

Mahdi Boroujeni
Mohammad Ghodsi
MohammadTaghi Hajiaghayi
Saeed Seddighin

Edit distance is one of the most fundamental problems in computer science. Tree edit distance is a natural generalization of edit distance to ordered rooted trees. Such a generalization extends the applications of edit distance to areas such as computational biology, structured data analysis (e.g., XML), image analysis, and compiler optimization. Perhaps the most notable application of tree edit distance is in the analysis of RNA molecules in computational biology where the secondary structure of RNA is typically represented as a rooted tree. The best-known solution for tree edit distance runs in cubic time. Recently, Bringmann et al. show that an O ( n 2.99 ) algorithm for weighted tree edit distance is unlikely by proving a conditional lower bound on the computational complexity of tree edit distance. This shows a substantial gap between the computational complexity of tree edit distance and that of edit distance for which a simple dynamic program solves the problem in quadratic time. In this work, we give the first non-trivial approximation algorithms for tree edit distance. Our main result is a quadratic time approximation scheme for tree edit distance that approximates the solution within a factor of 1+є for any constant є > 0.

Details

JAIR Journal 2019 Journal Article

Fair Allocation of Indivisible Goods to Asymmetric Agents

Alireza Farhadi
Mohammad Ghodsi
Mohammad Taghi Hajiaghayi
Sébastien Lahaie
David Pennock
Masoud Seddighin
Saeed Seddighin
Hadi Yami

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. Our emphasis is on the case where the goods are indivisible and agents have unequal entitlements. This problem is a generalization of the work by Procaccia and Wang (2014) wherein the agents are assumed to be symmetric with respect to their entitlements. Although Procaccia and Wang show an almost fair (constant approximation) allocation exists in their setting, our main result is in sharp contrast to their observation. We show that, in some cases with n agents, no allocation can guarantee better than 1/n approximation of a fair allocation when the entitlements are not necessarily equal. Furthermore, we devise a simple algorithm that ensures a 1/n approximation guarantee. Our second result is for a restricted version of the problem where the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. Although this assumption might seem without loss of generality, we show it enables us to find a 1/2 approximation fair allocation via a greedy algorithm. Finally, we run some experiments on real-world data and show that, in practice, a fair allocation is likely to exist. We also support our experiments by showing positive results for two stochastic variants of the problem, namely stochastic agents and stochastic items.

PDF Details DOI

AAAI Conference 2019 Conference Paper

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 3, even for simple metrics such as a line. In this study, we wish to answer the following question: how does the distortion value change if we allow less motivated agents to abstain from the election? We consider an election with two candidates and suggest an abstention model, which is a more general form of the abstention model proposed by Kirchgässner (2003). We define the concepts of the expected winner and the expected distortion to evaluate the distortion of an election in our model. Our results fully characterize the distortion value and provide a rather complete picture of the model.

PDF Details

TCS Journal 2019 Journal Article

Visibility extension via mirror-edges to cover invisible segments

Arash Vaezi
Mohammad Ghodsi

Given a simple polygon P with n vertices, the visibility polygon ( VP ) of a point q, or a segment p q ‾ inside P can be computed in linear time. We propose a linear time algorithm to extend the VP of a viewer (point or segment), by converting some edges of P into mirrors, such that a given non-visible segment u w ‾ can also be seen from the viewer. Various definitions for the visibility of a segment, such as weak, strong, or complete visibility are considered. Our algorithm finds every edge that, when converted to a mirror, makes u w ‾ visible to our viewer. We find out exactly which interval of u w ‾ becomes visible, by every edge middling as a mirror, all in linear time. In other words, in this article, we present an algorithm that, in linear time, for every edge e of P reveals precisely which part of u w ‾ is mirror-visible through e.

Details DOI

TCS Journal 2019 Journal Article

Visibility testing and counting for uncertain segments

Mohammad Ali Abam
Sharareh Alipour
Mohammad Ghodsi
Mohammad Mahdian

We study two well-known planar visibility problems, namely visibility testing and visibility counting, in a model where there is uncertainty about the input data. The standard versions of these problems are defined as follows: we are given a set S of n segments in R 2, and we would like to preprocess S so that we can quickly answer queries of the form: is the given query segment s ∈ S visible from the given query point q ∈ R 2 (for visibility testing) and how many segments in S are visible from the given query point q ∈ R 2 (for visibility counting). In our model of uncertainty, each segment may or may not exist, and if it does, it is located in one of finitely many possible locations, given by a discrete probability distribution. In this setting, the probabilistic visibility testing problem (PVTP, for short) is to compute the probability that a given segment s ∈ S is visible from a given query point q and the probabilistic visibility counting problem (PVCP, for short) is to compute the expected number of segments in S that are visible from a query point q. We first show that PVTP is #P-complete. In the special case where uncertainty is only about whether segments exist and not about their location, we show that PVTP is solvable in O ( n log ⁡ n ) time. Our algorithm for PVTP combined with linearity of expectation gives an O ( n 2 log ⁡ n ) time algorithm for PVCP. Using the algorithm for PVTP, together with a few old tricks, we can show that one can preprocess S in O ( n 5 log ⁡ n ) time into a data structure of size O ( n 4 ), so that each PVTP query for a fixed segment s can be answered in O ( log ⁡ n ) time. We also give a faster 2-approximation algorithm for this problem. At the end, we improve the approximation factor of the algorithm.

Details DOI

SODA Conference 2018 Conference Paper

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

Mahdi Boroujeni
Soheil Ehsani
Mohammad Ghodsi
MohammadTaghi Hajiaghayi
Saeed Seddighin

The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is “one of the biggest unsolved problems in the field of combinatorial pattern matching” [21]. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an O ( n 1. 858 ) quantum algorithm that approximates the edit distance within a factor of 7. We further extend this result to an O ( n 1. 781 ) quantum algorithm that approximates the edit distance within a larger constant factor. Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to metric estimation and provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of 3, with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.

Details

TCS Journal 2018 Journal Article

Randomized approximation algorithms for planar visibility counting problem

Sharareh Alipour
Mohammad Ghodsi
Amir Jafari

Given a set S of n disjoint line segments in R 2, the visibility counting problem (VCP) is to preprocess S such that the number of segments in S visible from any query point p can be computed quickly. This problem can be solved trivially in O ( log ⁡ n ) query time using O ( n 4 log ⁡ n ) preprocessing time and O ( n 4 ) space. Gudmundsson and Morin (2010) [10] proposed a 2-approximation algorithm for this problem with a tradeoff between the space and the query time. For any constant 0 ≤ α ≤ 1, their algorithm answers any query in O ϵ ( m ( 1 − α ) / 2 ) time with O ϵ ( m 1 + α ) of preprocessing time and space, where ϵ > 0 is a constant that can be made arbitrarily small and O ϵ ( f ( n ) ) = O ( f ( n ) n ϵ ) and m = O ( n 2 ) is a number that depends on the configuration of the segments. In this paper, we propose two randomized approximation algorithms for VCP. The first algorithm depends on two constants 0 ≤ β ≤ 2 3 and 0 < δ ≤ 1, and the expected preprocessing time, the expected space, and the expected query time are O ( m 2 − 3 β / 2 log ⁡ m ), O ( m 2 − 3 β / 2 ), and O ( 1 δ 2 m β / 2 log ⁡ m ), respectively. The algorithm, in the preprocessing phase, selects a sequence of random samples, whose size and number depend on the tradeoff parameters. When a query point p is given by an adversary unaware of the random sample of our algorithm, it computes the number of visible segments from p, denoted by m p, exactly, if m p ≤ 3 δ 2 m β / 2 log ⁡ ( 2 m ). Otherwise, it computes an approximated value, m p ′, such that with the probability of at least 1 − 1 m, we have ( 1 − δ ) m p ≤ m p ′ ≤ ( 2 + 2 δ ) m p. The preprocessing time and space of the second algorithm are O ( n 2 log ⁡ n ) and O ( n 2 ), respectively. This algorithm computes the exact value of m p if m p ≤ 1 δ 2 n log ⁡ n, otherwise it returns an approximated value m p ″ in expected O ( 1 δ 2 n log ⁡ n ) time, such that with the probability at least 1 − 1 log ⁡ n, we have ( 1 − 3 δ ) m p ≤ m p ″ ≤ ( 1. 5 + 3 δ ) m p.

Details DOI

AAAI Conference 2017 Conference Paper

Envy-Free Mechanisms with Minimum Number of Cuts

Reza Alijani
Majid Farhadi
Mohammad Ghodsi
Masoud Seddighin
Ahmad Tajik

We study the problem of fair division of a heterogeneous resource among strategic players. Given a divisible heterogeneous cake, we wish to divide the cake among n players in a way that meets the following criteria: (I) every player (weakly) prefers his allocated cake to any other player’s share (such notion is known as envy-freeness), (II) the mechanism is strategy-proof (truthful), and (III) the number of cuts made on the cake is minimal. We provide methods, namely expansion process and expansion process with unlocking, for dividing the cake under different assumptions on the valuation functions of the players.

PDF Details

AAMAS Conference 2017 Conference Paper

Fair Allocation of Indivisible Goods with Different Entitlements

Alireza Farhadi
MohammadTaghi Hajiaghayi
Mohammad Ghodsi
Sebastien Lahaie
David Pennock
Masoud Seddighin
Saeed Seddighin
Hadi Yami

We study fair allocation of indivisible goods to agents with unequal entitlements. Our emphasis is on the case where the goods are indivisible and agents have unequal entitlements. This problem is a generalization of the work by Procaccia and Wang [14] wherein the agents are assumed to be symmetric. We show that, in some cases with n agents, no allocation can guarantee better than 1/n approximation of a fair allocation when the entitlements are not necessarily equal. Furthermore, we devise a simple algorithm that ensures a 1/n approximation guarantee. Next, we assume that the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. We show it enables us to find a 1/2 approximation fair allocation via a greedy algorithm. Finally, we run some experiments on real-world data and show that, in practice, a fair allocation is likely to exist. We also support our experiments by showing positive results for two stochastic variants of the problem, namely stochastic agents and stochastic items. (The full version of the paper is available in https: //arxiv. org/abs/1703. 01649.) CCS Concepts •Computing methodologies → Multi-agent systems;

PDF

TCS Journal 2014 Journal Article

On non-progressive spread of influence through social networks

MohammadAmin Fazli
Mohammad Ghodsi
Jafar Habibi
Pooya Jalaly
Vahab Mirrokni
Sina Sadeghian

The spread of influence in social networks is studied in two main categories: progressive models and non-progressive models (see, e. g. , the seminal work of Kempe et al. [8]). While the progressive models are suitable for modeling the spread of influence in monopolistic settings, non-progressive models are more appropriate for non-monopolistic settings, e. g. , modeling diffusion of two competing technologies over a social network. Despite the extensive work on progressive models, non-progressive models have not been considered as much. In this paper, we study the spread of influence in the non-progressive model under the strict majority threshold: given a graph G with a set of initially infected nodes, each of which gets infected at time τ iff a majority of its neighbors are infected at time τ − 1. Our goal in the MinPTS problem is to find a minimum-cardinality initial set of infected nodes that would eventually converge to the steady state where all nodes of G are infected. We prove that while the MinPTS problem is NP-complete for a restricted family of graphs, it admits a constant-factor approximation algorithm for power-law graphs. We do so by proving the lower and upper bounds on the optimal solution of the MinPTS problem in terms of the minimum and maximum degrees of nodes in the graph. The upper bound is achieved in turn by applying a natural greedy algorithm. Our experimental evaluation of the greedy algorithm also shows its superior performance compared to other algorithms for a set of real-world graphs as well as the random power-law graphs. Finally, we study the convergence properties of these algorithms and show that the non-progressive model converges in at most O ( | E ( G ) | ) steps.

Details DOI

TCS Journal 2013 Journal Article

Equilibrium pricing with positive externalities

Nima AhmadiPourAnari
Shayan Ehsani
Mohammad Ghodsi
Nima Haghpanah
Nicole Immorlica
Hamid Mahini
Vahab Mirrokni

We study the problem of selling an item to strategic buyers in the presence of positive historical externalities, where the value of a product increases as more people buy and use it. This increase in the value of the product is the result of resolving bugs or security holes after more usage. We consider a continuum of buyers that are partitioned into types where each type has a valuation function based on the actions of other buyers. Given a fixed sequence of prices, or price trajectory, buyers choose a day on which to purchase the product, i. e. they have to decide whether to purchase the product early in the game or later after more people already own it. We model this strategic setting as a game, study existence and uniqueness of the equilibria, and design an FPTAS to compute an approximately revenue-maximizing pricing trajectory for the seller in two special cases: the symmetric settings in which there is just a single buyer type, and the linear settings that are characterized by an initial type-independent bias and a linear type-dependent influenceability coefficient.

Details DOI

TCS Journal 2007 Journal Article

Query-point visibility constrained shortest paths in simple polygons

Ramtin Khosravi
Mohammad Ghodsi

In this paper, we study the problem of finding the shortest path between two points inside a simple polygon such that there is at least one point on the path from which a query point is visible. We provide an algorithm which preprocesses the input in O ( n 2 + n K ) time and space and provides logarithmic query time. The input polygon has n vertices and K is a parameter dependent on the input polygon which is O ( n 2 ) in the worst case but is much smaller for most polygons. The preprocessing algorithm sweeps an angular interval around every reflex vertex of the polygon to store the optimal contact points between the shortest paths and the windows separating the visibility polygons of the query points from the source and the destination.

Details DOI

TCS Journal 2006 Journal Article

Label updating to avoid point-shaped obstacles in fixed model

Farshad Rostamabadi
Mohammad Ghodsi

In this paper, we present efficient algorithms for updating the labeling of a set of n points after the presence of a random obstacle that appears on the map repeatedly. We update the labeling so that the given obstacle does not appear in any of the labels, the new labeling is valid, and the labels are as large as possible (called the optimal labeling). Each point is assumed to have an axis-parallel, square-shaped label of unit size, attached exclusively to that point in the middle of one of its edges. We consider two models: (1) the 2PM model, where each label is attached to its feature only on the middle of one of its horizontal edges, and (2) the r4PM model, where each label is attached to its feature on the middle of either one of its horizontal or vertical edges (known in advance). We assume that a sequence of point-shaped obstacles appear on the map on random locations. Three settings are considered for the behavior of the obstacle: (1) the obstacle is removed afterwards, (2) it remains on the map, and (3) it receives a similar label and remains on the map. Only two operations are permitted on the labels: flipping one or more labels, and/or resizing all labels. In the first setting, we suggest a data structure of O ( n ) space and O ( n lg n ) time in the 2PM model, and of O ( n 2 ) time in the r4PM model, so that the updated labeling can be constructed for any obstacle position in O ( lg n + k ) time, where k is the minimum number of operations needed. For the second and third problems, we suggest an O ( n ) space and O ( n lg n ) time data structure that can place each obstacle (possibly with a label) on the map in O ( lg n + k ) time, if k label flips are sufficient to make room to place the new obstacle. Otherwise, two O ( n ) time algorithms are suggested when a relabeling of all points is required.

Details DOI