Two-dimensional packing with conflicts

We study the two-dimensional version of the bin packing problem with conflicts. We are given a set of (two-dimensional) squares V = {1, 2, . . . ,n} with sides and a conflict graph G = (V, E). We seek to find a partition of the items into independent sets of G, where each independent set can be packed into a unit square bin, such that no two squares packed together in one bin overlap. The goal is to minimize the number of independent sets in the partition. This problem generalizes the square packing problem (in which we have ) and the graph coloring problem (in which s _i = 0 for all i = 1,2, . . . , sn). It is well known that coloring problems on general graphs are hard to approximate. Following previous work on the one-dimensional problem, we study the problem on specific graph classes, namely, bipartite graphs and perfect graphs. We design a -approximation for bipartite graphs, which is almost best possible (unless P = NP). For perfect graphs, we design a 3.2744-approximation. An extended abstract version of this paper has appeared in Proceedings of the 16th International Symposium on Fundamentals of Computation Theory (FCT 2007), pp 288–299. Rob van Stee was supported by the Alexander von Humboldt Foundation.     

Maximum Induced Matchings for Chordal Graphs in Linear Time

The Maximum Induced Matching (MIM) Problem asks for a largest set of pairwise vertex-disjoint edges in a graph which are pairwise of distance at least two. It is well-known that the MIM problem is NP-complete even on particular bipartite graphs and on line graphs. On the other hand, it is solvable in polynomial time for various classes of graphs (such as chordal, weakly chordal, interval, circular-arc graphs and others) since the MIM problem on graph G corresponds to the Maximum Independent Set problem on the square G ^*=L(G)² of the line graph L(G) of G, and in some cases, G ^* is in the same graph class; for example, for chordal graphs G, G ^* is chordal. The construction of G ^*, however, requires time, where m is the number of edges in G. Is has been an open problem whether there is a linear-time algorithm for the MIM problem on chordal graphs. We give such an algorithm which is based on perfect elimination order and LexBFS.     

Renaming in synchronous message passing systems with Byzantine failures

We study the renaming problem in a fully connected synchronous network with Byzantine failures. We show that when the original namespace of the processors is unbounded, this problem cannot be solved in an a priori bounded number of rounds for , where n is the size of the network and t is the number of failures. On the other hand, for n > 3t, we present a Byzantine renaming algorithm that runs in O(lg n) rounds. In addition, we present a fast, efficient strong renaming algorithm for n > t, which runs in rounds, where N ₀ is the value of the highest identifier among all the correct processors.     

On approximating the longest path in a graph

We consider the problem of approximating the longest path in undirected graphs. In an attempt to pin down the best achievable performance ratio of an approximation algorithm for this problem, we present both positive and negative results. First, a simple greedy algorithm is shown to find long paths in dense graphs. We then consider the problem of finding paths in graphs that are guaranteed to have extremely long paths. We devise an algorithm that finds paths of a logarithmic length in Hamiltonian graphs. This algorithm works for a much larger class of graphs (weakly Hamiltonian), where the result is the best possible. Since the hard case appears to be that of sparse graphs, we also consider sparse random graphs. Here we show that a relatively long path can be obtained, thereby partially answering an open problem of Broderet al. To explain the difficulty of obtaining better approximations, we also prove hardness results. We show that, for any ε<1, the problem of finding a path of lengthn-n ^ε in ann-vertex Hamiltonian graph isNP-hard. We then show that no polynomial-time algorithm can find a constant factor approximation to the longest-path problem unlessP=NP. We conjecture that the result can be strengthened to say that, for some constant δ>0, finding an approximation of ration ^δ is alsoNP-hard. As evidence toward this conjecture, we show that if any polynomial-time algorithm can approximate the longest path to a ratio of , for any ε>0, thenNP has a quasi-polynomial deterministic time simulation. The hardness results apply even to the special case where the input consists of bounded degree graphs. D. Karger was supported by an NSF Graduate Fellowship, NSF Grant CCR-9010517, and grants from the Mitsubishi Corporation and OTL. R. Motwani was supported by an Alfred P. Sloan Research Fellowship, an IBM Faculty Development Award, grants from Mitsubishi and OTL, NSF Grant CCR-9010517, and NSF Young Investigator Award CCR-9357849, with matching funds from IBM, the Schlumberger Foundation, the Shell Foundation, and the Xerox Corporation, G. D. S. Ramkumar was supported by a grant from the Toshiba Corporation. Communicated by M. X. Goemans.     

