Giulio Cerbai, Anders Claesson, Luca Ferrari
2019-07-18
The (classical) problem of characterizing and enumerating permutations that can be sorted using two stacks connected in series is still largely open. In the present paper we address a related problem, in which we impose restrictions both on the procedure and on the stacks. More precisely, we consider a greedy algorithm where we perform the rightmost legal operation (here "rightmost" refers to the usual representation of stack sorting problems). Moreover, the first stack is required to be
-avoiding, for some permutation , meaning that, at each step, the elements maintained in the stack avoid the pattern when read from top to bottom. Since the set of permutations which can be sorted by such a device (which we call -machine) is not always a class, it would be interesting to understand when it happens. We will prove that the set of -machines whose associated sortable permutations are not a class is counted by Catalan numbers. Moreover, we will analyze two specific -machines in full details (namely when and ), providing for each of them a complete characterization and enumeration of sortable permutations.
Felix Happach
2019-07-18
We consider a variant of the NP-hard problem of assigning jobs to machines to minimize the completion time of the last job. Usually, precedence constraints are given by a partial order on the set of jobs, and each job requires all its predecessors to be completed before it can start. In his seminal paper, Graham (1966) presented a simple 2-approximation algorithm, and, more than 40 years later, Svensson (2010) proved that 2 is essentially the best approximation ratio one can hope for in general. In this paper, we consider a different type of precedence relation that has not been discussed as extensively and is called OR-precedence. In order for a job to start, we require that at least one of its predecessors is completed - in contrast to all its predecessors. Additionally, we assume that each job has a release date before which it must not start. We prove that Graham's algorithm has an approximation guarantee of 2 also in this setting, and present a polynomial-time algorithm that solves the problem to optimality, if preemptions are allowed. The latter result is in contrast to classical precedence constraints, for which Ullman (1975) showed that the preemptive variant is already NP-hard. Our algorithm generalizes a result of Johannes (2005) who gave a polynomial-time algorithm for unit processing time jobs subject to OR-precedence constraints, but without release dates. The performance guarantees presented here match the best-known ones for special cases where classical precedence constraints and OR-precedence constraints coincide.
Édouard Bonnet, Nidhi Purohit
2019-07-18
A resolving set
of a graph is a subset of its vertices such that no two vertices of have the same distance vector to . The Metric Dimension problem asks for a resolving set of minimum size, and in its decision form, a resolving set of size at most some specified integer. This problem is NP-complete, and remains so in very restricted classes of graphs. It is also W[2]-complete with respect to the size of the solution. Metric Dimension has proven elusive on graphs of bounded treewidth. On the algorithmic side, a polytime algorithm is known for trees, and even for outerplanar graphs, but the general case of treewidth at most two is open. On the complexity side, no parameterized hardness is known. This has led several papers on the topic to ask for the parameterized complexity of Metric Dimension with respect to treewidth. We provide a first answer to the question. We show that Metric Dimension parameterized by the treewidth of the input graph is W[1]-hard. More refinedly we prove that, unless the Exponential Time Hypothesis fails, there is no algorithm solving Metric Dimension in time on -vertex graphs of constant degree, with the pathwidth of the input graph, and any computable function. This is in stark contrast with an FPT algorithm of Belmonte et al. [SIAM J. Discrete Math. '17] with respect to the combined parameter , where is the tree-length and the maximum-degree of the input graph.
Nikhil Bansal
2018-11-05
We give a general method for rounding linear programs that combines the commonly used iterated rounding and randomized rounding techniques. In particular, we show that whenever iterated rounding can be applied to a problem with some slack, there is a randomized procedure that returns an integral solution that satisfies the guarantees of iterated rounding and also has concentration properties. We use this to give new results for several classic problems where iterated rounding has been useful.
Jan van den Brand, Thatchaphol Saranurak
2019-07-18
In the sensitive distance oracle problem, there are three phases. We first preprocess a given directed graph
with nodes and integer weights from . Second, given a single batch of edge insertions and deletions, we update the data structure. Third, given a query pair of nodes , return the distance from to . In the easier problem called sensitive reachability oracle problem, we only ask if there exists a directed path from to . Our first result is a sensitive distance oracle with preprocessing time, update time, and query time where the parameter can be chosen. The data-structure requires bits of memory. This is the first algorithm that can handle updates. Previous results (e.g. [Demetrescu et al. SICOMP'08; Bernstein and Karger SODA'08 and FOCS'09; Duan and Pettie SODA'09; Grandoni and Williams FOCS'12]) can handle at most 2 updates. When , the only non-trivial algorithm was by [Weimann and Yuster FOCS'10]. When , our algorithm simultaneously improves their preprocessing time, update time, and query time. In particular, when , their update and query time is , while our update and query time are truly subquadratic in , i.e., ours is faster by a polynomial factor of . To highlight the technique, ours is the first graph algorithm that exploits the kernel basis decomposition of polynomial matrices by [Jeannerod and Villard J.Comp'05; Zhou, Labahn and Storjohann J.Comp'15] developed in the symbolic computation community. [...]
Václav Blažej, Jan Matyáš Křišťan, Tomáš Valla
2019-07-18
Given a graph
, guards are placed on vertices of . Then vertices are subject to an infinite sequence of attacks so that each attack must be defended by a guard moving from a neighboring vertex. The m-eternal domination number is the minimum number of guards such that the graph can be defended indefinitely. In this paper we study the m-eternal domination number of cactus graphs, that is, connected graphs where each edge lies in at most two cycles, and we consider three variants of the m-eternal domination number: first variant allows multiple guards to occupy a single vertex, second variant does not allow it, and in the third variant additional "eviction" attacks must be defended. We provide a new upper bound for the m-eternal domination number of cactus graphs, and for a subclass of cactus graphs called Christmas cactus graphs, where each vertex lies in at most two cycles, we prove that these three numbers are equal. Moreover, we present a linear-time algorithm for computing them.
Andrej Brodnik, Aleksander Malnič, Rok Požar
2019-07-18
Given a finite sequence
of permutations in the symmetric group , and a permutation word over the alphabet , computation of the product in a straightforward manner takes time. However, it appears that this multiplication is such an elementary operation that, surprisingly enough, it went on unquestioned. We show that the above product can be computed in time using space, where . Consequently, this computation takes time whenever , which is a reasonable assumption in practice. The above result is used to solve the transitive simultaneous conjugacy problem in time and space, where . This problem asks whether there exists a permutation such that holds for all , where and are given sequences of permutations in , each of which generates a transitive subgroup of . As from mid 70' it has been know that the problem can be solved in time. An algorithm with running time , proposed in late 80', does not work correctly on all input data.
Suneel Sarswat, Abhishek Kr Singh
2019-07-18
We introduce a formal framework for analyzing trades in financial markets. An exchange is where multiple buyers and sellers participate to trade. These days, all big exchanges use computer algorithms that implement double sided auctions to match buy and sell requests and these algorithms must abide by certain regulatory guidelines. For example, market regulators enforce that a matching produced by exchanges should be \emph{fair}, \emph{uniform} and \emph{individual rational}. To verify these properties of trades, we first formally define these notions in a theorem prover and then give formal proofs of relevant results on matchings. Finally, we use this framework to verify properties of two important classes of double sided auctions. All the definitions and results presented in this paper are completely formalised in the Coq proof assistant without adding any additional axioms to it.
Vedat Levi Alev, Fernando Granha Jeronimo, Madhur Tulsiani
2019-07-18
We consider the problem of approximately solving constraint satisfaction problems with arity
( -CSPs) on instances satisfying certain expansion properties, when viewed as hypergraphs. Random instances of -CSPs, which are also highly expanding, are well-known to be hard to approximate using known algorithmic techniques (and are widely believed to be hard to approximate in polynomial time). However, we show that this is not necessarily the case for instances where the hypergraph is a high-dimensional expander. We consider the spectral definition of high-dimensional expansion used by Dinur and Kaufman [FOCS 2017] to construct certain primitives related to PCPs. They measure the expansion in terms of a parameter which is the analogue of the second singular value for expanding graphs. Extending the results by Barak, Raghavendra and Steurer [FOCS 2011] for 2-CSPs, we show that if an instance of MAX k-CSP over alphabet is a high-dimensional expander with parameter , then it is possible to approximate the maximum fraction of satisfiable constraints up to an additive error using levels of the sum-of-squares SDP hierarchy, provided . Based on our analysis, we also suggest a notion of threshold-rank for hypergraphs, which can be used to extend the results for approximating 2-CSPs on low threshold-rank graphs. We show that if an instance of MAX k-CSP has threshold rank for a threshold , then it is possible to approximately solve the instance up to additive error , using levels of the sum-of-squares hierarchy. As in the case of graphs, high-dimensional expanders (with sufficiently small ) have threshold rank 1 according to our definition.
Niels Möller
2019-07-17
The family of left-to-right GCD algorithms reduces input numbers by repeatedly subtracting the smaller number, or multiple of the smaller number, from the larger number. This paper describes how to extend any such algorithm to compute the Jacobi symbol, using a single table lookup per reduction. For both quadratic time GCD algorithms (Euclid, Lehmer) and subquadratic algorithms (Knuth, Sch"onhage, M"oller), the additional cost is linear, roughly one table lookup per quotient in the quotient sequence. This method was used for the 2010 rewrite of the Jacobi symbol computation in GMP.
