Improved Bounds for Acyclic Job Shop Scheduling

In acyclic job shop scheduling problems there are n jobs and m machines. Each job is composed of a sequence of operations to be performed on different machines. A legal schedule is one in which within each job, operations are carried out in order, and each machine performs at most one operation in any unit of time. If D denotes the length of the longest job, and C denotes the number of time units requested by all jobs on the most loaded machine, then clearly lb = max[C,D] is a lower bound on the length of the shortest legal schedule. A celebrated result of Leighton, Maggs, and Rao shows that if all operations are of unit length, then there always is a legal schedule of length O(lb), independent of n and m. For the case that operations may have different lengths, Shmoys, Stein and Wein showed that there always is a legal schedule of length , where the notation is used to suppress terms. We improve the upper bound to . We also show that our new upper bound is essentially best possible, by proving the existence of instances of acyclic job shop scheduling for which the shortest legal schedule is of length . This resolves (negatively) a known open problem of whether the linear upper bound of Leighton, Maggs, and Rao applies to arbitrary job shop scheduling instances (without the restriction to acyclicity and unit length operations). Received June 30, 1998 RID="*" ID="*" Incumbent of the Joseph and Celia Reskin Career Development Chair RID="†" ID="†" Research was done while staying at the Weizmann Institute, supported by a scholarship from the Minerva foundation.     

Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs

Received: August 22, 1996     

A Combinatorial Algorithm for the Minimum (2, r)-Metric Problem and Some Generalizations

be a graph with nonnegative integer capacities c(e) of the edges , and let μ be a metric that establishes distances on the pairs of elements of a subset . In the minimum 0-extension problem (*), one is asked for finding a (semi)metric m on V such that m coincides with μ within T, each is at zero distance from some , and the value is as small as possible. This is the classical minimum (undirected) cut problem when and , and the minimum (2, r)-metric problem when μ is the path metric of the complete bipartite graph . It is known that the latter problem can be solved in strongly polynomial time by use of the ellipsoid method. We develop a polynomial time algorithm for the minimum (2, r)-metric problem, using only ``purely combinatorial' means. The algorithm simultaneously solves a certain associated integer multiflow problem. We then apply this algorithm to solve (*) for a wider class of metrics μ, present other results and raise open questions. Received: June 11, 1998     

Quick Approximation to Matrices and Applications

m ×n matrix A with entries between say −1 and 1, and an error parameter ε between 0 and 1, we find a matrix D (implicitly) which is the sum of simple rank 1 matrices so that the sum of entries of any submatrix (among the ) of (A−D) is at most εmn in absolute value. Our algorithm takes time dependent only on ε and the allowed probability of failure (not on m, n). We draw on two lines of research to develop the algorithms: one is built around the fundamental Regularity Lemma of Szemerédi in Graph Theory and the constructive version of Alon, Duke, Leffman, R?dl and Yuster. The second one is from the papers of Arora, Karger and Karpinski, Fernandez de la Vega and most directly Goldwasser, Goldreich and Ron who develop approximation algorithms for a set of graph problems, typical of which is the maximum cut problem. From our matrix approximation, the above graph algorithms and the Regularity Lemma and several other results follow in a simple way. We generalize our approximations to multi-dimensional arrays and from that derive approximation algorithms for all dense Max-SNP problems. Received: July 25, 1997     

On a Generalized Anti-Ramsey Problem

For positive integers , a coloring of is called a -coloring if the edges of every receive at least and at most colors. Let denote the maximum number of colors in a -coloring of . Given we determine the largest such that all -colorings of have at most O(n) colors and we determine asymptotically when it is of order equal to . We give several bounds and constructions. Received May 3, 1999     

Critical Facets of the Stable Set Polytope

Dedicated to the memory of Paul Erdős A facet of the stable set polytope of a graph G can be viewed as a generalization of the notion of an -critical graph. We extend several results from the theory of -critical graphs to facets. The defect of a nontrivial, full-dimensional facet of the stable set polytope of a graph G is defined by . We prove the upper bound for the degree of any node u in a critical facet-graph, and show that can occur only when . We also give a simple proof of the characterization of critical facet-graphs with defect 2 proved by Sewell [11]. As an application of these techniques we sharpen a result of Surányi [13] by showing that if an -critical graph has defect and contains nodes of degree , then the graph is an odd subdivision of . Received October 23, 1998     

A Fast Algorithm For Finding A Maximum Free Multiflow In An Inner Eulerian Network And Some Generalizations

