Arrow Research search

Author name cluster

Magnús M. Halldórsson

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

44 papers
2 author rows

Possible papers

44

I&C Journal 2025 Journal Article

Distributed fractional local ratio and independent set approximation

  • Magnús M. Halldórsson
  • Dror Rawitz

We consider the Maximum Weight Independent Set problem, with a focus on obtaining good approximations for graphs of small maximum degree Δ. We give deterministic local algorithms running in time poly ( Δ, log ⁡ n ) that come close to matching the best centralized results known and improve the previous distributed approximations by a factor of about 2. More precisely, we obtain approximations below Δ + 1 / 2 2, and a further improvement to 8 / 5 + ε when Δ = 3. Technically, this is achieved by leveraging the fractional local ratio technique, for a first application in a distributed setting.

Details DOI

TCS Journal 2023 Journal Article

Superfast coloring in CONGEST via efficient color sampling

  • Magnús M. Halldórsson
  • Alexandre Nolin

We present a procedure for efficiently sampling colors in the CONGEST model. It allows nodes whose number of colors exceeds their number of neighbors by a constant fraction to sample up to Θ ( log ⁡ n ) semi-random colors unused by their neighbors in O ( 1 ) rounds, even in the distance-2 setting. This yields algorithms with O ( log ⁎ ⁡ Δ ) complexity for different edge-coloring, vertex coloring, and distance-2 coloring problems, matching the best possible. In particular, we obtain an O ( log ⁎ ⁡ Δ ) -round CONGEST algorithm for ( 1 + ϵ ) Δ -edge coloring when Δ = Ω ( log 1 + 1 / log ⁎ ⁡ n ⁡ n ), and a poly ( log ⁡ log ⁡ n ) -round algorithm for ( 2 Δ − 1 ) -edge coloring in general. The sampling procedure is inspired by a seminal result of Newman in communication complexity.

Details DOI

STOC Conference 2022 Conference Paper

Near-optimal distributed degree+1 coloring

  • Magnús M. Halldórsson
  • Fabian Kuhn
  • Alexandre Nolin
  • Tigran Tonoyan

We present a new approach to randomized distributed graph coloring that is simpler and more efficient than previous ones. In particular, it allows us to tackle the (deg+1)-list-coloring (D1LC) problem, where each node v of degree d v is assigned a palette of d v +1 colors, and the objective is to find a proper coloring using these palettes. While for (Δ+1)-coloring (where Δ is the maximum degree), there is a fast randomized distributed O (log 3 log n )-round algorithm due to Chang, Li, and Pettie, no o (log n )-round algorithms are known for the D1LC problem.

Details

STOC Conference 2021 Conference Paper

Efficient randomized distributed coloring in CONGEST

  • Magnús M. Halldórsson
  • Fabian Kuhn
  • Yannic Maus
  • Tigran Tonoyan

Distributed vertex coloring is one of the classic problems and probably also the most widely studied problems in the area of distributed graph algorithms. We present a new randomized distributed vertex coloring algorithm for the standard CONGEST model, where the network is modeled as an n -node graph G , and where the nodes of G operate in synchronous communication rounds in which they can exchange O (log n )-bit messages over all the edges of G . For graphs with maximum degree Δ, we show that the (Δ+1)-list coloring problem (and therefore also the standard (Δ+1)-coloring problem) can be solved in O (log 5 log n ) rounds. Previously such a result was only known for the significantly more powerful LOCAL model, where in each round, neighboring nodes can exchange messages of arbitrary size. The best previous (Δ+1)-coloring algorithm in the CONGEST model had a running time of O (logΔ + log 6 log n ) rounds. As a function of n alone, the best previous algorithm therefore had a round complexity of O (log n ), which is a bound that can also be achieved by a na'ive folklore algorithm. For large maximum degree Δ, our algorithm hence is an exponential improvement over the previous state of the art.

Details

