The $k$-center problem is to choose a subset of size $k$ from a set of $n$ points such that the maximum distance from each point to its nearest center is minimized. Let $Q=\{Q_1,\ldots,Q_n\}$ be a set of polygons or segments in the region-based uncertainty model, in which each $Q_i$ is an uncertain point, where the exact locations of the points in $Q_i$ are unknown. The geometric objects segments and polygons can be models of a point set. We define the uncertain version of the $k$-center problem as a generalization in which the objective is to find $k$ points from $Q$ to cover the remaining regions of $Q$ with minimum or maximum radius of the cluster to cover at least one or all exact instances of each $Q_i$, respectively. We modify the region-based model to allow multiple points to be chosen from a region and call the resulting model the aggregated uncertainty model. All these problems contain the point version as a special case, so they are all NP-hard with a lower bound 1.822. We give approximation algorithms for uncertain $k$-center of a set of segments and polygons. We also have implemented some of our algorithms on a data-set to show our theoretical performance guarantees can be achieved in practice. Comment: Accepted in Fundamenta Informaticae

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.

Edit distance is one of the most fundamental problems in combinatorial optimization to measure the similarity between strings. Ulam distance is a special case of edit distance where no character is allowed to appear more than once in a string. Recent developments have been very fruitful for obtaining fast and parallel algorithms for both edit distance and Ulam distance. In this work, we present an almost optimal MPC (massively parallel computation) algorithm for Ulam distance and improve MPC algorithms for edit distance. Our algorithm for Ulam distance is almost optimal in the sense that (1) the approximation factor of our algorithm is 1+ε1+ε, (2) the round complexity of our algorithm is constant, (3) the total memory of our algorithm is almost linear (~Oε(n)Õε(n)), and (4) the overall running time of our algorithm is almost linear which is the best known for Ulam distance. We also improve the work of Hajiaghayi et al. for edit distance in terms of total memory. The best previously known MPC algorithm for edit distance requires ~O(n2x)Õ(n2x) machines when the memory of each machine is bounded by ~O(n1-x)Õ(n1-x). In this work, we improve the number of machines to ~O(n(9/5)x)Õ(n(9/5)x) while keeping the memory limit intact. Moreover, the round complexity of our algorithm is constant and the total running time of our algorithm is truly subquadratic. However, our improvement comes at the expense of a constant factor in the approximation guarantee of the algorithm. This improvement is inspired by the recent techniques of Boroujeni et al. and Chakraborty et al. for obtaining truly subquadratic time algorithms for edit distance.

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 Kirchgä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.

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.

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 the share allocated to an agent may affect the utilities of other agents.

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.

Given a simple polygon P with n vertices, the visibility polygon (VP) of a point q, or a segment pq‾ 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 uw‾ 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 uw‾ visible to our viewer. We find out exactly which interval of uw‾ 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 uw‾ is mirror-visible through e.

