Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userErratum: Fast and Simple Horizontal Coordinate Assignment
96
0
0.0
(
0
)
Added by
Johannes Zink
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We point out two flaws in the algorithm of Brandes and Kopf (Proc. GD 2001), which is often used for the horizontal coordinate assignment in Sugiyamas framework for layered layouts. One of them has been noted and fixed multiple times, the other has not been documented before and requires a non-trivial adaptation. On the bright side, neither running time nor extensions of the algorithm are affected adversely.
rate research
Read More
We revisit the Subset Sum problem over the finite cyclic group $mathbb{Z}_m$ for some given integer $m$. A series of recent works has provided near-optimal algorithms for this problem under the Strong Exponential Time Hypothesis. Koiliaris and Xu (SODA17, TALG19) gave a deterministic algorithm running in time $tilde{O}(m^{5/4})$, which was later improved to $O(m log^7 m)$ randomized time by Axiotis et al. (SODA19). In this work, we present two simple algorithms for the Modular Subset Sum problem running in near-linear time in $m$, both efficiently implementing Bellmans iteration over $mathbb{Z}_m$. The first one is a randomized algorithm running in time $O(m log^2 m)$, that is based solely on rolling hash and an elementary data-structure for prefix sums; to illustrate its simplicity we provide a short and efficient implementation of the algorithm in Python. Our second solution is a deterministic algorithm running in time $O(m mathrm{polylog} m)$, that uses dynamic data structures for string manipulation. We further show that the techniques developed in this work can also lead to simple algorithms for the All Pairs Non-Decreasing Paths Problem (APNP) on undirected graphs, matching the near-optimal running time of $tilde{O}(n^2)$ provided in the recent work of Duan et al. (ICALP19).
In this paper, we develop a simple and fast online algorithm for solving a class of binary integer linear programs (LPs) arisen in general resource allocation problem. The algorithm requires only one single pass through the input data and is free of doing any matrix inversion. It can be viewed as both an approximate algorithm for solving binary integer LPs and a fast algorithm for solving online LP problems. The algorithm is inspired by an equivalent form of the dual problem of the relaxed LP and it essentially performs (one-pass) projected stochastic subgradient descent in the dual space. We analyze the algorithm in two different models, stochastic input and random permutation, with minimal technical assumptions on the input data. The algorithm achieves $Oleft(m sqrt{n}right)$ expected regret under the stochastic input model and $Oleft((m+log n)sqrt{n}right)$ expected regret under the random permutation model, and it achieves $O(m sqrt{n})$ expected constraint violation under both models, where $n$ is the number of decision variables and $m$ is the number of constraints. The algorithm enjoys the same performance guarantee when generalized to a multi-dimensional LP setting which covers a wider range of applications. In addition, we employ the notion of permutational Rademacher complexity and derive regret bounds for two earlier online LP algorithms for comparison. Both algorithms improve the regret bound with a factor of $sqrt{m}$ by paying more computational cost. Furthermore, we demonstrate how to convert the possibly infeasible solution to a feasible one through a randomized procedure. Numerical experiments illustrate the general applicability and effectiveness of the algorithms.
We consider the problem of transforming a set of elements into another by a sequence of elementary edit operations, namely substitutions, removals and insertions of elements. Each possible edit operation is penalized by a non-negative cost and the cost of a transformation is measured by summing the costs of its operations. A solution to this problem consists in defining a transformation having a minimal cost, among all possible transformations. To compute such a solution, the classical approach consists in representing removal and insertion operations by augmenting the two sets so that they get the same size. This allows to express the problem as a linear sum assignment problem (LSAP), which thus finds an optimal bijection (or permutation, perfect matching) between the two augmented sets. While the LSAP is known to be efficiently solvable in polynomial time complexity, for instance with the Hungarian algorithm, useless time and memory are spent to treat the elements which have been added to the initial sets. In this report, we show that the problem can be formalized as an extension of the LSAP which considers only one additional element in each set to represent removal and insertion operations. A solution to the problem is no longer represented as a bijection between the two augmented sets. We show that the considered problem is a binary linear program (BLP) very close to the LSAP. While it can be solved by any BLP solver, we propose an adaptation of the Hungarian algorithm which improves the time and memory complexities previously obtained by the approach based on the LSAP. The importance of the improvement increases as the size of the two sets and their absolute difference increase. Based on the analysis of the problem presented in this report, other classical algorithms can be adapted.
We study the assignment problem of objects to agents with heterogeneous preferences under distributional constraints. Each agent is associated with a publicly known type and has a private ordinal ranking over objects. We are interested in assigning as many agents as possible. Our first contribution is a generalization of the well-known and widely used serial dictatorship. Our mechanism maintains several desirable properties of serial dictatorship, including strategyproofness, Pareto efficiency, and computational tractability while satisfying the distributional constraints with a small error. We also propose a generalization of the probabilistic serial algorithm, which finds an ordinally efficient and envy-free assignment, and also satisfies the distributional constraints with a small error. We show, however, that no ordinally efficient and envy-free mechanism is also weakly strategyproof. Both of our algorithms assign at least the same number of students as the optimum fractional assignment.
Consider an online facility assignment problem where a set of facilities $F = { f_1, f_2, f_3, cdots, f_{|F|} }$ of equal capacity $l$ is situated on a metric space and customers arrive one by one in an online manner on that space. We assign a customer $c_i$ to a facility $f_j$ before a new customer $c_{i+1}$ arrives. The cost of this assignment is the distance between $c_i$ and $f_j$. The objective of this problem is to minimize the sum of all assignment costs. Recently Ahmed et al. (TCS, 806, pp. 455-467, 2020) studied the problem where the facilities are situated on a line and computed competitive ratio of Algorithm Greedy which assigns the customer to the nearest available facility. They computed competitive ratio of algorithm named Algorithm Optimal-Fill which assigns the new customer considering optimal assignment of all previous customers. They also studied the problem where the facilities are situated on a connected unweighted graph. In this paper we first consider that $F$ is situated on the vertices of a connected unweighted grid graph $G$ of size $r times c$ and customers arrive one by one having positions on the vertices of $G$. We show that Algorithm Greedy has competitive ratio $r times c + r + c$ and Algorithm Optimal-Fill has competitive ratio $O(r times c)$. We later show that the competitive ratio of Algorithm Optimal-Fill is $2|F|$ for any arbitrary graph. Our bound is tight and better than the previous result. We also consider the facilities are distributed arbitrarily on a plane and provide an algorithm for the scenario. We also provide an algorithm that has competitive ratio $(2n-1)$. Finally, we consider a straight line metric space and show that no algorithm for the online facility assignment problem has competitive ratio less than $9.001$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