TCS Journal 2021 Journal Article

Query minimization under stochastic uncertainty

  • Steven Chaplick
  • Magnús M. Halldórsson
  • Murilo S. de Lima
  • Tigran Tonoyan

We study problems with stochastic uncertainty information on intervals for which the precise value can be queried by paying a cost. The goal is to devise an adaptive decision tree to find a correct solution to the problem in consideration while minimizing the expected total query cost. We show that, for the sorting problem, such a decision tree can be found in polynomial time. For the problem of finding the data item with minimum value, we have some evidence for hardness. This contradicts intuition, since the minimum problem is easier both in the online setting with adversarial inputs and in the offline verification setting. However, the stochastic assumption can be leveraged to beat both deterministic and randomized approximation lower bounds for the online setting.

Details DOI

TCS Journal 2021 Journal Article

Query-competitive sorting with uncertainty

  • Magnús M. Halldórsson
  • Murilo Santos de Lima

We study the problem of sorting under incomplete information, when queries are used to resolve uncertainties. Each of n data items has an unknown value, which is known to lie in a given interval. We can pay a query cost to learn the actual value, and we may allow an error threshold in the sorting. The goal is to find a nearly-sorted permutation by performing a minimum-cost set of queries. We show that an offline optimum query set can be found in polynomial time, and that both oblivious and adaptive problems have simple query-competitive algorithms. The query-competitiveness for the oblivious problem is n for uniform query costs, and unbounded for arbitrary costs; for the adaptive problem, the ratio is 2. We then present a unified adaptive strategy for uniform query costs that yields the following improved results: (i) a 3/2-query-competitive randomized algorithm; (ii) a 5/3-query-competitive deterministic algorithm if the dependency graph has no 2-components after some preprocessing, which has query-competitive ratio 3 / 2 + O ( 1 / k ) if the components obtained have size at least k; and (iii) an exact algorithm if the intervals constitute a laminar family. The first two results have matching lower bounds, and we have a lower bound of 7/5 for large components. We also give a randomized adaptive algorithm with query-competitive factor 1 + 4 3 3 ≈ 1. 7698 for arbitrary query costs, and we show that the 2-query competitive deterministic adaptive algorithm can be generalized for queries returning intervals and for a more general graph problem (which is also a generalization of the vertex cover problem), by using the local ratio technique. Furthermore, we prove that the advice complexity of the adaptive problem is ⌊ n / 2 ⌋ if no error threshold is allowed, and ⌈ n / 3 ⋅ lg ⁡ 3 ⌉ for the general case. Finally, we present some graph-theoretical results regarding co-threshold tolerance graphs, and we discuss uncertainty variants of some classical interval problems.

Details DOI

TCS Journal 2020 Journal Article

Improved distributed algorithms for coloring interval graphs with application to multicoloring trees

  • Magnús M. Halldórsson
  • Christian Konrad

We give a distributed ( 1 + ϵ ) -approximation algorithm for the minimum vertex coloring problem on interval graphs, which runs in the LOCAL model and operates in O ( 1 ϵ log ⁎ ⁡ n ) rounds. If nodes are aware of their interval representations, then the algorithm can be adapted to the CONGEST model using the same number of rounds. Prior to this work, only constant factor approximations using O ( log ⁎ ⁡ n ) rounds were known [1]. Linial's ring coloring lower bound implies that the dependency on log ⁎ ⁡ n cannot be improved. We further prove that the dependency on 1 ϵ is also optimal. To obtain our CONGEST model algorithm, we develop a color rotation technique that may be of independent interest. We demonstrate that color rotations can also be applied to obtain a ( 1 + ϵ ) -approximate multicoloring of directed trees in O ( 1 ϵ log ⁎ ⁡ n ) rounds.

Details DOI

TCS Journal 2020 Journal Article

Leader election in SINR model with arbitrary power control

  • Magnús M. Halldórsson
  • Stephan Holzer
  • Evangelia Anna Markatou
  • Nancy Lynch