Distributed MST for constant diameter graphs

This paper considers the problem of distributively constructing a minimum-weight spanning tree (MST) for graphs of constant diameter in the bounded-messages model, where each message can contain at most B bits for some parameter B. It is shown that the number of communication rounds necessary to compute an MST for graphs of diameter 4 or 3 can be as high as and , respectively. The asymptotic lower bounds hold for randomized algorithms as well. On the other hand, we observe that O(log n) communication rounds always suffice to compute an MST deterministically for graphs with diameter 2, when B = O(log n). These results complement a previously known lower bound of for graphs of diameter Ω(log n). An extended abstract of this work appears in Proceedings of 20th ACM Symposium on Principles of Distributed Computing, August 2001.     

Greed is good: Approximating independent sets in sparse and bounded-degree graphs

Theminimum-degree greedy algorithm, or Greedy for short, is a simple and well-studied method for finding independent sets in graphs. We show that it achieves a performance ratio of (Δ+2)/3 for approximating independent sets in graphs with degree bounded by Δ. The analysis yields a precise characterization of the size of the independent sets found by the algorithm as a function of the independence number, as well as a generalization of Turán’s bound. We also analyze the algorithm when run in combination with a known preprocessing technique, and obtain an improved performance ratio on graphs with average degree , improving on the previous best of Hochbaum. Finally, we present an efficient parallel and distributed algorithm attaining the performance guarantees of Greedy. Gordon Gekko [29]. A preliminary version of this paper appeared at the 26th ACM Symposium on Theory of Computing, 1994. This work was done while both authors were at the Japan Advanced Institute of Science and Technology, Hokuriku.     

On the complexity of graph self-assembly in accretive systems

We study the complexity of the Accretive Graph Assembly Problem (). An instance of consists of an edge-weighted graph G, a seed vertex in G, and a temperature τ. The goal is to determine if the graph G can be assembled by a sequence of vertex additions starting from the seed vertex. The edge weights model the forces of attraction and repulsion, and determine which vertices can be added to a partially assembled graph at the given temperature. A vertex can be added when the total weight to its already built neighbors in the graph is at least τ. The assembly process is sequential meaning that only one vertex can be added at a time. Our first result is that is NP-complete even on planar graphs with maximum degree 3 when edges have only two different types of weights. This resolves the complexity of in the sense that the problem is poly-time solvable when either the maximum degree is at most 2 or the number of distinct edge weights is one, and is NP-complete otherwise. Our second result is a dichotomy theorem that completely characterizes the complexity of on graphs with maximum degree 3 and two distinct weights: w _p and w _n . We give a simple system of linear constraints on w _p , w _n , and τ that determines whether the problem is NP-complete or is poly-time solvable. In the process of establishing this dichotomy, we give a poly-time algorithm to solve a non-trivial class of Finally, we consider the optimization version of where the goal is to assemble a largest-possible induced subgraph of the given input graph. We show that even on graphs that can be assembled and have maximum degree 3, it is NP-hard to assemble a (1/n ^1-ε)-fraction of the input graph for any here n denotes the number of vertices in G.     

Planar and Grid Graph Reachability Problems

We study the complexity of restricted versions of s-t-connectivity, which is the standard complete problem for . In particular, we focus on different classes of planar graphs, of which grid graphs are an important special case. Our main results are:

Time slot scheduling of compatible jobs

A version of weighted coloring of a graph is introduced which is motivated by some types of scheduling problems: each node v of a graph G corresponds to some operation to be processed (with a processing time w(v)), edges represent nonsimultaneity requirements (incompatibilities). We have to assign each operation to one time slot in such a way that in each time slot, all operations assigned to this slot are compatible; the length of a time slot will be the maximum of the processing times of its operations. The number k of time slots to be used has to be determined as well. So, we have to find a k-coloring = of G such that w(S ₁) + ⋅s +w(S _k ) is minimized where w(S _i ) = max {w(v) :v∊V}. Properties of optimal solutions are discussed, and complexity and approximability results are presented. Heuristic methods are given for establishing some of these results. The associated decision problems are shown to be NP-complete for bipartite graphs, for line-graphs of bipartite graphs, and for split graphs.     

