Search

Abstract  There is substantial literature dealing with fixed parameter algorithms for the dominating set problem on various families of graphs. In this paper, we give a k O(dk) n time algorithm for finding a dominating set of size at most k in a d-degenerated graph with n vertices. This proves that the dominating set problem is fixed-parameter tractable for degenerated graphs. For graphs that do not contain K h as a topological minor, we give an improved algorithm for the problem with running time (O(h)) hk n. For graphs which are K h -minor-free, the running time is further reduced to (O(log h)) hk/2 n. Fixed-parameter tractable algorithms that are linear in the number of vertices of the graph were previously known only for planar graphs. For the families of graphs discussed above, the problem of finding an induced cycle of a given length is also addressed. For every fixed H and k, we show that if an H-minor-free graph G with n vertices contains an induced cycle of size k, then such a cycle can be found in O(n) expected time as well as in O(nlog n) worst-case time. Some results are stated concerning the (im)possibility of establishing linear time algorithms for the more general family of degenerated graphs. [ABSTRACT FROM AUTHOR]

Abstract   In the last years, new variants of the minimum cycle basis (MCB) problem and new classes of cycle bases have been introduced, as motivated by several applications from disparate areas of scientific and technological inquiry. At present, the complexity status of the MCB problem is settled only for undirected, directed, and strictly fundamental cycle bases (SFCB’s). Weakly fundamental cycle bases (WFCB’s) form a natural superclass of SFCB’s. A cycle basis of a graph G is a WFCB iff ν=0 or there exists an edge e of G and a circuit C i in such that is a WFCB of G∖e. WFCB’s still possess several of the nice properties offered by SFCB’s. At the same time, several classes of graphs enjoying WFCB’s of cost asymptotically inferior to the cost of the cheapest SFCB’s have been found and exhibited in the literature. Considered also the computational difficulty of finding cheap SFCB’s, these works advocated an in-depth study of WFCB’s. In this paper, we settle the complexity status of the MCB problem for WFCB’s (the MWFCB problem). The problem turns out to be -hard. However, in this paper, we also offer a simple and practical 2⌈log 2 n⌉-approximation algorithm for the MWFCB problem. In O(n ν) time, this algorithm actually returns a WFCB whose cost is at most 2⌈log 2 n⌉∑ e∈E(G) w e , thus allowing a fast 2⌈log 2 n⌉-approximation also for the MCB problem. With this algorithm, we provide tight bounds on the cost of any MCB and MWFCB. [ABSTRACT FROM AUTHOR]

Abstract   Broadcasting popular media to clients is the ultimate scalable solution for media-on-demand. Recently, it was shown that if clients can receive data at a rate faster than what they need for playback and if they can store later parts of the media in their buffers, then much higher scalability may be obtained. This paper addresses scheduling problems arising from these new systems for media-on-demand. For given amount of bandwidth, we reduce the maximal start-up delay time for an uninterrupted playback. We achieve our results by introducing two techniques. In the first, the media is arranged on the channels such that clients gain from buffering later parts of the transmission before the actual start of the playback. In the second, segments of different media may be mixed together on the same channel. We introduce a simple class of recursive round-robin scheduling algorithms that implement both techniques. Our results improve the best known asymptotic results. Moreover, our scheduling algorithms outperform known results for practical values for number of media and number of broadcasting channels. For some specific small values, we present solutions that are better than those achieved by our algorithms. Finally, we show that our techniques are useful for models in which clients may not receive data from all the channels, and are applicable to media with different lengths and popularities. [ABSTRACT FROM AUTHOR]

Abstract   It is a well-known result that testing a graph for planarity and, in the affirmative case, computing a planar embedding can be done in linear time. In this paper, we show that the same holds if additionally we require that the produced drawing be symmetric with respect to a given automorphism of the graph. This problem arises naturally in the area of automatic graph drawing, where symmetric and planar drawings are desired whenever possible. [ABSTRACT FROM AUTHOR]

