Search

Abstract In sum coloring, it is required to find a proper coloring of the vertices of a graph using positive integers, such that the sum of colors of the vertices is minimized. First Fit is the natural coloring algorithm that processes vertices one by one (in some order), and colors the current vertex with the minimum color that was not used for any of its already considered neighbors. Here, we study the approximation ratio of First Fit for sum coloring for the class of claw-free graphs, its most natural subclasses, and its generalizations, and get tight bounds for it. Highlights • A thorough study of the approximation ratio for the natural algorithm First Fit. • A study of sum coloring of graphs, of vertices or edges. • A tight analysis of (k + 1)-claw free graphs, with new types of examples. • A tight analysis for important subclasses of via linear programs. • A tight analysis for edge coloring and a tight analysis for unit interval graphs. [ABSTRACT FROM AUTHOR]

Abstract An HV-graph is a planar graph with vertex-degree at most four such that each edge is labeled either H (horizontal) or V (vertical). The HV-planarity testing problem asks whether an HV-graph admits an HV-drawing , that is, a planar drawing such that each edge with label H is drawn as a horizontal segment and each edge with label V is drawn as a vertical segment. We prove that the HV-planarity testing problem is NP-complete even for graphs with vertex-degree at most three, which answers an open question posed by both Manuch et al. [30] and Durocher et al. [17]. On the positive side, we prove that the HV-planarity testing problem can be solved in polynomial-time for series-parallel graphs. This result significantly extends a previous result by Durocher et al. about HV-planarity testing of biconnected outerplanar graphs of maximum vertex-degree three. Highlights • HV-planarity testing is NP-complete, even for graphs with vertex-degree at most 3. • Polynomial-time HV-planarity testing for 2-connected series-parallel graphs. • Polynomial-time HV-planarity testing for partial 2-trees. [ABSTRACT FROM AUTHOR]

Abstract Let R be a finite set of terminals in a convex metric space (M , d). We give approximation algorithms for problems of finding a minimum size set S ⊆ M of additional points such that the unit-disc graph G [ R ∪ S ] of R ∪ S satisfies some connectivity properties. Let Δ be the maximum number of independent points in a unit ball. For the Steiner Tree with Minimum Number of Steiner Points problem we obtain approximation ratio 1 + ln ⁡ (Δ − 1) + ϵ , which in R 2 reduces to 1 + ln ⁡ 4 + ϵ < 2.3863 + ϵ ; this improves the ratios ⌊ (Δ + 1) / 2 ⌋ + 1 + ϵ of [19] and 2.5 + ϵ of [7] , respectively. For the Steiner Forest with Minimum Number of Steiner Points problem we give a simple Δ-approximation algorithm, improving the ratio 2 (Δ − 1) of [21]. We also simplify the Δ-approximation of [4] , when G [ R ∪ S ] should be 2-connected. Highlights • We consider connectivity problems on unit-disc graphs in a convex metric space. • Let Δ be the maximum number of independent points in a unit ball. • For Steiner Tree with Minimum Number of Steiner Points we improve the ratio (Δ + 1) / 2 to 1 + ln ⁡ (Δ − 1). • For Steiner Forest with Minimum Number of Steiner Points we improve the ratio 2 (Δ − 1) to Δ. [ABSTRACT FROM AUTHOR]

We study the approximability of (Finite-)Valued Constraint Satisfaction Problems (VCSPs) with a fixed finite constraint language Γ consisting of finitary functions on a fixed finite domain. Ene et al. have shown that, under a mild technical condition, the basic LP relaxation is optimal for constant-factor approximation for VCSP ( Γ ) unless the Unique Games Conjecture fails. Using the algebraic approach to the CSP, we give new natural algebraic conditions for the finiteness of the integrality gap for the basic LP relaxation of VCSP ( Γ ) and show how this leads to efficient constant-factor approximation algorithms for several examples that cover all previously known cases that are NP-hard to solve to optimality but admit constant-factor approximation. Finally, we show that the absence of another algebraic condition leads to NP-hardness of constant-factor approximation. Thus, our results indicate where the boundary of constant-factor approximability for VCSPs lies. [ABSTRACT FROM AUTHOR]

Recent research in algorithmic robotics considers combinatorial filters , which concisely capture the discrete structure underlying many reasoning problems for robots. An important recent result is that the filter minimization problem —Given a filter, find the smallest equivalent filter—is NP-hard. This paper extends that result along several dimensions, including hardness proofs for some natural special cases and for approximation, and new results analyzing the only known algorithm for this problem. We show that this problem is not fixed-parameter tractable for any of the obvious parameters, but it is fixed-parameter tractable for a certain combination of new parameters. [ABSTRACT FROM AUTHOR]

State of the art Diffusion Weighted Magnetic Resonance Imaging (DW-MRI) protocols of white matter followed by advanced tractography techniques produce impressive reconstructions of White Matter (WM) pathways. These pathways often contain millions of trajectories (fibers). While for several applications the high number of fibers is essential, other applications (visualization, registration, some types of across-subject comparison) can achieve satisfying results using much smaller sets and may be overburdened by the computational load of the large fiber sets. In this paper we propose a novel, highly efficient algorithm for extracting a meaningful subset of fibers, which we term the Fiber-Density-Coreset (FDC). The reduced set is optimized to represent the main structures of the brain. FDC is based on an efficient geometric approximation paradigm named coresets, an optimization scheme showing much success in tasks requiring large computation time and/or memory. FDC was compared to two commonly used methods for selecting a reduced set of fibers: fiber-clustering and downsampling. The reduced sets were evaluated by several methods, including a novel structural comparison to the full sets called 3D indicator structure comparison (3D-ISC). The comparison was applied to High Angular Resolution Diffusion Imaging (HARDI) scans of 15 healthy individuals obtained from the Human Connectome Project. FDC produced the most satisfying subsets, consistently in all 15 subjects. It also displayed low memory usage and significantly lower running time than conventional fiber reduction schemes. [ABSTRACT FROM AUTHOR]

