Maximum thick paths in static and dynamic environments

We consider the problem of finding a large number of disjoint paths for unit disks moving amidst static or dynamic obstacles. The problem is motivated by the capacity estimation problem in air traffic management, in which one must determine how many aircraft can safely move through a domain while avoiding each other and avoiding “no-fly zones” and predicted weather hazards. For the static case we give efficient exact algorithms, based on adapting the “continuous uppermost path” paradigm. As a by-product, we establish a continuous analogue of Menger's Theorem.Next we study the dynamic problem in which the obstacles may move, appear and disappear, and otherwise change with time in a known manner; in addition, the disks are required to enter/exit the domain during prescribed time intervals. Deciding the existence of just one path, even for a 0-radius disk, moving with bounded speed is NP-hard, as shown by Canny and Reif [J. Canny, J.H. Reif, New lower bound techniques for robot motion planning problems, in: Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci., 1987, pp. 49–60]. Moreover, we observe that determining the existence of a given number of paths is hard even if the obstacles are static, and only the entry/exit time intervals are specified for the disks. This motivates studying “dual” approximations, compromising on the radius of the disks and on the maximum speed of motion.Our main result is a pseudopolynomial-time dual-approximation algorithm. If K unit disks, each moving with speed at most 1, can be routed through an environment, our algorithm finds (at least) K paths for disks of radius somewhat smaller than 1 moving with speed somewhat larger than 1.     

Exploiting structure in quantified formulas

We study the computational problem “find the value of the quantified formula obtained by quantifying the variables in a sum of terms.” The “sum” can be based on any commutative monoid, the “quantifiers” need only satisfy two simple conditions, and the variables can have any finite domain. This problem is a generalization of the problem “given a sum-of-products of terms, find the value of the sum” studied in [R.E. Stearns and H.B. Hunt III, SIAM J. Comput. 25 (1996) 448–476]. A data structure called a “structure tree” is defined which displays information about “subproblems” that can be solved independently during the process of evaluating the formula. Some formulas have “good” structure trees which enable certain generic algorithms to evaluate the formulas in significantly less time than by brute force evaluation. By “generic algorithm,” we mean an algorithm constructed from uninterpreted function symbols, quantifier symbols, and monoid operations. The algebraic nature of the model facilitates a formal treatment of “local reductions” based on the “local replacement” of terms. Such local reductions “preserve formula structure” in the sense that structure trees with nice properties transform into structure trees with similar properties. These local reductions can also be used to transform hierarchical specified problems with useful structure into hierarchically specified problems having similar structure.     

A graph search algorithm for indoor pursuit/evasion

Using concepts from both robotics and graph theory, we formulate the problem of indoor pursuit/evasion in terms of searching the nodes of a graph for a mobile evader. We present the IGNS (Iterative Greedy Node Search) algorithm, which performs offline guaranteed search (i.e. no matter how the evader moves, it will eventually be captured). Furthermore, the algorithm produces an internal search (the searchers move only along the edges of the graph; “teleporting” is not used) and exploits non-monotonicity, extended visibility and finite evader speed to reduce the number of searchers required to clear an environment. We present search experiments for several indoor environments, in all of which the algorithm succeeds in clearing the graph (i.e. capturing the evader).     

Ahlfors-régularité des quasi-minima de Mumford–Shah

Let be an open set. We consider on Ω the competitors (U,K) for the reduced Mumford–Shah functional, that is to say the Mumford–Shah functional in which the -norm of U term is removed, where K is a closed subset of Ω and U is a function on ΩK with gradient in  . The main result of this paper is the following: there exists a constant c for which, whenever (U,K) is a quasi-minimizer for the reduced Mumford–Shah functional and B(x,r) is a ball centered on K and contained in Ω with bounded radius, the -measure of is bounded above by cr^N−1 and bounded below by c⁻¹r^N−1.     

Tree decompositions of graphs: Saving memory in dynamic programming

We propose a simple and effective heuristic to save memory in dynamic programming on tree decompositions when solving graph optimization problems. The introduced “anchor technique” is based on a tree-like set covering problem. We substantiate our findings by experimental results. Our strategy has negligible computational overhead concerning running time but achieves memory savings for nice tree decompositions and path decompositions between 60% and 98%.     

Improved approximation of Max-Cut on graphs of bounded degree