We consider the Leader Election Problem in the Signal-to-Interference-plus-Noise-Ratio (SINR) model where nodes can adjust their transmission power. We show that in this setting it is possible to elect a leader in two communication rounds, with high probability. Previously, it was known that Θ ( log ⁡ n ) rounds were sufficient and necessary when using uniform power, where n is the number of nodes in the network. We then examine how much power control is needed to achieve fast leader election. We show that every 2-round leader election algorithm in the SINR model running correctly w. h. p. requires a power range 2 Ω ( n ), even when n is known. We complement this with an algorithm that uses power range 2 O ˜ ( n ) 1, when n is known, and 2 O ˜ ( n 1. 5 ), when n is not known. We also explore tradeoffs between time and power used, and show that to elect a leader in t rounds, a range of possible power levels of size e x p ( n 1 / Θ ( t ) ) is sufficient and necessary.

Details DOI

TCS Journal 2020 Journal Article

Limitations of current wireless link scheduling algorithms

  • Magnús M. Halldórsson
  • Christian Konrad
  • Tigran Tonoyan

We consider the following basic scheduling problem in wireless networks: partition a given set of unit demand communication links into the minimum number of feasible subsets. A subset is feasible if all communications can be done simultaneously, subject to mutual interference. We use the so-called physical model to formulate feasibility. We consider the two families of approximation algorithms that are known to guarantee O ( log ⁡ n ) approximation for the scheduling problem, where n is the number of links. We present network constructions showing that the approximation ratios of those algorithms are no better than logarithmic, both in n and in Δ, where Δ is a geometric parameter – the ratio of the maximum and minimum link lengths.

Details DOI

TCS Journal 2020 Journal Article

Radio aggregation scheduling

  • Rajiv Gandhi
  • Magnús M. Halldórsson
  • Christian Konrad
  • Guy Kortsarz
  • Hoon Oh

We consider the aggregation problem in radio networks: find a spanning tree in a given graph and a conflict-free schedule of the edges so as to minimize the latency of the computation. While a large body of literature exists on this and related problems, we give the first approximation results in graphs that are not induced by unit ranges in the plane. We give a polynomial-time O ˜ ( d n ) -approximation algorithm, where d is the average degree and n the number of vertices in the graph, and show that the problem is Ω ( n 1 − ϵ ) -hard (and Ω ( ( d n ) 1 / 2 − ϵ ) -hard) to approximate even on bipartite graphs, for any ϵ > 0, rendering our algorithm essentially optimal. We also obtain a O ( log ⁡ n ) -approximation in interval graphs.

Details DOI

TCS Journal 2020 Journal Article

Simple and local independent set approximation

  • Ravi B. Boppana
  • Magnús M. Halldórsson
  • Dror Rawitz

We study the worst-case behavior of Turán-like bounds for unweighted and weighted independent sets in bounded-degree graphs. In particular, we revisit a randomized approach of Boppana that forms a simple 1-round distributed algorithm, as well as a streaming algorithm and a preemptive online algorithm. We show that it gives a tight ( Δ + 1 ) / 2 -approximation in unweighted graphs of maximum degree Δ, which is best possible for 1-round distributed algorithms. For weighted graphs, it gives only a ( Δ + 1 ) -approximation, but a simple modification results in an asymptotic expected 0. 529 ( Δ + 1 ) -approximation.

Details DOI

MFCS Conference 2019 Conference Paper

Query-Competitive Sorting with Uncertainty

  • Magnús M. Halldórsson
  • Murilo Santos de Lima