Abstract: Zero-order ultrasensitivity (ZOU) is a long known and interesting phenomenon in enzyme networks. Here, a substrate is reversibly modified by two antagonistic enzymes (a ‘push–pull' system) and the fraction in modified state undergoes a sharp switching from near-zero to near-unity at a critical value of the ratio of the enzyme concentrations, under saturation conditions. ZOU and its extensions have been studied for several decades now, ever since the seminal paper of Goldbeter and Koshland (1981); however, a complete probabilistic treatment, important for the study of fluctuations in finite populations, is still lacking. In this paper, we study ZOU using a modular approach, akin to the total quasi-steady state approximation (tQSSA). This approach leads to a set of Fokker–Planck (drift–diffusion) equations for the probability distributions of the intermediate enzyme-bound complexes, as well as the modified/unmodified fractions of substrate molecules. We obtain explicit expressions for various average fractions and their fluctuations in the linear noise approximation (LNA). The emergence of a ‘critical point’ for the switching transition is rigorously established. New analytical results are derived for the average and variance of the fractional substrate concentration in various chemical states in the near-critical regime. For the total fraction in the modified state, the variance is shown to be a maximum near the critical point and decays algebraically away from it, similar to a second-order phase transition. The new analytical results are compared with existing ones as well as detailed numerical simulations using a Gillespie algorithm. [Copyright &y& Elsevier]

Abstract: A cut-and-paste operation can be a reversal, a transposition, or a transreversal on circular or linear permutations. There are several approximation algorithms for sorting signed permutations by combinations of these operations. For sorting unsigned permutations, we only know an algorithm with performance ratio 3 and its improved version with performance ratio allowing reversals and transpositions. In this paper, we present a 2.25-approximation algorithm for sorting unsigned circular permutations by cut-and-paste operations. A structure called tie is proposed to represent the alternating path of length 5. We can classify the ties into 6 types and find ways to remove the breakpoints for each type of ties, so that every cut-and-paste operation can reduce at least breakpoints averagely. Our algorithm can be used to sort unsigned linear permutations and achieve the performance ratio 2.25 if another operation named revrev is allowed. [Copyright &y& Elsevier]

Abstract: We present a deterministic black box solution for online approximate matching. Given a pattern of length m and a streaming text of length n that arrives one character at a time, the task is to report the distance between the pattern and a sliding window of the text as soon as the new character arrives. Our solution requires time for each input character, where is the total running time of the best offline algorithm. The types of approximation that are supported include exact matching with wildcards, matching under the Hamming norm, approximating the Hamming norm, k-mismatch and numerical measures such as the and norms. For these examples, the resulting online algorithms take , , , , and time per character, respectively. The space overhead is linear in the pattern size, which we show is optimal for any deterministic algorithm. [Copyright &y& Elsevier]

Abstract: We consider the following vertex coloring problem. We are given an undirected graph , where each vertex v is associated with a penalty rejection cost . We need to choose a subset of vertices, , and to find a proper coloring of the induced subgraph of G over . We are interested in both the number of colors used to color the vertices of , and in the total rejection cost of all other vertices. The goal is to minimize the sum of these two amounts. In this paper we consider both the online and the offline versions of this problem. In the online version, vertices arrive one at a time, revealing the rejection cost of the current vertex and the set of edges connecting it to previously revealed vertices. We also consider the classical online coloring problem on bounded degree graphs and on -claw free graphs. [ABSTRACT FROM AUTHOR]

Abstract: We study the capacitated vertex cover problem, a generalization of the well-known vertex-cover problem. Given a graph , the goal is to cover all the edges by picking a minimum cover using the vertices. When we pick a vertex, we can cover up to a pre-specified number of edges incident on this vertex (its capacity). The problem is clearly NP-hard as it generalizes the well-known vertex-cover problem. Previously, approximation algorithms with an approximation factor of 2 were developed with the assumption that an arbitrary number of copies of a vertex may be chosen in the cover. If we are allowed to pick at most a fixed number of copies of each vertex, the approximation algorithm becomes much more complex. Chuzhoy and Naor (FOCS, 2002) have shown that the weighted version of this problem is at least as hard as set cover; in addition, they developed a 3-approximation algorithm for the unweighted version. We give a 2-approximation algorithm for the unweighted version, improving the Chuzhoy–Naor bound of three and matching (up to lower-order terms) the best approximation ratio known for the vertex-cover problem. [Copyright &y& Elsevier]

Abstract: The server allocation with bounded simultaneous requests problem arises in isolated infostations, where mobile users going through the coverage area require immediate high-bit rate communications such as web surfing, file transferring, voice messaging, email and fax. Given a set of service requests, each characterized by a temporal interval and a category, an integer k, and an integer for each category c, the problem consists in assigning a server to each request in such a way that at most k mutually simultaneous requests are assigned to the same server at the same time, out of which at most are of category c, and the minimum number of servers is used. Since this problem is computationally intractable, a 2-approximation on-line algorithm is exhibited which asymptotically gives a -approximation, where . Generalizations of the problem are considered, where each request r is also characterized by a bandwidth rate , and the sum of the bandwidth rates of the simultaneous requests assigned to the same server at the same time is bounded, and where each request is characterized also by a gender bandwidth. Such generalizations contain bin-packing, multiprocessor task scheduling, and interval graph coloring as special cases, and they admit on-line algorithms providing constant approximations. [Copyright &y& Elsevier]