Let α0.87856 denote the best approximation ratio currently known for the Max-Cut problem on general graphs. We consider a semidefinite relaxation of the Max-Cut problem, round it using the random hyperplane rounding technique of Goemans and Williamson [J. ACM 42 (1995) 1115–1145], and then add a local improvement step. We show that for graphs of degree at most Δ, our algorithm achieves an approximation ratio of at least α+ε, where ε>0 is a constant that depends only on Δ. Using computer assisted analysis, we show that for graphs of maximal degree 3 our algorithm obtains an approximation ratio of at least 0.921, and for 3-regular graphs the approximation ratio is at least 0.924. We note that for the semidefinite relaxation of Max-Cut used by Goemans and Williamson the integrality gap is at least 1/0.885, even for 2-regular graphs.     

Claw-free graphs. III. Circular interval graphs

Construct a graph as follows. Take a circle, and a collection of intervals from it, no three of which have union the entire circle; take a finite set of points V from the circle; and make a graph with vertex set V in which two vertices are adjacent if they both belong to one of the intervals. Such graphs are “long circular interval graphs,” and they form an important subclass of the class of all claw-free graphs. In this paper we characterize them by excluded induced subgraphs. This is a step towards the main goal of this series, to find a structural characterization of all claw-free graphs.This paper also gives an analysis of the connected claw-free graphs G with a clique the deletion of which disconnects G into two parts both with at least two vertices.     

Orthogonal Rational Functions and Nested Disks

In Akhiezer's book [“The Classical Moment Problem and Some Related Questions in Analysis,” Oliver & Boyd, Edinburghasol;London, 1965] the uniqueness of the solution of the Hamburger moment problem, if a solution exists, is related to a theory of nested disks in the complex plane. The purpose of the present paper is to develop a similar nested disk theory for a moment problem that arises in the study of certain orthogonal rational functions. Let {α_n}^∞_n=0be a sequence in the open unit disk in the complex plane, let

Full-size image

( /|α_k|=−1 whenα_k=0), and let

Full-size image

We consider the following “moment” problem: Given a positive-definite Hermitian inner product ·, · on × , find a non-decreasing functionμon [−π, π] (or a positive Borel measureμon [−π,π)) such that

Full-size image

In particular we give necessary and sufficient conditions for the uniqueness of the solution in the case that If this series diverges the solution is always unique.     

Strong bias of group generators: an obstacle to the “product replacement algorithm”

Let G be a finite group. Efficient generation of nearly uniformly distributed random elements in G, starting from a given set of generators of G, is a central problem in computational group theory. In this paper we demonstrate a weakness in the popular “product replacement algorithm,” widely used for this purpose. The main results are the following. Let be the set of generating k-tuples of elements of G. Consider the distribution of the first components of the k-tuples in induced by the uniform distribution over  . We show that there exist infinite sequences of groups G such that this distribution is very far from uniform in two different senses: (1) its variation distance from uniform is >1−ε; and (2) there exists a short word (of length (loglog|G|)^O(k)) which separates the two distributions with probability 1−ε. The class of groups we analyze is direct powers of alternating groups. The methods used include statistical analysis of permutation groups, the theory of random walks, the AKS sorting network, and a randomized simulation of monotone Boolean operations by group operations, inspired by Barrington's work on bounded-width branching programs. The problem is motivated by the product replacement algorithm which was introduced in [Comm. Algebra 23 (1995) 4931–4948] and is widely used. Our results show that for certain groups the probability distribution obtained by the product replacement algorithm has a bias which can be detected by a short straight line program.     

Bicolored graph partitioning, or: gerrymandering at its worst

This study is motivated by an electoral application where we look into the following question: how much biased can the assignment of parliament seats be in a majority system under the effect of vicious gerrymandering when the two competing parties have the same electoral strength? To give a first theoretical answer to this question, we introduce a stylized combinatorial model, where the territory is represented by a rectangular grid graph, the vote outcome by a “balanced” red/blue node bicoloring and a district map by a connected partition of the grid whose components all have the same size. We constructively prove the existence in cycles and grid graphs of a balanced bicoloring and of two antagonist “partisan” district maps such that the discrepancy between their number of “red” (or “blue”) districts for that bicoloring is extremely large, in fact as large as allowed by color balance.     