Abstract   In this paper we consider the following question: how many vertices of the discrete torus must be deleted so that no topologically nontrivial cycles remain? We look at two different edge structures for the discrete torus. For (ℤ m d )1, where two vertices in ℤ m are connected if their ℓ 1 distance is 1, we show a nontrivial upper bound of on the number of vertices that must be deleted. For (ℤ m d )∞, where two vertices are connected if their ℓ ∞ distance is 1, Saks et al. (Combinatorica 24(3):525–530, 2004) already gave a nearly tight lower bound of d(m−1) d−1 using arguments involving linear algebra. We give a more elementary proof which improves the bound to m d −(m−1) d , which is precisely tight. [ABSTRACT FROM AUTHOR]

Abstract The Quality of Service Multicast Tree Problem is a generalization of the Steiner tree problem which appears in the context of multimedia multicast and network design. In this generalization, each node possesses a rate and the cost of an edge with length l in a Steiner tree T connecting the source to non-zero rate nodes is l re, where re is the maximum node rate in the component of T-{e} that does not contain the source. The best previously known approximation ratios for this problem (based on the best known approximation factor of 1.549 for the Steiner tree problem in networks) are 2.066 for the case of two non-zero rates and 4.212 for the case of an unbounded number of rates. In this paper we give improved approximation algorithms with ratios of 1.960 and 3.802, respectively. When the minimum spanning tree heuristic is used for finding approximate Steiner trees, then the previously best known approximation ratios of 2.667 for two non-zero rates and 5.542 for an unbounded number of rates are reduced to 2.414 and 4.311, respectively. [ABSTRACT FROM AUTHOR]

Persistent homology with coefficients in a field $$\mathbb {F}$$ coincides with the same for cohomology because of duality. We propose an implementation of a recently introduced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the representation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is more compact and reduces substantially the amount of matrix operations. In addition, we propose a heuristic to simplify further the representation of the cohomology groups and improve both time and space complexities. The paper provides a theoretical analysis, as well as a detailed experimental study of our implementation and comparison with state-of-the-art software for persistent homology and cohomology. [ABSTRACT FROM AUTHOR]

