共查询到20条相似文献,搜索用时 31 毫秒
1.
Constant-time distributed dominating set approximation 总被引:1,自引:0,他引:1
Finding a small dominating set is one of the most fundamental problems of classical graph theory. In this paper, we present a new fully distributed approximation algorithm based on LP relaxation techniques. For an arbitrary, possibly constant parameter k and maximum node degree
, our algorithm computes a dominating set of expected size
in
rounds. Each node has to send
messages of size
. This is the first algorithm which achieves a non-trivial approximation ratio in a constant number of rounds.Received: 9 September 2003, Accepted: 2 September 2004, Published online: 13 January 2005The work presented in this paper was supported (in part) by the National Competence Center in Research on Mobile Information and Communication Systems (NCCR-MICS), a center supported by the Swiss National Science Foundation under grant number 5005-67322. 相似文献
2.
The condition-based approach for consensus solvability consists of identifying sets of input vectors, called conditions, for which there exists an asynchronous protocol solving consensus despite the occurrence of up to f process crashes. This paper investigates
, the largest set of conditions which allow us to solve the consensus problem in an asynchronous shared memory system.The first part of the paper shows that
is made up of a hierarchy of classes of conditions,
where d is a parameter (called degree of the condition), starting with
and ending with d = 0, where
. We prove that each one is strictly contained in the previous one:
. Various properties of the hierarchy are also derived. It is shown that a class can be characterized in two equivalent but complementary ways: one is convenient for designing protocols while the other is for analyzing the class properties. The paper also defines a linear family of conditions that can be used to derive many specific conditions. In particular, for each d, two natural conditions are presented.The second part of the paper is devoted to the design of efficient condition-based protocols. A generic condition-based protocol is presented. This protocol can be instantiated with any condition C,
, and requires at most
shared memory read/write operations per process in the synchronization part of the protocol. Thus, the value (f-d) represents the difficulty of the class
. An improvement of the protocol for the conditions in
is also presented.Received: 15 November 2001, Accepted: 15 April 2003, Published online: 6 February 2004Parts of it have previously appeared in [23] and [25]. 相似文献
3.
4.
A graph G with n vertices and maximum degree
cannot be given weak sense of direction using less than
colours. It is known that n colours are always sufficient, and it was conjectured that just
are really needed, that is, one more colour is sufficient. Nonetheless, it has been shown [3] that for sufficiently large n there are graphs requiring
more colours than
. In this paper, using recent results in asymptotic graph enumeration, we show that (surprisingly) the same bound holds for regular graphs. We also show that
colours are necessary, where d
G
is the degree of G.Received: April 2002, Accepted: April 2003, Sebastiano Vigna: Partially supported by the Italian MURST (Finanziamento di iniziative di ricerca diffusa condotte da parte di giovani ricercatori).The results of this paper appeared in a preliminary form in Distributed Computing. 14th International Conference, DISC 2000, Springer-Verlag, 2000. 相似文献
5.
6.
In 1999 Nakano, Olariu, and Schwing in [20], they showed that the permutation routing of n items pretitled on a mobile ad hoc network (MANET for short) of p stations (p known) and k channels (MANET{(n, p, k)) with k < p, can be carried out in
broadcast rounds if k p and if each station has a
-memory locations. And if k
and if each station has a
-memory locations, the permutations of these n pretitled items can be done also in
broadcast rounds. They used two assumptions: first they suppose that each station of the mobile ad hoc network has an identifier beforehand. Secondly, the stations are partitioned into k groups such that each group has
stations, but it was not shown how this partition can be obtained. In this paper, the stations have not identifiers beforehand and p is unknown. We develop a protocol which first names the stations, secondly gives the value of p, and partitions stations in groups of
stations. Finally we show that the permutation routing problem can be solved on it in
broadcast rounds in the worst case. It can be solved in
broadcast rounds in the better case. Note that our approach does not impose any restriction on k. 相似文献
7.
We give a complete characterization of the complexity of the element distinctness problem for n elements of
bits each on deterministic and nondeterministic one-tape Turing machines. We present an algorithm running in time
for deterministic machines and nondeterministic solutions that are of time complexity
. For elements of logarithmic size
, on nondeterministic machines, these results close the gap between the known lower bound
and the previous upper bound
. Additional lower bounds are given to show that the upper bounds are optimal for all other possible relations between m and n. The upper bounds employ hashing techniques, while the lower bounds make use of the communication complexity of set disjointness.Received: 23 April 2001, Published online: 2 September 2003Holger Petersen: Supported by Deutsche Akademie der Naturforscher Leopoldina, grant number BMBF-LPD 9901/8-1 of Bundesministerium für Bildung und Forschung. 相似文献
8.
Klaus Meer 《Theory of Computing Systems》2007,41(1):107-118
In [10] it was recently shown that
that is the existence of transparent long proofs for
was established. The latter denotes the class of real number decision problems verifiable in polynomial time as introduced
by Blum et al. [6]. The present paper is devoted to the question what impact a potential full real number
theorem
would have on approximation issues in the BSS model of computation. We study two natural optimization problems in the BSS
model. The first, denoted by MAX-QPS, is related to polynomial systems; the other, MAX-q-CAP, deals with algebraic circuits.
Our main results combine the PCP framework over
with approximation issues for these two problems. We also give a negative approximation result for a variant of the MAX-QPS
problem. 相似文献
9.
10.
Coupling and self-stabilization 总被引:1,自引:0,他引:1
A randomized self-stabilizing algorithm
is an algorithm that, whatever the initial configuration is, reaches a set
of М legal configurations} in finite time with probability 1. The proof of convergence towards
is generally done by exhibiting a potential function
, which measures the “vertical” distance of any configuration to
, such that
decreases with non-null probability at each step of
. We propose here a method, based on the notion of coupling, which makes use of a “horizontal” distance
between any pair of configurations, such that
decreases in expectation at each step of
. In contrast with classical methods, our coupling method does not require the knowledge of
. In addition to the proof of convergence, the method allows us to assess the convergence rate according to two different
measures. Proofs produced by the method are often simpler or give better upper bounds than their classical counterparts, as
examplified here on Herman's mutual exclusion and Iterated Prisoner's Dilemma algorithms in the case of cyclic graphs. 相似文献
11.
Joviša Žunić 《Journal of Mathematical Imaging and Vision》2004,21(3):199-204
A digital disc is defined as the set of all integer points inside of a given real disc. In this paper we show that there are no more than
different (up to translations) digital discs consisting of n points. 相似文献
12.
Abstract We obtain a multivariate extension of a classical result of Schoenberg on cardinal spline interpolation. Specifically, we
prove the existence of a unique function in
, polyharmonic of order p on each strip
,
, and periodic in its last n variables, whose restriction to the parallel hyperplanes
,
, coincides with a prescribed sequence of n-variate periodic data functions satisfying a growth condition in
. The constructive proof is based on separation of variables and on Micchelli’s theory of univariate cardinal
-splines.
Keywords: cardinal
-splines, polyharmonic functions, multivariable interpolation
Mathematics Subject Classification (2000): 41A05, 41A15, 41A63 相似文献
13.
We study the problem of computing the k maximum sum subsequences. Given a sequence of real numbers
and an integer parameter k,
the problem involves finding the k largest values of
for
The problem for fixed k = 1, also known as the maximum sum subsequence problem, has received much attention in the literature
and is linear-time solvable. Recently, Bae and Takaoka presented a
-time algorithm for the k maximum sum subsequences problem. In this paper we design an efficient algorithm that solves the
above problem in
time in the worst case. Our algorithm is optimal for
and improves over the previously best known result for any value of the user-defined parameter k < 1. Moreover, our results
are also extended to the multi-dimensional versions of the k maximum sum subsequences problem; resulting in fast algorithms
as well. 相似文献
14.
Hongzhong Wu 《Acta Informatica》1994,31(3):285-299
This paper presents a new approach to construct a smalln-column 0, 1-matrix for two given integersn andk(k, such that everyk-column projection contains all 2
k
possible row vectors, namely surjective on {0, 1}
k
. The number of the matrix's rows does not exceed
. This approach has considerable advantage for smallk and practical sizes ofn. It can be applied to the test generation of VLSI circuits, the design of fault tolerant systems and other fields. 相似文献
15.
N. N. Tokareva 《Problems of Information Transmission》2005,41(2):113-124
A binary code is called ℤ4-linear if its quaternary Gray map preimage is linear. We show that the set of all quaternary linear Preparata codes of length n = 2m, m odd, m ≥ 3, is nothing more than the set of codes of the form
with
where T
λ(⋅) and S
ψ (⋅) are vector fields of a special form defined over the binary extended linear Hamming code H
n
of length n. An upper bound on the number of nonequivalent quaternary linear Preparata codes of length n is obtained, namely,
. A representation for binary Preparata codes contained in perfect Vasil’ev codes is suggested.__________Translated from Problemy Peredachi Informatsii, No. 2, 2005, pp. 50–62.Original Russian Text Copyright © 2005 by Tokareva.Supported in part by the Ministry of Education of the Russian Federation program “Development of the Scientific Potential of the Higher School,” project no. 512. 相似文献
16.
We consider asynchronous consensus in the shared-memory setting. We present the first efficient low-contention consensus algorithm for the weak-adversary-scheduler model. The algorithm achieves consensus in
total work and
(hot-spot) contention, both expected and with high probability. The algorithm assumes the value-oblivious scheduler, which is defined in the paper. Previous efficient consensus algorithms for weak adversaries suffer from
memory contention.Yonatan Aumann: This work was partially completed while theauthor was at Harvard University, supported in part by ONRcontract ONR-N00014-91-J-1981.Michael A. Bender: This work was supported inpart by HRL Laboratories, Sandia National Laboratories, and NSF GrantsACI-032497, CCR-0208670, and EIA-0112849. This work was partiallycompleted while the author was at Harvard University, supported inpart by NSF grants CCR-9700365, CCR-9504436, and CCR-9313775.An early version of this paper was presented in the 23rd International Colloquium on Automata, Languages, and Programming (ICALP 96) [8]. 相似文献
17.
18.
We present new baby steps/giant steps algorithms of asymptotically fast running time for dense matrix problems. Our algorithms compute the determinant, characteristic polynomial, Frobenius normal form and Smith normal form of a dense n × n matrix A with integer entries in
and
bit operations; here
denotes the largest entry in absolute value and the exponent adjustment by +o(1) captures additional factors
for positive real constants C1, C2, C3. The bit complexity
results from using the classical cubic matrix multiplication algorithm. Our algorithms are randomized, and we can certify that the output is the determinant of A in a Las Vegas fashion. The second category of problems deals with the setting where the matrix A has elements from an abstract commutative ring, that is, when no divisions in the domain of entries are possible. We present algorithms that deterministically compute the determinant, characteristic polynomial and adjoint of A with n3.2+o(1) and O(n2.697263) ring additions, subtractions and multiplications.To B. David Saunders on the occasion of his 60th birthday 相似文献
19.
We present approximation algorithms for the unsplittable flow problem (UFP) in undirected graphs. As is standard in this line
of research, we assume that the maximum
demand is at most the minimum capacity. We focus on the non-uniform capacity case in which the edge capacities can vary arbitrarily
over the graph. Our results are:
We obtain an
approximation ratio for UFP, where n is the number of vertices,
is the maximum degree, and
is the expansion of the graph. Furthermore, if we specialize to the case where all edges have the same capacity, our algorithm
gives an
approximation.
For certain strong constant-degree expanders considered by we obtain an
approximation for the uniform capacity case.
For UFP on the line and the ring, we give the first constant-factor approximation algorithms.
All of the above results improve if the maximum demand is bounded away from the minimum capacity. The above results either
improve upon or
are incomparable with previously known results for these problems. The main technique used for these results is randomized
rounding followed by greedy alteration, and is inspired by the use of this idea in recent work. 相似文献
20.
Unambiguity in alternating Turing machines has received considerable attention in the context of analyzing globally unique
games by Aida et al. [ACRW] and in the design of efficient protocols involving globally unique games by Crasmaru et al. [CGRS].
This paper explores the power of unambiguity in alternating Turing machines in the following settings: 1. We show that unambiguity-based
hierarchies-AUPH, UPH, and UPH-are infinite in some relativized world. For each
, we construct another relativized world where the unambiguity-based hierarchies collapse so that they have exactly k distinct
levels and their k-th levels coincide with PSPACE. These results shed light on the relativized power of the unambiguity-based
hierarchies, and parallel the results known for the case of the polynomial hierarchy. 2. For every
, we define the bounded-level unambiguous alternating solution class UAS(k) as the class of all sets L for which there exists
a polynomial-time alternating Turing machine N, which need not be unambiguous on every input, with at most k alternations
such that
if and only if x is accepted unambiguously by N. We construct a relativized world where, for all
and
. 3. Finally, we show that robustly k-level unambiguous alternating polynomial-time Turing machines, i.e., polynomial-time
alternating Turing machines that for every oracle have k alternating levels and are unambiguous, accept languages that are
computable in
, for every oracle A. This generalizes a result of Hartmanis and Hemachandra [HH]. 相似文献