be a network, where is an undirected graph with nodes and edges, is a set of specified nodes of , called terminals, and each edge of has a nonnegative integer capacity . If the total capacity of edges with one end at is even for every non-terminal node , then is called inner Eulerian. A free multiflow is a collection of flows between arbitrary pairs of terminals such that the total flow through each edge does not exceed its capacity. In this paper we first generalize a method in Karzanov [11] to find a maximum integer free multiflow in an inner Eulerian network, in time, where is the complexity of finding a maximum flow between two terminals. Next we extend our algorithm to solve the so-called laminar locking problem on multiflows, also in time. We then consider analogs of the above problems in inner balanced directed networks, which means that for each non-terminal node , the sums of capacities of arcs entering and leaving are the same. We show that for such a network a maximum integer free multiflow can be constructed in time, and then extend this result to the corresponding locking problem. Received: March 24, 1997     

NOTE – On the Membership Problem for the Elementary Closure of a Polyhedron

A , an integral vector b and some rational vector , decide whether is outside the elementary closure , is NP-complete. This result is achieved by an extension of a result by Caprara and Fischetti. Received: November 11, 1998     

On a Max-min Problem Concerning Weights of Edges

The weight w(e) of an edge e = uv of a graph is defined to be the sum of degrees of the vertices u and v. In 1990 P. Erdős asked the question: What is the minimum weight of an edge of a graph G having n vertices and m edges? This paper brings a precise answer to the above question of Erdős. Received July 12, 1999     

A Sublinear Bipartiteness Tester for Bounded Degree Graphs

d , and the testing algorithm can perform queries of the form: ``who is the ith neighbor of vertex v'. The tester should determine with high probability whether the graph is bipartite or ε-far from bipartite for any given distance parameter ε. Distance between graphs is defined to be the fraction of entries on which the graphs differ in their incidence-lists representation. Our testing algorithm has query complexity and running time where N is the number of graph vertices. It was shown before that queries are necessary (for constant ε), and hence the performance of our algorithm is tight (in its dependence on N), up to polylogarithmic factors. In our analysis we use techniques that were previously applied to prove fast convergence of random walks on expander graphs. Here we use the contrapositive statement by which slow convergence implies small cuts in the graph, and further show that these cuts have certain additional properties. This implication is applied in showing that for any graph, the graph vertices can be divided into disjoint subsets such that: (1) the total number of edges between the different subsets is small; and (2) each subset itself exhibits a certain mixing property that is useful in our analysis. Received: February 6, 1998     

Submodular Flow Problem with a Nonseparable Cost Function

Received: February 19, 1996     

Improved Pseudorandom Generators for Combinatorial Rectangles

We construct a pseudorandom generator which uses bits and approximates the volume of any combinatorial rectangle in to within error. This improves on the previous construction using bits by Armoni, Saks, Wigderson, and Zhou [4]. For a subclass of rectangles with at most nontrivial dimensions and each dimension being an interval, we also give a pseudorandom generator using bits. This again improves the previous upper bound by Chari, Rohatgi, and Srinivasan [5]. Received July 29, 1998     

Edge-Coloring Bipartite Multigraphs in O(E logD) Time