Given a set of points $P \subset\mathbb{R}^{d}$, the k-means clustering problem is to find a set of k centers $C = \{ c_{1},\ldots,c_{k}\}, c_{i} \in\mathbb{R}^{d}$, such that the objective function ∑ e( x, C), where e( x, C) denotes the Euclidean distance between x and the closest center in C, is minimized. This is one of the most prominent objective functions that has been studied with respect to clustering. D-sampling (Arthur and Vassilvitskii, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'07, pp. 1027-1035, SIAM, Philadelphia, ) is a simple non-uniform sampling technique for choosing points from a set of points. It works as follows: given a set of points $P \subset\mathbb{R}^{d}$, the first point is chosen uniformly at random from P. Subsequently, a point from P is chosen as the next sample with probability proportional to the square of the distance of this point to the nearest previously sampled point. D-sampling has been shown to have nice properties with respect to the k-means clustering problem. Arthur and Vassilvitskii (Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'07, pp. 1027-1035, SIAM, Philadelphia, ) show that k points chosen as centers from P using D-sampling give an O(log k) approximation in expectation. Ailon et al. (NIPS, pp. 10-18, ) and Aggarwal et al. (Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 15-28, Springer, Berlin, ) extended results of Arthur and Vassilvitskii (Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'07, pp. 1027-1035, SIAM, Philadelphia, ) to show that O( k) points chosen as centers using D-sampling give an O(1) approximation to the k-means objective function with high probability. In this paper, we further demonstrate the power of D-sampling by giving a simple randomized (1+ ϵ)-approximation algorithm that uses the D-sampling in its core. [ABSTRACT FROM AUTHOR]

The polynomial-time solvable k-hurdle problem is a natural generalization of the classical s- t minimum cut problem where we must select a minimum-cost subset S of the edges of a graph such that | p∩ S|≥ k for every s- t path p. In this paper, we describe a set of approximation algorithms for ' k-hurdle' variants of the NP-hard multiway cut and multicut problems. For the k-hurdle multiway cut problem with r terminals, we give two results, the first being a pseudo-approximation algorithm that outputs a ( k−1)-hurdle solution whose cost is at most that of an optimal solution for k hurdles. Secondly, we provide a $2(1-\frac{1}{r})$-approximation algorithm based on rounding the solution of a linear program, for which we give a simple randomized half-integrality proof that works for both edge and vertex k-hurdle multiway cuts that generalizes the half-integrality results of Garg et al. for the vertex multiway cut problem. We also describe an approximation-preserving reduction from vertex cover as evidence that it may be difficult to achieve a better approximation ratio than $2(1-\frac{1}{r})$. For the k-hurdle multicut problem in an n-vertex graph, we provide an algorithm that, for any constant ε>0, outputs a ⌈(1− ε) k⌉-hurdle solution of cost at most O(log n) times that of an optimal k-hurdle solution, and we obtain a 2-approximation algorithm for trees. [ABSTRACT FROM AUTHOR]

Abstract   Given a graph and degree upper bounds on vertices, the BDMST problem requires us to find a minimum cost spanning tree respecting the given degree bounds. This problem generalizes the Travelling Salesman Path Problem (TSPP), even in unweighted graphs, and so we expect that it is necessary to relax the degree constraints to get efficient algorithms. Könemann and Ravi (Proceedings of the Thirty Second Annual ACM Symposium on Theory of Computing, pp. 537–546, 2000; Proceedings of the Thirty-Fifth ACM Symposium on Theory of Computing, pp. 389–395, 2003) give bicriteria approximation algorithms for the problem using local search techniques of Fischer (Technical Report 14853, Cornell University, 1993). Their algorithms find solutions which make a tradeoff of the approximation factor for the cost of the resulting tree against the factor by which degree constraints are violated. In particular, they give an algorithm which, for a graph with a spanning tree of cost C and degree B, and for parameters b,w>1, produces a tree whose cost is at most wC and whose degree is at most A primary contribution of Könemann and Ravi is to use a Lagrangean relaxation to formally relate the BDMST problem to what we call the MDMST problem, which is the problem of finding an MST of minimum degree in a graph. In their solution to the MDMST problem, they make central use of a local-search approximation algorithm of Fischer. In this paper, we give the first approximation algorithms for the BDMST problem—both our algorithms find trees of optimal cost. We achieve this improvement using a primal-dual cost bounding methodology from Edmonds’ weighted matching algorithms which was not previously used in this context. In order to follow Edmonds’ approach, we develop algorithms for a variant of the MDMST problem in which there are degree lower bound requirements. This variant may be of independent interest; in particular, our results extend to a generalized version of the BDMST problem in which both upper and lower degree bounds are given. First we give a polynomial-time algorithm that finds a tree of optimal cost and with maximum degree at most for any b∈(1,2). We also give a quasi-polynomial-time approximation algorithm which produces a tree of optimal cost C and maximum degree at most B+O(log n/log log n). That is, the error is additive as well as restricted just to the degree. This further improvement in degree is obtained by using augmenting-path techniques that search over a larger solution space than Fischer’s local-search algorithm. [ABSTRACT FROM AUTHOR]

Abstract   The parameterized node multiway cut problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4 k n 3) time algorithm for this problem, significantly improving the previous algorithm of time for the problem. Our result gives the first polynomial time algorithm for the minimum node multiway cut problem when the separator size is bounded by O(log n). [ABSTRACT FROM AUTHOR]

Abstract  In this paper, we study parameterized algorithms for the set splitting problem, for both weighted and unweighted versions. First, we develop a new and effective technique based on a probabilistic method that allows us to develop a simpler and more efficient deterministic kernelization algorithm for the unweighted set splitting problem. We then propose a randomized algorithm for the weighted set splitting problem that is based on a new subset partition technique and has its running time bounded by O *(2 k ), which is significantly better than that of the previous best deterministic algorithm (which only works for the simpler unweighted set splitting problem) of running time O *(2.65 k ). We also show that our algorithm can be de-randomized, which leads to a deterministic parameterized algorithm of running time O *(4 k ) for the weighted set splitting problem and gives the first proof that the problem is fixed-parameter tractable. [ABSTRACT FROM AUTHOR]