Single machine batch scheduling problem with family setup times and release dates to minimize makespan

In this paper we consider the single machine batch scheduling problem with family setup times and release dates to minimize makespan. We show that this problem is strongly NP-hard, and give an time dynamic programming algorithm and an time dynamic programming algorithm for the problem, where n is the number of jobs, m is the number of families, k is the number of distinct release dates and P is the sum of the setup times of all the families and the processing times of all the jobs. We further give a heuristic with a performance ratio 2. We also give a polynomial-time approximation scheme (PTAS) for the problem.     

Simple a posteriori error estimators for the <Emphasis Type="Italic">h</Emphasis>-version of the boundary element method

The h-h/2-strategy is one well-known technique for the a posteriori error estimation for Galerkin discretizations of energy minimization problems. One considers to estimate the error , where is a Galerkin solution with respect to a mesh and is a Galerkin solution with respect to the mesh obtained from a uniform refinement of . This error estimator is always efficient and observed to be also reliable in practice. However, for boundary element methods, the energy norm is non-local and thus the error estimator η does not provide information for a local mesh-refinement. We consider Symm’s integral equation of the first kind, where the energy space is the negative-order Sobolev space . Recent localization techniques allow to replace the energy norm in this case by some weighted L ²-norm. Then, this very basic error estimation strategy is also applicable to steer an h-adaptive algorithm. Numerical experiments in 2D and 3D show that the proposed method works well in practice. A short conclusion is concerned with other integral equations, e.g., the hypersingular case with energy space and , respectively, or a transmission problem. Dedicated to Professor Ernst P. Stephan on the occasion of his 60th birthday.     

Lower bounds for sense of direction in regular graphs

A graph G with n vertices and maximum degree cannot be given weak sense of direction using less than colours. It is known that n colours are always sufficient, and it was conjectured that just are really needed, that is, one more colour is sufficient. Nonetheless, it has been shown [3] that for sufficiently large n there are graphs requiring more colours than . In this paper, using recent results in asymptotic graph enumeration, we show that (surprisingly) the same bound holds for regular graphs. We also show that colours are necessary, where d _G is the degree of G.Received: April 2002, Accepted: April 2003, Sebastiano Vigna: Partially supported by the Italian MURST (Finanziamento di iniziative di ricerca diffusa condotte da parte di giovani ricercatori).The results of this paper appeared in a preliminary form in Distributed Computing. 14th International Conference, DISC 2000, Springer-Verlag, 2000.     

Improved Bounds on Quantum Learning Algorithms

In this article we give several new results on the complexity of algorithms that learn Boolean functions from quantum queries and quantum examples.

Efficient Solution of A, x ( k )?= b ( k ) Using A ?1

In this work, we consider the problem of solving , , where b ^(k+1) = f(x ^(k)). We show that when A is a full matrix and , where depends on the specific software and hardware setup, it is faster to solve for by explicitly evaluating the inverse matrix A ⁻¹ rather than through the LU decomposition of A. We also show that the forward error is comparable in both methods, regardless of the condition number of A.     

Algorithms and analyses for maximal vector computation

The maximal vector problem is to identify the maximals over a collection of vectors. This arises in many contexts and, as such, has been well studied.The problem recently gained renewed attention with skyline queries for relational databases and with work to develop skyline algorithms that are external and relationally well behaved. While many algorithms have been proposed, how they perform has been unclear. We study the performance of, and design choices behind, these algorithms. We prove runtime bounds based on the number of vectors N and the dimensionality K. Early algorithms based on divide and conquer established seemingly good average and worst-case asymptotic runtimes. In fact, the problem can be solved in average-case (holding K as fixed). We prove, however, that the performance is quite bad with respect to K. We demonstrate that the more recent skyline algorithms are better behaved, and can also achieve average-case. While K matters for these, in practice, its effect vanishes in the asymptotic. We introduce a new external algorithm, LESS, that is more efficient and better behaved. We evaluate LESS’s effectiveness and improvement over the field, and prove that its average-case running time is .Part of this work was conducted at William & Mary where Ryan Shipley was a student and Parke Godfrey was on faculty while on leave of absence from York.     