We study the problem of sorting under incomplete information, when queries are used to resolve uncertainties. Each of n data items has an unknown value, which is known to lie in a given interval. We can pay a query cost to learn the actual value, and we may allow an error threshold in the sorting. The goal is to find a nearly-sorted permutation by performing a minimum-cost set of queries. We show that an offline optimum query set can be found in polynomial time, and that both oblivious and adaptive problems have simple query-competitive algorithms. The query-competitiveness for the oblivious problem is n for uniform query costs, and unbounded for arbitrary costs; for the adaptive problem, the ratio is 2. We then present a unified adaptive strategy for uniform query costs that yields: (i) a 3/2-query-competitive randomized algorithm; (ii) a 5/3-query-competitive deterministic algorithm if the dependency graph has no 2-components after some preprocessing, which has query-competitive ratio 3/2 + O(1/k) if the components obtained have size at least k; (iii) an exact algorithm if the intervals constitute a laminar family. The first two results have matching lower bounds, and we have a lower bound of 7/5 for large components. We also show that the advice complexity of the adaptive problem is floor[n/2] if no error threshold is allowed, and ceil[n/3 * lg 3] for the general case.

Details

STOC Conference 2015 Conference Paper

How Well Can Graphs Represent Wireless Interference?

  • Magnús M. Halldórsson
  • Tigran Tonoyan

Efficient use of a wireless network requires that transmissions be grouped into feasible sets, where feasibility means that each transmission can be successfully decoded in spite of the interference caused by simultaneous transmissions. Feasibility is most closely modeled by a signal-to-interference-plus-noise (SINR) formula, which unfortunately is conceptually complicated, being an asymmetric, cumulative, many-to-one relationship. We re-examine how well graphs can capture wireless receptions as encoded in SINR relationships, placing them in a framework in order to understand the limits of such modelling. We seek for each wireless instance a pair of graphs that provide upper and lower bounds on the feasibility relation, while aiming to minimize the gap between the two graphs. The cost of a graph formulation is the worst gap over all instances, and the price of (graph) abstraction is the smallest cost of a graph formulation. We propose a family of conflict graphs that is parameterized by a non-decreasing sub-linear function, and show that with a judicious choice of functions, the graphs can capture feasibility with a cost of O(log* Δ), where Δ is the ratio between the longest and the shortest link length. This holds on the plane and more generally in doubling metrics. We use this to give greatly improved O(log* Δ)-approximation for fundamental link scheduling problems with arbitrary power control. We also explore the limits of graph representations and find that our upper bound is tight: the price of graph abstraction is Ω(log* Δ). In addition, we give strong impossibility results for general metrics, and for approximations in terms of the number of links.

Details

TCS Journal 2014 Journal Article

Wireless capacity with arbitrary gain matrix

  • Magnús M. Halldórsson
  • Pradipta Mitra

Given a set of wireless links, a fundamental problem is to find the largest subset that can transmit simultaneously, within the SINR model of interference. Significant progress on this problem has been made in recent years. In this note, we study the problem in the setting where we are given a fixed set of arbitrary powers each sender must use, and an arbitrary gain matrix defining how signals fade. This variation of the problem appears immune to most algorithmic approaches studied in the literature. Indeed it is very hard to approximate since it generalizes the max independent set problem. Here, we propose a simple semi-definite programming approach to the problem that yields constant factor approximation, if the optimal solution is strictly larger than half of the input size.

Details DOI

TCS Journal 2013 Journal Article

Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees

  • Tatsuya Akutsu
  • Daiji Fukagawa
  • Magnús M. Halldórsson
  • Atsuhiro Takasu
  • Keisuke Tanaka

Given two rooted, labeled, unordered trees, the common subtree problem is to find a bijective matching between subsets of nodes of the trees of maximum cardinality which preserves labels and ancestry relationship. The tree edit distance problem is to determine the least cost sequence of insertions, deletions and substitutions that converts a tree into another given tree. Both problems are known to be hard to approximate within some constant factor in general. We tackle these problems from two perspectives: giving exact algorithms, either for special cases or in terms of some parameters; and approximation algorithms and hardness of approximation. We present a parameterized algorithm in terms of the number of branching nodes that solves both problems and yields polynomial algorithms for several special classes of trees. This is complemented with a tighter APX-hardness proof that holds when the trees are of height one and two, respectively. Furthermore, we present the first approximation algorithms for both problems. In particular, for the common subtree problem for t trees, we present an algorithm achieving a t log 2 ( b O P T + 1 ) ratio, where b O P T is the number of branching nodes in the optimal solution. We also present constant factor approximation algorithms for both problems in the case of bounded height trees.