Abstract  Inferring graphs from path frequency has been studied as an important problem which has a potential application to drug design and elucidation of chemical structures. Given a multiple set g of strings of labels with length at most K, the problem asks to find a vertex-labeled graph G that attains a one-to-one correspondence between g and the occurrences of labels along all paths of length at most K in G. In this paper, we prove that the problem with K=1 can be formulated as a problem of finding a loopless and connected detachment, based on which an efficient algorithm for solving the problem is derived. Our algorithm also solves the problem with an additional constraint such that every vertex in an inferred graph is required to have a specified degree. [ABSTRACT FROM AUTHOR]

Abstract   An instance of the path hitting problem consists of two families of paths, and ℋ, in a common undirected graph, where each path in ℋ is associated with a non-negative cost. We refer to and ℋ as the sets of demand and hitting paths, respectively. When p∈ℋ and share at least one mutual edge, we say that p hits q. The objective is to find a minimum cost subset of ℋ whose members collectively hit those of . In this paper we provide constant factor approximation algorithms for path hitting, confined to instances in which the underlying graph is a tree, a spider, or a star. Although such restricted settings may appear to be very simple, we demonstrate that they still capture some of the most basic covering problems in graphs. Our approach combines several novel ideas: We extend the algorithm of Garg, Vazirani and Yannakakis (Algorithmica, 18:3–20, 1997) for approximate multicuts and multicommodity flows in trees to prove new integrality properties; we present a reduction that involves multiple calls to this extended algorithm; and we introduce a polynomial-time solvable variant of the edge cover problem, which may be of independent interest. [ABSTRACT FROM AUTHOR]

Abstract   We study an online job scheduling problem arising in networks with aggregated links. The goal is to schedule n jobs, divided into k disjoint chains, on m identical machines, without preemption, so that the jobs within each chain complete in the order of release times and the maximum flow time is minimized. We present a deterministic online algorithm with competitive ratio , and show a matching lower bound, even for randomized algorithms. The performance bound for we derive in the paper is, in fact, more subtle than a standard competitive ratio bound, and it shows that in overload conditions (when many jobs are released in a short amount of time), ’s performance is close to the optimum. We also show how to compute an offline solution efficiently for k=1, and that minimizing the maximum flow time for k,m≥2 is -hard. As by-products of our method, we obtain two offline polynomial-time algorithms for minimizing makespan: an optimal algorithm for k=1, and a 2-approximation algorithm for any k. [ABSTRACT FROM AUTHOR]

Abstract   In this paper, we provide a unified approach to solving preemptive scheduling problems with uniform parallel machines and controllable processing times. We demonstrate that a single criterion problem of minimizing total compression cost subject to the constraint that all due dates should be met can be formulated in terms of maximizing a linear function over a generalized polymatroid. This justifies applicability of the greedy approach and allows us to develop fast algorithms for solving the problem with arbitrary release and due dates as well as its special case with zero release dates and a common due date. For the bicriteria counterpart of the latter problem we develop an efficient algorithm that constructs the trade-off curve for minimizing the compression cost and the makespan. [ABSTRACT FROM AUTHOR]

Abstract   A tree t-spanner T of a graph G is a spanning tree of G whose max-stretch is t, i.e., the distance between any two vertices in T is at most t times their distance in G. If G has a tree t-spanner but not a tree (t−1)-spanner, then G is said to have max-stretch of t. In this paper, we study the Max-Stretch Reduction Problem: for an unweighted graph G=(V,E), find a set of edges not in E originally whose insertion into G can decrease the max-stretch of G. Our results are as follows: (i) For a ring graph, we give a linear-time algorithm which inserts k edges improving the max-stretch optimally. (ii) For a grid graph, we give a nearly optimal max-stretch reduction algorithm which preserves the structure of the grid. (iii) In the general case, we show that it is -hard to decide, for a given graph G and its spanning tree of max-stretch t, whether or not one-edge insertion can decrease the max-stretch to t−1. (iv) Finally, we show that the max-stretch of an arbitrary graph on n vertices can be reduced to s′≥2 by inserting O(n/s′) edges, which can be determined in linear time, and observe that this number of edges is optimal up to a constant. [ABSTRACT FROM AUTHOR]