An <Emphasis Type="Italic">R</Emphasis> || <Emphasis Type="Italic">C</Emphasis><Subscript>max</Subscript> Quantum Scheduling Algorithm

Grover’s search algorithm can be applied to a wide range of problems; even problems not generally regarded as searching problems, can be reformulated to take advantage of quantum parallelism and entanglement, and lead to algorithms which show a square root speedup over their classical counterparts. In this paper, we discuss a systematic way to formulate such problems and give as an example a quantum scheduling algorithm for an R||C_max problem. R||C_max is representative for a class of scheduling problems whose goal is to find a schedule with the shortest completion time in an unrelated parallel machine environment. Given a deadline, or a range of deadlines, the algorithm presented in this paper allows us to determine if a solution to an R||C_max problem with N jobs and M machines exists, and if so, it provides the schedule. The time complexity of the quantum scheduling algorithm is while the complexity of its classical counterpart is .     

Snap-stabilization and PIF in tree networks

The contribution of this paper is threefold. First, we present the paradigm of snap-stabilization. A snap- stabilizing protocol guarantees that, starting from an arbitrary system configuration, the protocol always behaves according to its specification. So, a snap-stabilizing protocol is a time optimal self-stabilizing protocol (because it stabilizes in 0 rounds). Second, we propose a new Propagation of Information with Feedback (PIF) cycle, called Propagation of Information with Feedback and Cleaning (). We show three different implementations of this new PIF. The first one is a basic cycle which is inherently snap-stabilizing. However, the first PIF cycle can be delayed O(h ²) rounds (where h is the height of the tree) due to some undesirable local states. The second algorithm improves the worst delay of the basic algorithm from O(h ²) to 1 round. The state requirement for the above two algorithms is 3 states per processor, except for the root and leaf processors that use only 2 states. Also, they work on oriented trees. We then propose a third snap-stabilizing PIF algorithm on un-oriented tree networks. The state requirement of the third algorithm depends on the degree of the processors, and the delay is at most h rounds. Next, we analyze the maximum waiting time before a PIF cycle can be initiated whether the PIF cycle is infinitely and sequentially repeated or launch as an isolated PIF cycle. The analysis is made for both oriented and un-oriented trees. We show or conjecture that the two best of the above algorithms produce optimal waiting time. Finally, we compute the minimal number of states the processors require to implement a single PIF cycle, and show that both algorithms for oriented trees are also (in addition to being time optimal) optimal in terms of the number of states. WARNING: The concept of snap-stabilization was first introduced in [12]. The concept evolved over the last eight years. We take this evolution in consideration in this paper, which includes the early results published in [10] and [12]. In particular, infinite repetition of computation cycles is a requirement of self-stabilizing systems. This is not required in snap-stabilization because snap-stabilization ensures that the first completed computation cycle is executed according to the specification of the problem. The correctness proofs conform to this basic property.     

Scheduling with conflicts: online and offline algorithms

We consider the following problem of scheduling with conflicts (swc): Find a minimum makespan schedule on identical machines where conflicting jobs cannot be scheduled concurrently. We study the problem when conflicts between jobs are modeled by general graphs. Our first main positive result is an exact algorithm for two machines and job sizes in {1,2}. For jobs sizes in {1,2,3}, we can obtain a -approximation, which improves on the -approximation that was previously known for this case. Our main negative result is that for jobs sizes in {1,2,3,4}, the problem is APX-hard. Our second contribution is the initiation of the study of an online model for swc, where we present the first results in this model. Specifically, we prove a lower bound of on the competitive ratio of any deterministic online algorithm for m machines and unit jobs, and an upper bound of 2 when the algorithm is not restricted computationally. For three machines we can show that an efficient greedy algorithm achieves this bound. For two machines we present a more complex algorithm that achieves a competitive ratio of when the number of jobs is known in advance to the algorithm.