Details DOI

I&C Journal 2013 Journal Article

Online selection of intervals and t -intervals

  • Unnar Th. Bachmann
  • Magnús M. Halldórsson
  • Hadas Shachnai

A t-interval is a union of at most t half-open intervals on the real line. An interval is the special case where t = 1. In this paper we study the problems of online selection of intervals and t-intervals. We derive lower bounds and (almost) matching upper bounds on the competitive ratios of randomized algorithms for selecting intervals, 2-intervals and t-intervals, for any t > 2. While offline t-interval selection has been studied before, the online version is considered here for the first time.

Details DOI

TCS Journal 2013 Journal Article

SDP-based algorithms for maximum independent set problems on hypergraphs

  • Geir Agnarsson
  • Magnús M. Halldórsson
  • Elena Losievskaja

This paper deals with approximations of maximum independent sets in non-uniform hypergraphs of low degree. We obtain the first performance ratio that is sublinear in terms of the maximum or average degree of the hypergraph. We extend this to the weighted case and give a O ( D ̄ log log D ̄ / log D ̄ ) bound, where D ̄ is the average weighted degree in a hypergraph, matching the best bounds known for the special case of graphs. Our approach is to use an semi-definite technique to sparsify a given hypergraph and then apply combinatorial algorithms to find a large independent set in the resulting sparser instance.

Details DOI

SODA Conference 2011 Conference Paper

Wireless Capacity with Oblivious Power in General Metrics

  • Magnús M. Halldórsson
  • Pradipta Mitra

The capacity of a wireless network is the maximum possible amount of simultaneous communication, taking interference into account. Formally, we treat the following problem. Given is a set of links, each a sender-receiver pair located in a metric space, and an assignment of power to the senders. We seek a maximum subset of links that are feasible in the SINR model: namely, the signal received on each link should be larger than the sum of the interferences from the other links. We give a constant-factor approximation that holds for any length-monotone, sub-linear power assignment and any distance metric. We use this to give essentially tight characterizations of capacity maximization under power control using oblivious power assignments. Specifically, we show that the mean power assignment is optimal for capacity maximization of bi-directional links, and give a tight θ (log n )-approximation of scheduling bi-directional links with power control using oblivious power. For uni-directional links we give a nearly optimal O (log n + log log Δ)-approximation to the power control problem using mean power, where Δ is the ratio of longest and shortest links. Combined, these results clarify significantly the centralized complexity of wireless communication problems.

Details

TCS Journal 2008 Journal Article

Minimizing interference of a wireless ad-hoc network in a plane

  • Magnús M. Halldórsson
  • Takeshi Tokuyama

We consider interference minimization in wireless ad-hoc networks. This is formulated as assigning a suitable transmission radius to each of the given points in the plane, so as to minimize the maximum number of transmission ranges overlapping any point. Using ideas from computational geometry and ϵ -net theory, we attain an O ( Δ ) bound for the maximum interference where Δ is the interference of a uniform-radius ad-hoc network. This generalizes a result given in [P. von Rickenbach, S. Schmid, R. Wattenhofer, A. Zollinger, A robust interference model for wireless ad-hoc networks, in: Proc. 5th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN), Denver, Colorado, USA, April 2005] for the special case of highway model (i. e. , one-dimensional problem) to the two-dimensional case. We show how a distributed algorithm can achieve a slightly weaker bound. We also give a method based on quad-tree decomposition and bucketing that has another provable interference bound in terms of the ratio of the minimum distance to the radius of a uniform-radius ad-hoc network.