Abstract  We present a simple O(m+n 6/ε 12) time (1+ε)-approximation algorithm for finding a minimum-cost sequence of lines to cut a convex n-gon out of a convex m-gon. [ABSTRACT FROM AUTHOR]

We show that the quantum query complexity of detecting if an n-vertex graph contains a triangle is $$O(n^{9/7})$$ . This improves the previous best algorithm of Belovs (Proceedings of 44th symposium on theory of computing conference, pp 77-84, 2012) making $$O(n^{35/27})$$ queries. For the problem of determining if an operation $$\circ : S \times S \rightarrow S$$ is associative, we give an algorithm making $$O(|S|^{10/7})$$ queries, the first improvement to the trivial $$O(|S|^{3/2})$$ application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm. [ABSTRACT FROM AUTHOR]

The signature of a permutation $$\sigma $$ is a word $$\mathtt {sg}(\sigma )\subseteq \{\mathfrak {a},\mathfrak {d}\}^*$$ with ith letter $$\mathfrak {d}$$ when $$\sigma $$ has a descent [i.e. $$\sigma (i)>\sigma (i+1)$$ ] and $$\mathfrak {a}$$ when $$\sigma $$ has an ascent [i.e. $$\sigma (i)<\sigma (i+1)$$ ]. The combinatorics of permutations with a prescribed signature is quite well explored. Here we introduce regular classes of permutations, the sets $$\varLambda (L)$$ of permutations with signature in regular languages $$L\subseteq \{\mathfrak {a},\mathfrak {d}\}^*$$ . Given a regular class of permutations we (i) count the permutations of a given length within the class; (ii) compute a closed form formula for the exponential generating function; and (iii) sample uniformly at random the permutation of a given length. We first recall how (i) is solved in the literature for the case of a single signature. We then explain how to extend these methods to regular classes of permutations using language equations from automata theory. We give two methods to solve (ii) in terms of exponentials of matrices. For the third problem we provide both discrete and continuous recursive methods as well as an extension of Boltzmann sampling to uncountable union of sets parametrised by a variable ranging over an interval. Last but not least, a part of our contributions are based on a geometric interpretation of a subclass of regular timed languages (that is, recognised by timed automata specific to our problem). [ABSTRACT FROM AUTHOR]

We study the complexity of the Channel Assignment problem. By applying the meet-in-the-middle approach we get an algorithm for the $$\ell $$ -bounded Channel Assignment (when the edge weights are bounded by $$\ell $$ ) running in time $$O^*((2\sqrt{\ell +1})^n)$$ . This is the first algorithm which breaks the $$(O(\ell ))^n$$ barrier. We extend this algorithm to the counting variant, at the cost of slightly higher polynomial factor. Very recently the second author showed that Channel Assignment does not admit a $$O(c^n)$$ -time algorithm, for a constant c independent of $$\ell $$ . We consider a similar question for Generalized $$T$$ - Coloring, a CSP problem that generalizes Channel Assignment. We show that Generalized $$T$$ - Coloring does not admit a $$2^{2^{o\left( \sqrt{n}\right) }} \mathrm{poly}(r)$$ -time algorithm, where r is the size of the instance. [ABSTRACT FROM AUTHOR]

