All-Pairs Shortest Paths with Real Weights in <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>3</Superscript>/log <Emphasis Type="Italic">n</Emphasis>) Time

We describe an O(n ³/log n)-time algorithm for the all-pairs-shortest-paths problem for a real-weighted directed graph with n vertices. This slightly improves a series of previous, slightly subcubic algorithms by Fredman (SIAM J. Comput. 5:49–60, 1976), Takaoka (Inform. Process. Lett. 43:195–199, 1992), Dobosiewicz (Int. J. Comput. Math. 32:49–60, 1990), Han (Inform. Process. Lett. 91:245–250, 2004), Takaoka (Proc. 10th Int. Conf. Comput. Comb., Lect. Notes Comput. Sci., vol. 3106, pp. 278–289, Springer, 2004), and Zwick (Proc. 15th Int. Sympos. Algorithms and Computation, Lect. Notes Comput. Sci., vol. 3341, pp. 921–932, Springer, 2004). The new algorithm is surprisingly simple and different from previous ones. A preliminary version of this paper appeared in Proc. 9th Workshop Algorithms Data Struct. (WADS), Lect. Notes Comput. Sci., vol. 3608, pp. 318–324, Springer, 2005.     

Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs

We present a deterministic Logspace procedure, which, given a bipartite planar graph on n vertices, assigns O(log n) bits long weights to its edges so that the minimum weight perfect matching in the graph becomes unique. The Isolation Lemma as described in Mulmuley et al. (Combinatorica 7(1):105–131, 1987) achieves the same for general graphs using randomness, whereas we can do it deterministically when restricted to bipartite planar graphs. As a consequence, we reduce both decision and construction versions of the perfect matching problem in bipartite planar graphs to testing whether a matrix is singular, under the promise that its determinant is 0 or 1, thus obtaining a highly parallel SPL\mathsf{SPL} algorithm for both decision and construction versions of the bipartite perfect matching problem. This improves the earlier known bounds of non-uniform SPL\mathsf{SPL} by Allender et al. (J. Comput. Syst. Sci. 59(2):164–181, 1999) and NC\mathsf{NC} ² by Miller and Naor (SIAM J. Comput. 24:1002–1017, 1995), and by Mahajan and Varadarajan (Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC), pp. 351–357, 2000). It also rekindles the hope of obtaining a deterministic parallel algorithm for constructing a perfect matching in non-bipartite planar graphs, which has been open for a long time. Further we try to find the lower bound on the number of bits needed for deterministically isolating a perfect matching. We show that our particular method for isolation will require Ω(log n) bits. Our techniques are elementary.     

Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats

Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623–644, 1977; Jaitly et al. in J. Comput. Syst. Sci. 65:494–507, 2002; Tang et al. in J. Comput. Biol. 9:429–446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n ⁵) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002) takes O(n ¹¹) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case. Part of work was done during a Z.-Z. Chen visit at City University of Hong Kong.     

Location-Oblivious Distributed Unit Disk Graph Coloring

We present the first location-oblivious distributed unit disk graph coloring algorithm having a provable performance ratio of three (i.e. the number of colors used by the algorithm is at most three times the chromatic number of the graph). This is an improvement over the standard sequential coloring algorithm that has a worst case lower bound on its performance ratio of 4−3/k (for any k>2, where k is the chromatic number of the unit disk graph achieving the lower bound) (Tsai et al., in Inf. Process. Lett. 84(4):195–199, 2002). We present a slightly better worst case lower bound on the performance ratio of the sequential coloring algorithm for unit disk graphs with chromatic number 4. Using simulation, we compare our algorithm with other existing unit disk graph coloring algorithms.     

Parallel algorithms for finding polynomial Roots on OTIS-torus