Details DOI

MFCS Conference 2004 Invited Paper

Multicoloring: Problems and Techniques

  • Magnús M. Halldórsson
  • Guy Kortsarz

Abstract A multicoloring is an assignment where each vertex is assigned not just a single number (a “color”) but a set of numbers. The number of colors assigned to the vertex is specified by the length (or color requirement ) parameter of that vertex in the input. As usual, adjacent vertices cannot receive the same color; thus here, the sets of colors they receive must be disjoint. Multicolorings are therefore proper generalizations of ordinary graph colorings. The purpose of this paper is to summarize some of the techniques that have been developed specifically for obtaining good approximate multicolorings in different classes of graphs.

Details

TCS Journal 2004 Journal Article

Randomized approximation of the stable marriage problem

  • Magnús M. Halldórsson
  • Kazuo Iwama
  • Shuichi Miyazaki
  • Hiroki Yanagisawa

While the original stable marriage problem requires all participants to rank all members of the opposite sex in a strict order, two natural variations are to allow for incomplete preference lists and ties in the preferences. Either variation is polynomially solvable, but it has recently been shown to be NP-hard to find a maximum cardinality stable matching when both of the variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, an approximation algorithm with a factor two is trivial. In this paper, we give a randomized approximation algorithm RANDBRK and show that its expected approximation ratio is at most 10 / 7 ( < 1. 4286 ) for a restricted but still NP-hard case, where ties occur in only men's lists, each man writes at most one tie, and the length of ties is two. We also show that our analysis is nearly tight by giving a lower bound 32 / 23 ( > 1. 3913 ) for RANDBRK. Furthermore, we show that these restrictions except for the last one can be removed without increasing the approximation ratio too much.

Details DOI

TCS Journal 2003 Journal Article

Approximability results for stable marriage problems with ties

  • Magnús M. Halldórsson
  • Robert W. Irving
  • Kazuo Iwama
  • David F. Manlove
  • Shuichi Miyazaki
  • Yasufumi Morita
  • Sandy Scott

We consider instances of the classical stable marriage problem in which persons may include ties in their preference lists. We show that, in such a setting, strong lower bounds hold for the approximability of each of the problems of finding an egalitarian, minimum regret and sex-equal stable matching. We also consider stable marriage instances in which persons may express unacceptable partners in addition to ties. In this setting, we prove that there are constants δ, δ′ such that each of the problems of approximating a maximum and minimum cardinality stable matching within factors of δ, δ′ (respectively) is NP-hard, under strong restrictions. We also give an approximation algorithm for both problems that has a performance guarantee expressible in terms of the number of lists with ties. This significantly improves on the best-known previous performance guarantee, for the case that the ties are sparse. Our results have applications to large-scale centralized matching schemes.

Details DOI

I&C Journal 2003 Journal Article

Multicoloring trees

  • Magnús M. Halldórsson
  • Guy Kortsarz
  • Andrzej Proskurowski
  • Ravit Salman
  • Hadas Shachnai
  • Jan Arne Telle

Scheduling jobs with pairwise conflicts is modeled by the graph multicoloring problem. It occurs in two versions: in the preemptive case, each vertex may get any set of colors, while in the non-preemptive case, the set of colors assigned to each vertex has to be contiguous. We study these versions of the multicoloring problem on trees, under the sum-of-completion-times objective. In particular, we give a quadratic algorithm for the non-preemptive case, and a faster algorithm in the case that all job lengths are short, while we present a polynomial-time approximation scheme for the preemptive case.

Details DOI

TCS Journal 2002 Journal Article

Online independent sets

  • Magnús M. Halldórsson
  • Kazuo Iwama
  • Shuichi Miyazaki
  • Shiro Taketomi

