A tighter upper bound for random MAX 2-SAT

Given a conjunctive normal form F with n variables and m=cn 2-clauses, it is interesting to study the maximum number of clauses satisfied by all the assignments of the variables (MAX 2-SAT). When c is sufficiently large, the upper bound of of random MAX 2-SAT had been derived by the first-moment argument. In this paper, we provide a tighter upper bound (3/4)cn+g(c)cn also using the first-moment argument but correcting the error items for f(n,cn), and when considering the ε³ error item. Furthermore, we extrapolate the region of the validity of the first-moment method is c>2.4094 by analyzing the higher order error items.     

Improved deterministic approximation algorithms for Max TSP

We present an O(n³)-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically , where n is the number of vertices in the input complete edge-weighted (undirected) graph. We also present an O(n³)-time approximation algorithm for the metric case of the problem whose approximation ratio is asymptotically . Both algorithms improve on the previous bests.     

Jebelean-Weber's algorithm without spurious factors

Tudor Jebelean and Ken Weber introduced an algorithm for finding (a,b)-pairs satisfying au+bv≡0 (mod k), with . It is based on Sorenson's “k-ary reduction”. This algorithm does not preserve the GCD and its related GCD algorithm has an O(n²) time bit complexity in the worst case. We present a modified version which avoids this problem. We show that a slightly modified GCD algorithm has an O(n²/logn) running time in the worst case, where n is the number of bits of the larger input.     

The complexity of changing colourings with bounded maximum degree

Let G be a graph, x,y∈V(G), and ?:V(G)→[k] a k-colouring of G such that ?(x)=?(y). If then the following question is NP-complete: Does there exist a k-colouring ?^′ of G such that ?^′(x)≠?^′(y)? Conversely, if then the problem is polynomial time.     

Efficient visual secret sharing scheme for color images

A k-out-of-n visual secret sharing scheme (VSSS) resolves the visual variant of the k-out-of-n secret sharing problem where only k or more out of n participants can reveal the secret by human visual system without any cryptographic computation. The best pixel expansion of the general k-out-of-n VSSS for c-colored images was c×m by Yang and Laih [New colored visual secret sharing schemes, Des Codes Cryptogr. 24 (2000) 325-335] where m is the pixel expansion of an existing binary k-out-of-n VSSS. Regarding the c-colored n-out-of-n scheme, the best pixel expansion is (c-1)2^n-1-c+2 and c(c-1)2^n-2-c when n is odd and even, respectively, by Blundo et al. [Improved schemes for visual cryptography, Des Codes Cryptogr. 24 (2001) 255-278]. In this paper, we propose a new c-colored k-out-of-n VSSS by using a pixel expansion of that is more efficient than ever.     

Distinct squares in run-length encoded strings

Squares are strings of the form ww where w is any nonempty string. Two squares ww and w^′w^′ are of different types if and only if w≠w^′. Fraenkel and Simpson [Avieri S. Fraenkel, Jamie Simpson, How many squares can a string contain? Journal of Combinatorial Theory, Series A 82 (1998) 112-120] proved that the number of square types contained in a string of length n is bounded by O(n). The set of all different square types contained in a string is called the vocabulary of the string. If a square can be obtained by a series of successive right-rotations from another square, then we say the latter covers the former. A square is called a c-square if no square with a smaller index can cover it and it is not a trivial square. The set containing all c-squares is called the covering set. Note that every string has a unique covering set. Furthermore, the vocabulary of the covering set are called c-vocabulary. In this paper, we prove that the cardinality of c-vocabulary in a string is less than , where N is the number of runs in this string.     

Transforming spanning trees and pseudo-triangulations

Let TS be the set of all crossing-free straight line spanning trees of a planar n-point set S. Consider the graph TS where two members T and T^′ of TS are adjacent if T intersects T^′ only in points of S or in common edges. We prove that the diameter of TS is O(logk), where k denotes the number of convex layers of S. Based on this result, we show that the flip graph PS of pseudo-triangulations of S (where two pseudo-triangulations are adjacent if they differ in exactly one edge—either by replacement or by removal) has a diameter of O(nlogk). This sharpens a known O(nlogn) bound. Let be the induced subgraph of pointed pseudo-triangulations of PS. We present an example showing that the distance between two nodes in is strictly larger than the distance between the corresponding nodes in PS.     

Finding a maximum-density path in a tree under the weight and length constraints

Let T=(V,E) be a tree with n nodes such that each node v is associated with a value-weight pair(valv,wv), where the valuevalv is a real number and the weightwv is a positive integer. The density of a path P=〈v₁,v₂,…,vk〉 is defined as . The weight of P, denoted by w(P), is . Given a tree of n nodes, two integers wmin and wmax, and a length lower bound L, we present a pseudo-polynomial O(wmaxnL)-time algorithm to find a maximum-density path P in T such that wmin?w(P)?wmax and the length of P is at least L.     

On the linear complexity of some new q-ary sequences

Some new q-ary sequences with period q^3ek-1 (q=p^m, p an odd prime, m, e, k integers) are first constructed and then, inspired by Antweiler’s method, their linear complexity is examined. The exact value of linear complexity k(6e)^w is determined when . Furthermore, an upper bound of the linear complexity is given for the other values of r. Our results show that this sequence has larger linear span than GMW sequence with the same parameters. Finally, the results of a Maple program are included to illustrate the validity of the results.     