We present two parallel algorithms for finding all the roots of an N-degree polynomial equation on an efficient model of Optoelectronic Transpose Interconnection System (OTIS), called OTIS-2D torus. The parallel algorithms are based on the iterative schemes of Durand–Kerner and Ehrlich methods. We show that the algorithm for the Durand–Kerner method requires (N ^0.75+0.5N ^0.25−1) electronic moves + 2(N ^0.5−1) OTIS moves using N processors. The parallel algorithm for Ehrlich method is shown to run in (N ^0.75+0.5N ^0.25−1) electronic moves + 2(N ^0.5−1) OTIS moves with the same number of processors. The algorithms have lower AT cost than the algorithms presented in Jana (Parallel Comput 32:301–312, 2006). The scalability of the algorithms is also discussed.     

The Directed Orienteering Problem

This paper studies vehicle routing problems on asymmetric metrics. Our starting point is the directed k-TSP problem: given an asymmetric metric (V,d), a root r∈V and a target k≤|V|, compute the minimum length tour that contains r and at least k other vertices. We present a polynomial time O(\fraclog² nloglogn·logk)O(\frac{\log^{2} n}{\log\log n}\cdot\log k)-approximation algorithm for this problem. We use this algorithm for directed k-TSP to obtain an O(\fraclog² nloglogn)O(\frac{\log^{2} n}{\log\log n})-approximation algorithm for the directed orienteering problem. This answers positively, the question of poly-logarithmic approximability of directed orienteering, an open problem from Blum et al. (SIAM J. Comput. 37(2):653–670, 2007). The previously best known results were quasi-polynomial time algorithms with approximation guarantees of O(log ² k) for directed k-TSP, and O(log n) for directed orienteering (Chekuri and Pal in IEEE Symposium on Foundations in Computer Science, pp. 245–253, 2005). Using the algorithm for directed orienteering within the framework of Blum et al. (SIAM J. Comput. 37(2):653–670, 2007) and Bansal et al. (ACM Symposium on Theory of Computing, pp. 166–174, 2004), we also obtain poly-logarithmic approximation algorithms for the directed versions of discounted-reward TSP and vehicle routing problem with time-windows.     

Quadratic Kernelization for Convex Recoloring of Trees

The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called “perfect phylogeny”. For an input consisting of a vertex-colored tree T, the problem is to determine whether recoloring at most k vertices can achieve a convex coloring, meaning by this a coloring where each color class induces a subtree. The problem was introduced by Moran and Snir (J. Comput. Syst. Sci. 73:1078–1089, 2007; J. Comput. Syst. Sci. 74:850–869, 2008) who showed that CR is NP-hard, and described a search-tree based FPT algorithm with a running time of O(k(k/log k) ^k n ⁴). The Moran and Snir result did not provide any nontrivial kernelization. In this paper, we show that CR has a kernel of size O(k ²).     

On the Automatizability of Polynomial Calculus

We prove that Polynomial Calculus and Polynomial Calculus with Resolution are not automatizable, unless W[P]-hard problems are fixed parameter tractable by one-side error randomized algorithms. This extends to Polynomial Calculus the analogous result obtained for Resolution by Alekhnovich and Razborov (SIAM J. Comput. 38(4):1347–1363, 2008).     

A Linear-Time Algorithm for Symmetric Convex Drawings of Internally Triconnected Plane Graphs

We study a crossing minimization problem of drawing a bipartite graph with a radial drawing of two orbits. Radial drawings are one of well-known drawing conventions in social network analysis and visualization, in particular, displaying centrality indices of actors (Wasserman and Faust, Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge, 1994). The main problem in this paper is called the one-sided radial crossing minimization, if the positions of vertices in the outer orbit are fixed. The problem is known to be NP-hard (Bachmaier, IEEE Trans. Vis. Comput. Graph. 13, 583–594, 2007), and a number of heuristics are available (Bachmaier, IEEE Trans. Vis. Comput. Graph. 13, 583–594, 2007). However, there is no approximation algorithm for the crossing minimization problem in radial drawings. We present the first polynomial time constant-factor approximation algorithm for the one-sided radial crossing minimization problem.     

Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems

In this paper, we study two variants of the bin packing and covering problems called Maximum Resource Bin Packing (MRBP) and Lazy Bin Covering (LBC) problems, and present new approximation algorithms for them. For the offline MRBP problem, the previous best known approximation ratio is \frac65\frac{6}{5} (=1.2) achieved by the classical First-Fit-Increasing (FFI) algorithm (Boyar et al. in Theor. Comput. Sci. 362(1–3):127–139, 2006). In this paper, we give a new FFI-type algorithm with an approximation ratio of \frac8071\frac{80}{71} (≈1.12676). For the offline LBC problem, it has been shown in Lin et al. (COCOON, pp. 340–349, 2006) that the classical First-Fit-Decreasing (FFD) algorithm achieves an approximation ratio of \frac7160\frac{71}{60} (≈1.18333). In this paper, we present a new FFD-type algorithm with an approximation ratio of \frac1715\frac{17}{15} (≈1.13333). Our algorithms are based on a pattern-based technique and a number of other observations. They run in near linear time (i.e., O(nlog n)), and therefore are practical.     

Sublinear Fully Distributed Partition with Applications

We present new efficient deterministic and randomized distributed algorithms for decomposing a graph with n nodes into a disjoint set of connected clusters with radius at most k−1 and having O(n ^1+1/k ) intercluster edges. We show how to implement our algorithms in the distributed CONGEST\mathcal{CONGEST} model of computation, i.e., limited message size, which improves the time complexity of previous algorithms (Moran and Snir in Theor. Comput. Sci. 243(1–2):217–241, 2000; Awerbuch in J. ACM 32:804–823, 1985; Peleg in Distributed Computing: A Locality-Sensitive Approach, 2000) from O(n) to O(n ^1−1/k ). We apply our algorithms for constructing low stretch graph spanners and network synchronizers in sublinear deterministic time in the CONGEST\mathcal{CONGEST} model.     

A randomized algorithm for the on-line weighted bipartite matching problem

We study the on-line minimum weighted bipartite matching problem in arbitrary metric spaces. Here, n not necessary disjoint points of a metric space M are given, and are to be matched on-line with n points of M revealed one by one. The cost of a matching is the sum of the distances of the matched points, and the goal is to find or approximate its minimum. The competitive ratio of the deterministic problem is known to be Θ(n), see (Kalyanasundaram, B., Pruhs, K. in J. Algorithms 14(3):478–488, 1993) and (Khuller, S., et al. in Theor. Comput. Sci. 127(2):255–267, 1994). It was conjectured in (Kalyanasundaram, B., Pruhs, K. in Lecture Notes in Computer Science, vol. 1442, pp. 268–280, 1998) that a randomized algorithm may perform better against an oblivious adversary, namely with an expected competitive ratio Θ(log n). We prove a slightly weaker result by showing a o(log ³ n) upper bound on the expected competitive ratio. As an application the same upper bound holds for the notoriously hard fire station problem, where M is the real line, see (Fuchs, B., et al. in Electonic Notes in Discrete Mathematics, vol. 13, 2003) and (Koutsoupias, E., Nanavati, A. in Lecture Notes in Computer Science, vol. 2909, pp. 179–191, 2004). The authors were partially supported by OTKA grants T034475 and T049398.     

The Baire Partial Quasi-Metric Space: A?Mathematical Tool for Asymptotic Complexity Analysis in Computer Science