An application of the Turán theorem to domination in graphs

A function f:V(G)→{+1,−1} defined on the vertices of a graph G is a signed dominating function if for any vertex v the sum of function values over its closed neighborhood is at least 1. The signed domination number γ_s(G) of G is the minimum weight of a signed dominating function on G. By simply changing “{+1,−1}” in the above definition to “{+1,0,−1}”, we can define the minus dominating function and the minus domination number of G. In this note, by applying the Turán theorem, we present sharp lower bounds on the signed domination number for a graph containing no (k+1)-cliques. As a result, we generalize a previous result due to Kang et al. on the minus domination number of k-partite graphs to graphs containing no (k+1)-cliques and characterize the extremal graphs.     

Passage to the limit in Proposition I, Book I of Newton's Principia

The purpose of this paper is to analyze the way in which Newton uses his polygon model and passes to the limit in Proposition I, Book I of his Principia. It will be evident from his method that the limit of the polygon is indeed the orbital arc of the body and that his approximation of the actual continuous force situation by a series of impulses passes correctly in the limit into the continuous centripetal force situation. The analysis of the polygon model is done in two ways: (1) using the modern concepts of force, linear momentum, linear impulse, and velocity, and (2) using Newton's concepts of motive force and quantity of motion. It should be clearly understood that the term “force” without the adjective “motive,” is used in the modern sense, which is that force is a vector which is the time rate of change of the linear momentum. Newton did not use the word “force” in this modern sense. The symbol F denotes modern force. For Newton “force” was “motive force,” which is measured by the change in the quantity of motion of a body. Newton's “quantity of motion” is proportional to the magnitude of the modern vector momentum. Motive force is a scalar and the symbol F_m is used for motive force.     

Resource augmentation for online bounded space bin packing

We study online bounded space bin packing in the resource augmentation model of competitive analysis. In this model, the online bounded space packing algorithm has to pack a list L of items in (0,1] into a small number of bins of size b1. Its performance is measured by comparing the produced packing against the optimal offline packing of the list L into bins of size 1.We present a complete solution to this problem: For every bin size b1, we design online bounded space bin packing algorithms whose worst case ratio in this model comes arbitrarily close to a certain bound ρ(b). Moreover, we prove that no online bounded space algorithm can perform better than ρ(b) in the worst case.     

Māl, enunciations, and the prehistory of Arabic algebra