Flying over a polyhedral terrain

We consider the problem of computing shortest paths in three-dimensions in the presence of a single-obstacle polyhedral terrain, and present a new algorithm that for any p?1, computes a (c+ε)-approximation to the Lp-shortest path above a polyhedral terrain in time and O(nlogn) space, where n is the number of vertices of the terrain, and c=²(p−1)/p. This leads to a FPTAS for the problem in L₁ metric, a -factor approximation algorithm in Euclidean space, and a 2-approximation algorithm in the general Lp metric.     

Acyclic edge colourings of graphs with the number of edges linearly bounded by the number of vertices

Let G be any finite graph. A mapping c:E(G)→{1,…,k} is called an acyclic edge k-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced in G by all the edges that have colour i or j is acyclic. The smallest number k of colours such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G and is denoted by .Determining the acyclic chromatic index of a graph is a hard problem, both from theoretical and algorithmical point of view. In 1991, Alon et al. proved that for any graph G of maximum degree Δ(G). This bound was later improved to 16Δ(G) by Molloy and Reed. In general, the problem of computing the acyclic chromatic index of a graph is NP-complete. Only a few algorithms for finding acyclic edge colourings have been known by now. Moreover, these algorithms work only for graphs from particular classes.In our paper, we prove that for every graph G which satisfies the condition that |E(G^′)|?t|V(G^′)|−1 for each subgraph G^′⊆G, where t?2 is a given integer, the constant p=2t³−3t+2. Based on that result, we obtain a polynomial algorithm which computes such a colouring. The class of graphs covered by our theorem is quite rich, for example, it contains all t-degenerate graphs.     

An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem

We consider the minimum maximal matching problem, which is NP-hard (Yannakakis and Gavril (1980) [18]). Given an unweighted simple graph G=(V,E), the problem seeks to find a maximal matching of minimum cardinality. It was unknown whether there exists a non-trivial approximation algorithm whose approximation ratio is less than 2 for any simple graph. Recently, Z. Gotthilf et al. (2008) [5] presented a -approximation algorithm, where c is an arbitrary constant.In this paper, we present a -approximation algorithm based on an LP relaxation, where χ^′(G) is the edge-coloring number of G. Our algorithm is the first non-trivial approximation algorithm whose approximation ratio is independent of |V|. Moreover, it is known that the minimum maximal matching problem is equivalent to the edge dominating set problem. Therefore, the edge dominating set problem is also -approximable. From edge-coloring theory, the approximation ratio of our algorithm is , where Δ(G) represents the maximum degree of G. In our algorithm, an LP formulation for the edge dominating set problem is used. Fujito and Nagamochi (2002) [4] showed the integrality gap of the LP formulation for bipartite graphs is at least . Moreover, χ^′(G) is Δ(G) for bipartite graphs. Thus, as far as an approximation algorithm for the minimum maximal matching problem uses the LP formulation, we believe our result is the best possible.     

Optimal per-edge processing times in the semi-streaming model

We present semi-streaming algorithms for basic graph problems that have optimal per-edge processing times and therefore surpass all previous semi-streaming algorithms for these tasks. The semi-streaming model, which is appropriate when dealing with massive graphs, forbids random access to the input and restricts the memory to bits.Particularly, the formerly best per-edge processing times for finding the connected components and a bipartition are O(α(n)), for determining k-vertex and k-edge connectivity O(k²n) and O(n⋅logn) respectively for any constant k and for computing a minimum spanning forest O(logn). All these time bounds we reduce to O(1).Every presented algorithm determines a solution asymptotically as fast as the best corresponding algorithm up to date in the classical RAM model, which therefore cannot convert the advantage of unlimited memory and random access into superior computing times for these problems.     

Flexible coloring

Motivated by reliability considerations in data deduplication for storage systems, we introduce the problem of flexible coloring. Given a hypergraph H and the number of allowable colors k, a flexible coloring of H is an assignment of one or more colors to each vertex such that, for each hyperedge, it is possible to choose a color from each vertex?s color list so that this hyperedge is strongly colored (i.e., each vertex has a different color). Different colors for the same vertex can be chosen for different incident hyperedges (hence the term flexible). The goal is to minimize color consumption, namely, the total number of colors assigned, counting multiplicities. Flexible coloring is NP-hard and trivially approximable, where s is the size of the largest hyperedge, and n is the number of vertices. Using a recent result by Bansal and Khot, we show that if k is constant, then it is UGC-hard to approximate to within a factor of s−ε, for arbitrarily small constant ε>0. Lastly, we present an algorithm with an approximation ratio, where k^′ is number of colors used by a strong coloring algorithm for H.     

All-pairs shortest-paths computation in the presence of negative cycles

We present an algorithm that solves the all-pairs shortest-paths problem on a directed graph with n vertices and m arcs in time O(nm+n²logn), where the arcs are assigned real, possibly negative costs. Our algorithm is new in the following respect. It computes the distance μ(v,w) between each pair v,w of vertices even in the presence of negative cycles, where μ(v,w) is defined as the infimum of the costs of all directed paths from v to w.