163 research outputs found
Optimal Packet-to-Slot Assignment in Mobile Telecommunications
No full textThe problem of assigning information packets of different services to time slots of a radio frame is addressed. Packet sizes are divisible, and a maximum time slot to which a packet can be assigned is given. We present a polynomial-time scheduling algorithm maximizing the number of scheduled packets
On the diameter of the edge cover polytope
No full textWe characterize adjacency of edge covers on the edge cover polytope of a graph G = (V, E), and derive that the diameter of the edge cover polytope is equal to |E| - ¿(G), where ¿(G) is the minimum size of an edge cover
Blowing up convex sets in the plane
No full textAbstractLet K be a convex set in R2 such that every line in R2 meets K+Z2. We prove that αK+Z2=R2 for α⩾1+23√3, and that this bound is best possible, thus solving a problem of Kannan and Lovász
On the existence of an integral potential in a weighted bidirected graph
No full textAbstractA. Schrijver proved that if A denotes the incidence matrix of a bidirected graph, and b is an integral “length” function on the edges of A, then the system Ax⩽b has an integer solution x if and only if (i) each cycle in A has nonnegative length, and (ii) each doubly odd cycle in A has positive length. Unfortunately these cycles may be very complicated. We show that we may restrict conditions (i) and (ii) to a set of reasonably simple cycles
Conference Matrices from Projective Planes of Order 9
No full textThere exist at least 4 nonisomorphic projective planes of order 9. They determine 1+ 2 + 2 + 2 = 7 nonisomorphic affine planes of order 9, that is, 7 nonisomorphic transversal designs T(10, 9). These yield 7 x (10/5) = 1764 transversal designs T(5,9), each of which defines a strongly regular graph on 81 vertices, and a conference matrix of order 82. We show that these constructions reduce to 26 nonequivalent conference matrices of order 82, which give rise to 175 nonisomorphic strongly regular graphs (81, 40, 19, 20). Our tools are considerations of symmetry, use of a computer, and general results such as the following. For any strongly regular graph (4µ+ 1,2µ, µ - 1, µ) the number of 4-cliques equals the number of 4-cocliques. Section 2 recalls the definitions of a transversal design T(k, n), the corresponding strongly regular graph and, in the case 2k = n + I, the conference matrix of order n2+ 1. Section 3 adds some new results to the general theory of conference matrices (Theorems 3.3 and 3.4). Section 4 explains the tables, which lead to the results mentioned above. Table 1 copies the 7 alline planes of order 9 from [4], Table 2 mentions some useful permutations, and Table 3 lists the 26 nonisomorphic graphs (81, 40, 19, 20). We gratefully acknowledge the collaboration by M. J. van Althuis and the advice by H. A. Wilbrink
Local search for multiprocessor scheduling : how many moves does it take to a local optimum?
No full text
- …