We introduce a new algebraic sieving technique to detect constrained multilinear monomials in multivariate polynomial generating functions given by an evaluation oracle. The polynomials are assumed to have coefficients from a field of characteristic two. As applications of the technique, we show an $$O^*(2^k)$$ -time polynomial space algorithm for the $$k$$ -sized Graph Motif problem. We also introduce a new optimization variant of the problem, called Closest Graph Motif and solve it within the same time bound. The Closest Graph Motif problem encompasses several previously studied optimization variants, like Maximum Graph Motif, Min- Substitute Graph Motif, and Min- Add Graph Motif. Finally, we provide a piece of evidence that our result might be essentially tight: the existence of an $$O^*((2-\epsilon )^k)$$ -time algorithm for the Graph Motif problem implies an $$O((2-\epsilon ')^n)$$ -time algorithm for Set Cover. [ABSTRACT FROM AUTHOR]

It is known to be NP-hard to decide whether a graph can be made chordal by the deletion of k vertices or by the deletion of k edges. Here we present a uniformly polynomial-time algorithm for both problems: the running time is f( k)⋅ n α for some constant α not depending on k and some f depending only on k. For large values of n, such an algorithm is much better than trying all the O( n k) possibilities. Therefore, the chordal deletion problem parameterized by the number k of vertices or edges to be deleted is fixed-parameter tractable. This answers an open question of Cai (Discrete Appl. Math. 127:415–429, ). [ABSTRACT FROM AUTHOR]

Abstract   Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k-th root operations for integral k, and taking roots of polynomials whose coefficients are given by the values of subexpressions. We consider the sign computation of real algebraic expressions, a task vital for the implementation of geometric algorithms. We prove a new separation bound for real algebraic expressions and compare it analytically and experimentally with previous bounds. The bound is used in the sign test of the number type leda::real. [ABSTRACT FROM AUTHOR]

Abstract   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]. [ABSTRACT FROM AUTHOR]

Abstract   We present a method to speed up the dynamic program algorithms used for solving the HMM decoding and training problems for discrete time-independent HMMs. We discuss the application of our method to Viterbi’s decoding and training algorithms (IEEE Trans. Inform. Theory IT-13:260–269, 1967), as well as to the forward-backward and Baum-Welch (Inequalities 3:1–8, 1972) algorithms. Our approach is based on identifying repeated substrings in the observed input sequence. Initially, we show how to exploit repetitions of all sufficiently small substrings (this is similar to the Four Russians method). Then, we describe four algorithms based alternatively on run length encoding (RLE), Lempel-Ziv (LZ78) parsing, grammar-based compression (SLP), and byte pair encoding (BPE). Compared to Viterbi’s algorithm, we achieve speedups of Θ(log n) using the Four Russians method, using RLE, using LZ78, using SLP, and Ω(r) using BPE, where k is the number of hidden states, n is the length of the observed sequence and r is its compression ratio (under each compression scheme). Our experimental results demonstrate that our new algorithms are indeed faster in practice. We also discuss a parallel implementation of our algorithms. [ABSTRACT FROM AUTHOR]

Abstract   We consider online coloring of intervals with bandwidth in a setting where colors have variable capacities. Whenever the algorithm opens a new color, it must choose the capacity for that color and cannot change it later. A set of intervals can be assigned the same color a of capacity C a if the sum of bandwidths of intervals at each point does not exceed C a . The goal is to minimize the total capacity of all the colors used. We consider the bounded model, where all capacities must be chosen in the range (0,1], and the unbounded model, where the algorithm may use colors of any positive capacity. For the absolute competitive ratio, we give an upper bound of 14 and a lower bound of 4.59 for the bounded model, and an upper bound of 4 and a matching lower bound of 4 for the unbounded model. We also consider the offline version of these problems and show that whereas the unbounded model is polynomially solvable, the bounded model is NP-hard in the strong sense and admits a 3.6-approximation algorithm. [ABSTRACT FROM AUTHOR]

Abstract   Given a set of monomials, the Minimum AND-Circuit problem asks for a circuit that computes these monomials using AND-gates of fan-in two and being of minimum size. We prove that the problem is not polynomial-time approximable within a factor of less than 1.0051 unless , even if the monomials are restricted to be of degree at most three. For the latter case, we devise several efficient approximation algorithms, yielding an approximation ratio of 1.278. For the general problem, we achieve an approximation ratio of d−3/2, where d is the degree of the largest monomial. In addition, we prove that the problem is fixed parameter tractable with the number of monomials as parameter. Finally, we discuss generalizations of the Minimum AND-Circuit problem and relations to addition chains and grammar-based compression. [ABSTRACT FROM AUTHOR]

Abstract   We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game-theoretic approach and graph decompositions called q -branched tree decompositions, which can be interpreted as a parameterized version of tree decompositions. Path decomposition and (standard) tree decomposition are two extreme cases of q-branched tree decompositions. The equivalence between nondeterministic graph searching and q-branched tree decomposition enables us to design an exact (exponential time) algorithm computing q-branched treewidth for all q≥0, which is thus valid for both treewidth and pathwidth. This algorithm performs as fast as the best known exact algorithm for pathwidth. Conversely, this equivalence also enables us to design a lower bound on the amount of nondeterminism required to search a graph with the minimum number of searchers. [ABSTRACT FROM AUTHOR]

Abstract   The Maximum Induced Matching (MIM) Problem asks for a largest set of pairwise vertex-disjoint edges in a graph which are pairwise of distance at least two. It is well-known that the MIM problem is NP-complete even on particular bipartite graphs and on line graphs. On the other hand, it is solvable in polynomial time for various classes of graphs (such as chordal, weakly chordal, interval, circular-arc graphs and others) since the MIM problem on graph G corresponds to the Maximum Independent Set problem on the square G *=L(G)2 of the line graph L(G) of G, and in some cases, G * is in the same graph class; for example, for chordal graphs G, G * is chordal. The construction of G *, however, requires time, where m is the number of edges in G. Is has been an open problem whether there is a linear-time algorithm for the MIM problem on chordal graphs. We give such an algorithm which is based on perfect elimination order and LexBFS. [ABSTRACT FROM AUTHOR]

Abstract   We present an O(n 3(log log n/log n)5/4) time algorithm for all pairs shortest paths. This algorithm improves on the best previous result of O(n 3/log n) time. [ABSTRACT FROM AUTHOR]

Abstract We propose an efficient and accurate randomized approximation algorithm for computing the price of European-Asian options. Our algorithm can be seen as a modification of the approximation algorithm developed by Aingworth et al. (2000) into a randomized algorithm, which improves the accuracy theoretically as well as practically. We also propose a new option named the Saving-Asian option which enjoys advantages of both the European-Asian and American-Asian options. It is shown that our approximation algorithm also works for pricing Saving-Asian options. [ABSTRACT FROM AUTHOR]

For a set $P$ of $n$ points in the plane and an integer $k \leq n$, consider the problem of finding the smallest circle enclosing at least $k$ points of $P$. We present a randomized algorithm that computes in $O( n k )$ expected time such a circle, improving over previously known algorithms. Further, we present a linear time $\delta$-approximation algorithm that outputs a circle that contains at least $k$ points of $P$ and has radius less than $(1+\delta)r_{opt}(P,k)$, where $r_{opt}(P,k)$ is the radius of the minimum circle containing at least $k$ points of $P$. The expected running time of this approximation algorithm is $O(n + n \cdot\min((1/k\delta^3) \log^2 (1/\delta), k))$. [ABSTRACT FROM AUTHOR]

We present a new algorithm, called MCS-M, for computing minimal triangulations of graphs. Lex-BFS, a seminal algorithm for recognizing chordal graphs, was the genesis for two other classical algorithms: LEX M and MCS. LEX M extends the fundamental concept used in Lex-BFS, resulting in an algorithm that not only recognizes chordality, but also computes a minimal triangulation of an arbitrary graph. MCS simplifies the fundamental concept used in Lex-BFS, resulting in a simpler algorithm for recognizing chordal graphs. The new algorithm MCS-M combines the extension of LEX M with the simplification of MCS, achieving all the results of LEX M in the same time complexity. [ABSTRACT FROM AUTHOR]

We present an O(n log n)-time algorithm to solve the three-dimensional layers-of-maxima problem. This is an improvement over the prior O(n log n log log n)-time solution. A previous claimed O(n log n)-time solution due to Atallah et al. has technical flaws. Our algorithm is based on a common framework underlying previous work, but to implement it we devise a new data structure to solve a special case of dynamic planar point location in a staircase subdivision. Our data structure itself relies on a new extension to dynamic fractional cascading that allows vertices of high degree in the control graph. [ABSTRACT FROM AUTHOR]