In 1994, S.G. Matthews introduced the notion of partial metric space in order to obtain a suitable mathematical tool for program verification (Ann. N.Y. Acad. Sci. 728:183–197, 1994). He gave an application of this new structure to parallel computing by means of a partial metric version of the celebrated Banach fixed point theorem (Theor. Comput. Sci. 151:195–205, 1995). Later on, M.P. Schellekens introduced the theory of complexity (quasi-metric) spaces as a part of the development of a topological foundation for the asymptotic complexity analysis of programs and algorithms (Electron. Notes Theor. Comput. Sci. 1:211–232, 1995). The applicability of this theory to the asymptotic complexity analysis of Divide and Conquer algorithms was also illustrated by Schellekens. In particular, he gave a new proof, based on the use of the aforenamed Banach fixed point theorem, of the well-known fact that Mergesort algorithm has optimal asymptotic average running time of computing. In this paper, motivated by the utility of partial metrics in Computer Science, we discuss whether the Matthews fixed point theorem is a suitable tool to analyze the asymptotic complexity of algorithms in the spirit of Schellekens. Specifically, we show that a slight modification of the well-known Baire partial metric on the set of all words over an alphabet constitutes an appropriate tool to carry out the asymptotic complexity analysis of algorithms via fixed point methods without the need for assuming the convergence condition inherent to the definition of the complexity space in the Schellekens framework. Finally, in order to illustrate and to validate the developed theory we apply our results to analyze the asymptotic complexity of Quicksort, Mergesort and Largesort algorithms. Concretely we retrieve through our new approach the well-known facts that the running time of computing of Quicksort (worst case behaviour), Mergesort and Largesort (average case behaviour) are in the complexity classes O(n²)\mathcal{O}(n^{2}), O(nlog₂(n))\mathcal{O}(n\log_{2}(n)) and O(2(n-1)-log₂(n))\mathcal{O}(2(n-1)-\log_{2}(n)), respectively.     

A Note on Exact Algorithms for Vertex Ordering Problems on Graphs

In this note, we give a proof that several vertex ordering problems can be solved in O ^∗(2 ⁿ ) time and O ^∗(2 ⁿ ) space, or in O ^∗(4 ⁿ ) time and polynomial space. The algorithms generalize algorithms for the Travelling Salesman Problem by Held and Karp (J. Soc. Ind. Appl. Math. 10:196–210, 1962) and Gurevich and Shelah (SIAM J. Comput. 16:486–502, 1987). We survey a number of vertex ordering problems to which the results apply.     

On truthfulness and approximation for scheduling selfish tasks

We consider the problem of designing truthful mechanisms for scheduling n tasks on a set of m parallel related machines in order to minimize the makespan. In what follows, we consider that each task is owned by a selfish agent. This is a variant of the KP-model introduced by Koutsoupias and Papadimitriou (Proc. of STACS 1999, pp. 404–413, 1999) (and of the CKN-model of Christodoulou et al. in Proc. of ICALP 2004, pp. 345–357, 2004) in which the agents cannot choose the machine on which their tasks will be executed. This is done by a centralized authority, the scheduler. However, the agents may manipulate the scheduler by providing false information regarding the length of their tasks. We introduce the notion of increasing algorithm and a simple reduction that transforms any increasing algorithm into a truthful one. Furthermore, we show that some of the classical scheduling algorithms are indeed increasing: the LPT algorithm, the PTAS of Graham (SIAM J. Appl. Math. 17(2):416–429, 1969) in the case of two machines, as well as a simple PTAS for the case of m machines, with m a fixed constant. Our results yield a randomized r(1+ε)-approximation algorithm where r is the ratio between the largest and the smallest speed of the related machines. Furthermore, by combining our approach with the classical result of Shmoys et al. (SIAM J. Comput. 24(6):1313–1331, 1995), we obtain a randomized 2r(1+ε)-competitive algorithm. It has to be noticed that these results are obtained without payments, unlike most of the existing works in the field of Mechanism Design. Finally, we show that if payments are allowed then our approach gives a (1+ε)-algorithm for the off-line case with related machines.     

基于图像分割的立体匹配算法

针对在立体匹配中弱纹理及纯色区域匹配不准确和图像分割算法耗时较多的问题,提出一种融合图像分割的立体匹配算法。首先,将初始图像进行高斯滤波和Sobel平滑的处理,获取图像的边缘特征图;然后,将原图的红、绿、蓝三个通道值采用最大类间方差法进行二分类,再融合得到分割模板图;最后,将所得到的灰度图、边缘特征图和分割模板图用于视差计算和视差优化的过程,计算得到视差图。相比绝对差值和(SAD)算法,所提算法在精度上平均提升了14.23个百分点,时间开销上平均每万个像素点只多消耗了7.16 ms。实验结果表明,该算法在纯色及弱纹理区域和视差不连续区域取得了更加平滑的匹配结果,在图像分割上能够自动计算阈值且能够较快地对图像进行分割。     