We study the online version of the independent set problem in graphs. The vertices of an input graph are given one by one along with their edges to previous vertices, and the task is to decide whether to add each given vertex to an independent set solution. The goal is to maximize the size of the independent set, relative to the size of the optimal independent set. Since it is known that no online algorithm can attain competitive ratio better than n−1, where n denotes the number of vertices, we study here relaxations where the algorithm can hedge its bets by maintaining multiple alternative solutions. We introduce two models. In the first model, the algorithm can maintain a multiple number (r(n)) of solutions (independent sets) and choose the largest one as the final solution. We show that the best competitive ratio for this model is θ(n/log n) when r(n) is a polynomial and θ(n) when r(n) is a constant. In the second more powerful model, the algorithm can copy intermediate solutions and extend the copied solutions in different ways. We obtain an upper bound O(n/log n) and a lower bound Ω(n/log 3n) for the best possible competitive ratio when r(n) is a polynomial. Furthermore, we show a tight θ(n) bound when r(n) is a constant. Lower bound results of this paper hold also for randomized online algorithms against an oblivious adversary.

Details DOI

TCS Journal 2001 Journal Article

Approximations for the general block distribution of a matrix

  • Bengt Aspvall
  • Magnús M. Halldórsson
  • Fredrik Manne

The general block distribution of a matrix is a rectilinear partition of the matrix into orthogonal blocks such that the maximum sum of the elements within a single block is minimized. This corresponds to partitioning the matrix onto parallel processors so as to minimize processor load while maintaining regular communication patterns. Applications of the problem include various parallel sparse matrix computations, compilers for high-performance languages, particle in cell computations, video and image compression, and simulations associated with a communication network. We analyze the performance guarantee of a natural and practical heuristic based on iterative refinement, which has previously been shown to give good empirical results. When p 2 is the number of blocks, we show that the tight performance ratio is θ( p ). When the matrix has rows of large cost, the details of the objective function of the algorithm are shown to be important, since a naive implementation can lead to a Ω(p) performance ratio. Extensions to more general cost functions, higher-dimensional arrays, and randomized initial configurations are also considered.

Details DOI

TCS Journal 2000 Journal Article

On the approximation of largest common subtrees and largest common point sets

  • Tatsuya Akutsu
  • Magnús M. Halldórsson

This paper considers the approximability of the largest common subtree and the largest common point-set problems, which have applications in molecular biology. It is shown that the problems cannot be approximated within a factor of n1−ε in polynomial time for any ε>0 unless NP ⊆ ZPP, while a general search algorithm which approximates both problems within a factor of O(n/logn) is presented. For trees of bounded degree, an improved algorithm which approximates the largest common subtree within a factor of O(n/log 2n) is presented. Moreover, several variants of the largest common subtree problem are studied.

Details DOI

FOCS Conference 1993 Conference Paper

Directed vs. Undirected Monotone Contact Networks for Threshold Functions

  • Magnús M. Halldórsson
  • Jaikumar Radhakrishnan
  • K. V. Subrahmanyam 0001

We consider the problem of computing threshold functions using directed and undirected monotone contact networks. Our main results are the following. First, we show that there exist directed monotone contact networks that compute T/sub k//sup n/, 2/spl les/k/spl les/n-1, of size O(k(n-k+2)log(n-k+2)). This bound is almost optimal for small thresholds, since there exists an /spl Omega/(knlog (n/(k-1))) lower bound. Our networks are described explicitly; the previously best upper bound known, obtained from the undirected networks of Dubiner and Zwick, used non-constructive arguments and gave directed networks of size O(k/sup 3. 99/nlog n). Second, we show a lower bound of O(nlogloglog n) on the size of undirected monotone contact networks computing T/sub n-1//sup n/, improving the 2(n-1) lower bound of Markov. Combined with our upper bound result, this shows that directed monotone contact networks compute some threshold functions more easily than undirected networks. >

Details
v2026.09.13