Medieval Arabic algebra books intended for practical training generally have in common a first “book” which is divided into two sections: one on the methods of solving simplified equations and manipulating expressions, followed by one consisting of worked-out problems. By paying close attention to the wording of the problems in the books of al-Khwārizmī, Abū Kāmil, and Ibn Badr, we reveal the different ways the word māl was used. In the enunciation of a problem it is a common noun meaning “quantity,” while in the solution it is the proper noun naming the square of “thing” (shay '). We then look into the differences between the wording of enunciations and equations, which clarify certain problems solved without “thing,” and help explain the development of algebra before the time of al-Khwārizmī.     

A generalization of a theorem on biseparating maps

In J. Math. Anal. Appl. 12 (1995) 258–265, Araujo et al. proved that for any linear biseparating map  from C(X) onto C(Y), where X and Y are completely regular, there exist ω in C(Y) and an homeomorphism h from the realcompactification vX of X onto vY, such that

The compact version of this result was proved before by Jarosz in Bull. Canad. Math. Soc. 33 (1990) 139–144. In Contemp. Math., Vol. 253, 2000, pp. 125–144, Henriksen and Smith asked to what extent the result above can be generalized to a larger class of algebras. In the present paper, we give an answer to that question as follows. Let A and B be uniformly closed Φ-algebras. We first prove that every order bounded linear biseparating map from A onto B is automatically a weighted isomorphism, that is, there exist ω in B and a lattice and algebra isomorphism ψ between A and B such that

(a)=ωψ(a) for all aA.

We then assume that every universally σ-complete projection band in A is essentially one-dimensional. Under this extra condition and according to a result from Mem. Amer. Math. Soc. 143 (2000) 679 by Abramovich and Kitover, any linear biseparating map from A onto B is automatically order bounded and, by the above, a weighted isomorphism. It turns out that, indeed, the latter result is a generalization of the aforementioned theorem by Araujo et al. since we also prove that every universally σ-complete projection band in the uniformly closed Φ-algebra C(X) is essentially one-dimensional.     

Parameterized graph cleaning problems

We investigate the Induced Subgraph Isomorphism problem with non-standard parameterization, where the parameter is the difference |V(G)|−|V(H)| with H and G being the smaller and the larger input graph, respectively. Intuitively, we can interpret this problem as “cleaning” the graph G, regarded as a pattern containing extra vertices indicating errors, in order to obtain the graph H representing the original pattern. We show fixed-parameter tractability of the cases where both H and G are planar and H is 3-connected, or H is a tree and G is arbitrary. We also prove that the problem when H and G are both 3-connected planar graphs is NP-complete without parameterization.     

Mathematical programming models for some smallest-world problems

Given a weighted graph G, in the minimum-cost-edge-selection problem (MCES), a minimum weighted set of edges is chosen subject to an upper bound on the diameter of graph G. Similarly, in the minimum-diameter-edge-selection problem (MDES), a set of edges is chosen to minimize the diameter subject to an upper bound on their total weight. These problems are shown to be equivalent and proven to be NP-complete. MCES is then formulated as a 0–1 integer programming problem. The problems MCES and MDES provide models for determining smallest-world networks and for measuring the “small-worldness” of graphs.     

A PTAS for the sparsest 2-spanner of 4-connected planar triangulations

A t-spanner of an undirected, unweighted graph G is a spanning subgraph of G with the added property that for every pair of vertices in G, the distance between them in is at most t times the distance between them in G. We are interested in finding a sparsest t-spanner, i.e., a t-spanner with the minimum number of edges. In the general setting, this problem is known to be NP-hard for all t2. For t5, the problem remains NP-hard for planar graphs, whereas for t{2,3,4}, the complexity of this problem on planar graphs is still unknown. In this paper we present a polynomial time approximation scheme for the problem of finding a sparsest 2-spanner of a 4-connected planar triangulation.     

Randomized online graph coloring

We study the problem of coloring graphs in an online manner. The only known deterministic online graph coloring algorithm with a sublinear performance function was found by [9.], 319–325). Their algorithm colors graphs of chromatic number χ with no more than (2χn)/log^* n colors, where n is the number of vertices. They point out that the performance can be improved slightly for graphs with bounded chromatic number. For three-chromatic graphs the number of colors used, for example, is O(n log log log n/log log n). We show that randomization helps in coloring graphs online. We present a simple randomized online algorithm to color graphs with expected number of colors O(2^χχ²n^{(χ−2)/(χ−1)}(log n)^1/(χ−1)). For three-colorable graphs the expected number of colors our algorithm uses is . All our algorithms run in polynomial time. It is interesting to note that our algorithm compares well with the best known polynomial time offline algorithms. For instance, the best polynomial time algorithm known for three-colorable graphs, due to [4.] pp. 554–562). We also prove a lower bound of Ω((1/(χ − 1))((log n/(12(χ + 1))) − 1)^χ−1) for the randomized model. No lower bound for the randomized model was previously known. For bounded χ, our result improves even the best known lower bound for the deterministic case: Ω((log n/log log n)^χ−1), due to Noga Alon (personal communication, September 1989).     

Sum Multicoloring of Graphs

Scheduling dependent jobs on multiple machines is modeled by the graph multicoloring problem. In this paper we consider the problem of minimizing the average completion time of all jobs. This is formalized as the sum multicoloring problem: Given a graph and the number of colors required by each vertex, find a multicoloring which minimizes the sum of the largest colors assigned to the vertices. It reduces to the known sum coloring problem when each vertex requires exactly one color.This paper reports a comprehensive study of the sum multicoloring problem, treating three models: with and without preemptions, as well as co-scheduling where jobs cannot start while others are running. We establish a linear relation between the approximability of the maximum independent set problem and the approximability of the sum multicoloring problem in all three models, via a link to the sum coloring problem. Thus, for classes of graphs for which the independent set problem is ρ-approximable, we obtain O(ρ)-approximations for preemptive and co-scheduling sum multicoloring and O(ρ log n)-approximation for nonpreemptive sum multicoloring. In addition, we give constant ratio approximations for a number of fundamental classes of graphs, including bipartite, line, bounded degree, and planar graphs.