Moving-window discrete Fourier transform

The moving-window discrete Fourier transform (MWDFT) is a dynamic spectrum analysis in which the next analysis interval differs from the previous one by including the next signal sample and excluding the first one from the previous analysis interval (Dillard in IEEE Trans Inform Theory 13:2–6, 1967, Comput Elect Eng 1:143–152, 1973, USA Patent 4023028, May 10, 1977). Such a spectrum analysis is necessary for time–frequency localization of analyzed signals with given peculiarities (Tolimieri and An in Time–frequency representations. Birkhauser, Basel, 1998). Using the well-known fast Fourier transform (FFT) towards this aim is not effective. Recursive algorithms which use only one complex multiplication for computing one spectrum sample during each analysis interval are more effective. The author improved one algorithm so that it is possible to use only one complex multiplication for computing two, four, and even eight (for complex signals) spectrum samples simultaneously. Problems of realization and application of the MWDFT are also considered in the paper.     

Models of Greedy Algorithms for Graph Problems

Borodin et al. (Algorithmica 37(4):295–326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271–291, 2004) extended their work to facility location and set cover problems. We generalize their model to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems, as Borodin et al. (Algorithmica 37(4):295–326, 2003) did for scheduling. We prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such as shortest path, weighted vertex cover, Steiner tree, and independent set. For example, we show that, for the shortest path problem, no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size), but the well-known Dijkstra’s algorithm is an optimal ADAPTIVE priority algorithm. We also prove that the approximation ratio for weighted vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known upper bounds (Johnson in J. Comput. Syst. Sci. 9(3):256–278, 1974). We give a number of other lower bounds for priority algorithms, as well as a new approximation algorithm for minimum Steiner tree problem with weights in the interval [1,2]. S. Davis’ research supported by NSF grants CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. R. Impagliazzo’s research supported by NSF grant CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. Some work done while at the Institute for Advanced Study, supported by the State of New Jersey.     

Local abstraction–refinement for the <Emphasis Type="Italic">μ</Emphasis>-calculus

A key technique for the verification of programs is counterexample-guided abstraction–refinement (CEGAR). Grumberg et al. (LNCS, vol 3385, pp. 233–249. Springer, Berlin, 2005; Inf Comput 205(8):1130–1148, 2007) developed a CEGAR-based algorithm for the modal μ-calculus. There, every abstract state is split in a refinement step. In this paper, the work of Grumberg et al. is generalized by presenting a new CEGAR-based algorithm for the μ-calculus. It is based on a more expressive abstract model and applies refinement only locally (at a single abstract state), i.e., the lazy abstraction technique for safety properties is adapted to the μ-calculus. Furthermore, it separates refinement determination from the (3-valued based) model checking. Three different heuristics for refinement determination are presented and illustrated.     

对比度、颜色一致性和灰度像素保持的消色算法

目的 为了解决目前消色算法中不能同时保持原始图像的对比度,颜色一致性和灰度像素特征的问题,提出一种新的优化算法,最大限度地同时保留这些视觉特性。方法 为了保持原始图像的结构和局部对比度信息,用双高斯模型构建像素对之间的误差能量项;为了保持颜色一致性,采用局部线性嵌入模型构建能量项,确保原始图像中颜色一致的像素在结果图像中也拥有一样的灰度级;为了保持灰度像素特征,先标记出原始图像中的灰度像素,并强制规定这些像素的灰度值是已知的且在消色变换的过程中始终不变,然后用双高斯模型构建出灰度像素与其他像素之间的误差能量项。线性结合这3个能量项,得到目标能量函数,再通过迭代法求解出使总能量值达到最小的灰度值,从而得到了最终的消色结果。结果 实验结果表明,本文算法能够同时较好地保持原始图像中的对比度、颜色一致性和灰度像素特征。结论 本文算法基本符合人类对图像对比度变化的感知程度,而且能够很好地保持细节信息和全局结构,可应用于数字打印、模式识别等方面,具有很大的应用价值。