Let V, E, and D denote the cardinality of the vertex set, the cardinality of the edge set, and the maximum degree of a bipartite multigraph G. We show that a minimal edge-coloring of G can be computed in O(E logD time. This result follows from an algorithm for finding a matching in a regular bipartite graph in O(E) time. Received September 23, 1999     

On the Knowledge Complexity of

We show that if a language has an interactive proof of logarithmic statistical knowledge-complexity, then it belongs to the class . Thus, if the polynomial time hierarchy does not collapse, then -complete languages do not have logarithmic knowledge complexity. Prior to this work, there was no indication that would contradict languages being proven with even one bit of knowledge. Our result is a common generalization of two previous results: The first asserts that statistical zero knowledge is contained in [11, 2], while the second asserts that the languages recognizable in logarithmic statistical knowledge complexity are in [19]. Next, we consider the relation between the error probability and the knowledge complexity of an interactive proof. Note that reducing the error probability via repetition is not free: it may increase the knowledge complexity. We show that if the negligible error probability is less than (where k(n) is the knowledge complexity) then the language proven is in the third level of the polynomial time hierarchy (specifically, it is in ). In the standard setting of negligible error probability, there exist PSPACE-complete languages which have sub-linear knowledge complexity. However, if we insist, for example, that the error probability is less than , then PSPACE-complete languages do not have sub-quadratic knowledge complexity, unless . In order to prove our main result, we develop an AM protocol for checking that a samplable distribution D has a given entropy h. For any fractions , the verifier runs in time polynomial in and and fails with probability at most to detect an additive error in the entropy. We believe that this protocol is of independent interest. Subsequent to our work Goldreich and Vadhan [16] established that the problem of comparing the entropies of two samplable distributions if they are noticeably different is a natural complete promise problem for the class of statistical zero knowledge (). Received January 6, 2000 RID=" " ID=" " This research was performed while the authors were visiting the Computer Science Department at the University of Toronto, preliminary version of this paper appeared in [27] RID="*" ID="*" Partially supported by Technion V. P. R. Found––N. Haar and R. Zinn Research Fund. RID="†" ID="†" Partially supported by the grants OTKA T-029255, T-030059, FKFP 0607/1999, and AKP 2000-78 2.1.     

Diophantine Approximations and Integer Points of Cones

The purpose of this note is to present a relation between directed best approximations of a rational vector and the elements of the minimal Hilbert basis of certain rational pointed cones. Furthermore, we show that for a special class of these cones the integer Carathéodory property holds true. Received May 6, 1998 RID="*" ID="*" Supported by a "Leibniz Preis" of the German Science Foundation (DFG) awarded to M. Gr?tschel. RID="†" ID="†" Supported by a "Gerhard-Hess-Forschungsf?rderpreis" of the German Science Foundation (DFG).     

Deterministic Routing With Bounded Buffers: Turning Offline Into Online Protocols

In this paper we present a deterministic protocol for routing arbitrary permutations in arbitrary networks. The protocol is analyzed in terms of the size of the network and the routing number of the network. Given a network H of n nodes, the routing number of H is defined as the maximum over all permutations on {1, ..., n} of the minimal number of steps to route offline in H. We show that for any network H of size n with routing number R our protocol needs time to route any permutation in H using only constant size edge buffers. This significantly improves all previously known results on deterministic routing. In particular, our result yields optimal deterministic routing protocols for arbitrary networks with diameter or bisection width , constant. Furthermore we can extend our result to deterministic compact routing. This yields, e.g., a deterministic routing protocol with runtime O(R logn) for arbitrary bounded degree networks if only O(logn) bits are available at each node for storing routing information. Our protocol is a combination of a generalized ``routing via simulation' technique with an new deterministic protocol for routing h-relations in an extended version of a multibutterfly network. This protocol improves upon all previous routing protocols known for variants of the multibutterfly network. The ``routing via simulation' technique used here extends a method previously introduced by the authors for designing compact routing protocols. Received July 18, 1997     

Transversals in Uniform Hypergraphs with Property (p,2)

Dedicated to the memory of Paul Erdős Let f(r,p,t) (p > t >= 1, r >= 2) be the maximum of the cardinality of a minimum transversal over all r-uniform hypergraphs possessing the property that every subhypergraph of with p edges has a transversal of size t. The values of f(r,p,2) for p = 3, 4, 5, 6 were found in [1] and bounds on f(r,7,2) are given in [3]. Here we prove that for large p and huge r. Received September 23, 1999 RID="*" ID="*" This work was partially supported by the grant 99-01-00581 of the Russian Foundation for Fundamental Research and the Dutch–Russian Grant NWO-047-008-006.     

Existence of Polyhedral Embeddings of Graphs

It is proved that the decision problem about the existence of an embedding of face-width 3 of a given graph is NP-complete. A similar result is proved for some related decision problems. This solves a problem raised by Neil Robertson. Received July 6, 1998 RID="*" ID="*" Supported in part by the Ministry of Science and Technology of Slovenia, Research Project J1–0502–0101–98.     

Highly Arc-Transitive Digraphs With No Homomorphism Onto <Emphasis Type="Bold">Z</Emphasis>

In an infinite digraph D, an edge e' is reachable from an edge e if there exists an alternating walk in D whose initial and terminal edges are e and e'. Reachability is an equivalence relation and if D is 1-arc-transitive, then this relation is either universal or all of its equivalence classes induce isomorphic bipartite digraphs. In Combinatorica, 13 (1993), Cameron, Praeger and Wormald asked if there exist highly arc-transitive digraphs (apart from directed cycles) for which the reachability relation is not universal and which do not have a homomorphism onto the two-way infinite directed path (a Cayley digraph of Z with respect to one generator). In view of an earlier result of Praeger in Australas. J. Combin., 3 (1991), such digraphs are either locally infinite or have equal in- and out-degree. In European J. Combin., 18 (1997), Evans gave an affirmative answer by constructing a locally infinite example. For each odd integer n >= 3, a construction of a highly arc-transitive digraph without property Z satisfying the additional properties that its in- and out-degree are equal to 2 and that the reachability equivalence classes induce alternating cycles of length 2n, is given. Furthermore, using the line digraph operator, digraphs having the above properties but with alternating cycles of length 4 are obtained. Received April 12, 1999 Supported in part by "Ministrstvo za šolstvo, znanost in šport Slovenije", research program PO-0506-0101-99.     

Randomized Simplex Algorithms on Klee-Minty Cubes

The analysis of two most natural randomized pivot rules on the Klee-Minty cubes leads to (nearly) quadratic lower bounds for the complexity of linear programming with random pivots. Thus we disprove two bounds (for the expected running time of the random-edge simplex algorithm on Klee-Minty cubes) conjectured in the literature. At the same time, we establish quadratic upper bounds for the expected length of a path for a simplex algorithm with random pivots on the classes of linear programs under investigation. In contrast to this, we find that the average length of an increasing path in a Klee-Minty cube is exponential when all paths are taken with equal probability. Received: September 2, 1996