We study the problem of fair allocation for indivisible goods. We use the maxmin share paradigm introduced by Budish~\citeBudish:first as a measure for fairness. \procacciafirst ~\citeProcaccia:first were the first to investigate this fundamental problem in the additive setting. They show that a maxmin guarantee (1-$\MMS$ allocation) is not always possible even when the number of agents is limited to 3. While the existence of an approximation solution (e.g. a $1/2$-$\MMS$ allocation) is quite straightforward, improving the guarantee becomes subtler for larger constants. \sprocacciafirst ~\citeProcaccia:first provide a proof for the existence of a $2/3$-$\MMS$ allocation and leave the question open for better guarantees. Our main contribution is an answer to the above question. We improve the result of \sprocacciafirst~to a $3/4$ factor in the additive setting. The main idea for our $3/4$-$\MMS$ allocation method is clustering the agents. To this end, we introduce three notions and techniques, namely reducibility, matching allocation, and cycle-envy-freeness, and prove the approximation guarantee of our algorithm via non-trivial applications of these techniques. Our analysis involves coloring and double counting arguments that might be of independent interest. One major shortcoming of the current studies on fair allocation is the additivity assumption on the valuations. We alleviate this by extending our results to the case of submodular, fractionally subadditive, and subadditive settings. More precisely, we give constant approximation guarantees for submodular and XOS agents, and a logarithmic approximation for the case of subadditive agents. 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 additive, submodular, and XOS settings in polynomial time. The reader can find a summary of our results in Table \refresultstable.

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(n1.858) quantum algorithm that approximates the edit distance within a factor of 7. We further extend this result to an O(n1.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.

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.

We study permutation betting markets, introduced by Chen, Fortnow, Nikolova, and Pennock [3]. For these markets, we consider subset bettings in which each trader can bet on a subset of candidates ending up in a subset of positions. We consider the revenue maximization problem for the auctioneer in two main frameworks: the risk-free revenue maximization (studied in [3]), and the probabilistic revenue maximization. We also explore the use of some certain knowledge or extra information about the possible outcomes of the market. We first show that finding the optimal revenue in the risk-free model for the subset betting problem is inapproximable. This resolves an open question posed by Chen et al. [3]. In order to identify solvable variants of the problem, we propose the singleton betting language which allows traders to bet an arbitrary value on one candidate for one position. For singleton bettings, we first provide a linear-time implementable necessary and sufficient condition for existence of a solution with positive revenue for any possible outcome. Furthermore, we develop an LP-based polynomial-time algorithm to find the optimum solution of this problem. In addition, we show how to extend this LP-based method to handle some extra information about the possible outcomes. Finally, we consider the revenue maximization problem in a probabilistic setting. For this variant, we observe that the problem of maximizing the expected revenue is polynomial-time solvable, but we show that maximizing the probability of achieving a pre-specified revenue is #P-Complete.

Given an undirected graph with weights associated with its edges, the Steiner tree problem consists of finding a minimum weight subtree spanning a given subset of (terminal) nodes of the original graph. Minimum Spanning Tree Heuristic (MSTH) is a heuristic for solving the Steiner problem in graphs. In this paper we first review existing algorithms for solving the Steiner problem in graphs. We then introduce a new parallel version of MSTH on three dimensional mesh of trees architecture. We describe our algorithm and analyze its time complexity. The time complexity analysis shows that the algorithm’s running time is O(lg2n) which is comparable with other existing parallel solutions.

This paper considers scheduling tasks while minimizing the power consumption of one or more processors, each of which can go to sleep at a fixed cost α. There are two natural versions of this problem, both considered extensively in recent work: minimize the total power consumption (including computation time), or minimize the number of gaps in execution. For both versions in a multiprocessor system, we develop a polynomial-time algorithm based on sophisticated dynamic programming. In a generalization of the power-saving problem, where each task can execute in any of a specified set of time intervals, we develop a (1 + 23 α)-approximation, and show that dependence on α is necessary. In contrast, the analogous multi-interval gap scheduling problem is set-cover hard (and thus not o(lg n)-approximable), even in the special cases of just two intervals per job or just three unit intervals per job. We also prove several other hardness-of-approximation results. Finally, we give an O(√n)-approximation for maximizing throughput given a hard upper bound on the number of gaps.

Modern search engines use link structure of the World Wide Web in order to gain better results for ranking the results of users' queries. One of the most popular ranking algorithms which is based on link analysis is HITS. It generates very accurate outputs but because of huge amount of online computations, this algorithm is relatively slow. In this paper we introduce PHITS, a parallelized version of the HITS algorithm that is suitable for working with huge web graphs in a reason- able time. For implementing this algorithm, we use WebGraph framework and we focus on parallelizing access to web graph as the main bottleneck in the HITS algorithm. I. INTRODUCTION Search technology is one of the most important reasons for success of the web. The huge amount of information available on the web, its high growth rate, and its unstructured nature, all increase the need for search engines with high performance and accurate results. One of the major components of each search engine is its ranking algorithm. Traditional Information Retrieval (IR) systems usually use some models like VMS (4) and compute rank of results using content similarity measures between user's query and retrieved documents. But in the context of the web, there are some problems with these approaches. For example, spamming may lead to inefficient ranking. Some methods have been proposed to encounter these problems most of which uses some implicit information which is embedded in the web graph. These methods are known as Link-Analysis based algorithms. PageRank (5) and HITS (Hyperlink Induced Topic Search) (1) are the most well known algorithms in this category. PageRank, which is used by Google for ranking its results, is an offline and query-independent ranking algorithm. This means that the ranking is independent of the specific queries of users and therefore can be done once and used for all of the upcoming queries. On the other hand, HITS is an online and query-dependent algorithm. Being query dependent makes HITS more precise but it has some disadvantages too. In fact, required online computations for this algorithm is too much and the response time of the search engine after submitting queries by users is not acceptable. To overcome this problem, in this paper we will exploit the parallel processing methods to improve the execution performance of the algorithm. The rest of this paper is organized as follows. In section II, link-analysis based algorithms in general and HITS as a special case are discussed. At the end of this section, some of the variations and improvements for the HITS algorithm that are suggested in the literature are also described. Implementing the HITS algorithm and its parallel version, PHITS, are discussed in sections III and IV respectively. Finally, last section of this paper contains conclusion and some ideas for future work in this topic.

Summary form only given. This work focuses on the problem of compressing the Web graph by means of eliminating some of the edges in its link structure. An algorithm is used to divide the task so that it can be executed on parallel processors. Ran on a test bed of generated Web graphs, the algorithm improved the compression ratio of both Huffman-coding schemes and Adler and Mitzenmacher's find reference algorithm tangibly. In the find reference case, improvement was up to 90%

In this paper, we consider the problem of computing the visibility of a query point inside polygons with holes. The goal is to perform this computation efficiently per query with more cost in the preprocessing phase. Our algorithm is based on solutions in [13] and [2] proposed for simple polygons. In our solution, the preprocessing is done in time O(n3 log(n)) to construct a data structure of size O(n3). It is then possible to report the visibility polygon of any query point q in time O((1+h′) log n+|V(q)|), in which n and h are the number of the vertices and holes of the polygon respectively, |V(q)| is the size of the visibility polygon of q, and h′ is an output and preprocessing sensitive parameter of at most min(h,|V(q)|). This is claimed to be the best query-time result on this problem so far.

Abstract The path‐matching problem is to find a set of vertex‐ or edge‐disjoint paths with length constraints in a given graph with a given set of endpoints. This problem has several applications in broadcasting and multicasting in computer networks. In this paper, we study the algorithmic complexity of different cases of this problem. In each case, we either provide a polynomial‐time algorithm or prove that the problem is NP‐complete. © 2002 Wiley Periodicals, Inc.