共查询到20条相似文献,搜索用时 31 毫秒
1.
Romeo Rizzi 《Algorithmica》2009,53(3):402-424
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. 相似文献
2.
Joel Ratsaby 《Annals of Mathematics and Artificial Intelligence》2008,52(1):55-65
Consider a class of binary functions h: X→{ − 1, + 1} on an interval . Define the sample width of h on a finite subset (a sample) S ⊂ X as ω
S
(h) = min
x ∈ S
|ω
h
(x)| where ω
h
(x) = h(x) max {a ≥ 0: h(z) = h(x), x − a ≤ z ≤ x + a}. Let be the space of all samples in X of cardinality ℓ and consider sets of wide samples, i.e., hypersets which are defined as Through an application of the Sauer-Shelah result on the density of sets an upper estimate is obtained on the growth function
(or trace) of the class , β > 0, i.e., on the number of possible dichotomies obtained by intersecting all hypersets with a fixed collection of samples
of cardinality m. The estimate is .
相似文献
3.
A traveling salesman game is a cooperative game
. Here N, the set of players, is the set of cities (or the vertices of the complete graph) and c
D
is the characteristic function where D is the underlying cost matrix. For all S⊆N, define c
D
(S) to be the cost of a minimum cost Hamiltonian tour through the vertices of S∪{0} where
is called as the home city. Define Core
as the core of a traveling salesman game
. Okamoto (Discrete Appl. Math. 138:349–369, [2004]) conjectured that for the traveling salesman game
with D satisfying triangle inequality, the problem of testing whether Core
is empty or not is
-hard. We prove that this conjecture is true. This result directly implies the
-hardness for the general case when D is asymmetric. We also study approximately fair cost allocations for these games. For this, we introduce the cycle cover
games and show that the core of a cycle cover game is non-empty by finding a fair cost allocation vector in polynomial time.
For a traveling salesman game, let
and ∀
S⊆N, x(S)≤ε⋅c
D
(S)} be an ε-approximate core, for a given ε>1. By viewing an approximate fair cost allocation vector for this game as a sum of exact fair cost allocation vectors of
several related cycle cover games, we provide a polynomial time algorithm demonstrating the non-emptiness of the log 2(|N|−1)-approximate core by exhibiting a vector in this approximate core for the asymmetric traveling salesman game. We improve
it further by finding a
-approximate core in polynomial time for some constant c. We also show that there exists an ε
0>1 such that it is
-hard to decide whether ε
0-Core
is empty or not.
A preliminary version of the paper appeared in the third Workshop on Approximation and Online Algorithms (WAOA), 2005. 相似文献
4.
Radio networks model wireless data communication when the bandwidth is limited to one wave frequency. The key restriction
of such networks is mutual interference of packets arriving simultaneously at a node. The many-to-many (m2m) communication
primitive involves p participant nodes from among n nodes in the network, where the distance between any pair of participants is at most d. The task is to have all the participants get to know all the input messages. We consider three cases of the m2m communication
problem. In the ad-hoc case, each participant knows only its name and the values of n, p and d. In the partially centralized case, each participant knows the topology of the network and the values of p and d, but does not know the names of the other participants. In the centralized case, each participant knows the topology of the
network and the names of all the participants. For the centralized m2m problem, we give deterministic protocols, for both
undirected and directed networks, working in
time, which is provably optimal. For the partially centralized m2m problem, we give a randomized protocol for undirected networks
working in
time with high probability (whp), and we show that any deterministic protocol requires
time. For the ad-hoc m2m problem, we develop a randomized protocol for undirected networks that works in
time whp. We show two lower bounds for the ad-hoc m2m problem. One lower bound states that any randomized protocol for the
m2m ad hoc problem requires
expected time. Another lower bound states that for any deterministic protocol for the m2m ad hoc problem, there is a network
on which the protocol requires
time when n−p(n)=Ω(n) and d>1, and that it requires Ω(n) time when n−p(n)=o(n).
The results of this paper appeared in a preliminary form in “On many-to-many communication in packet radio networks” in Proceedings
of the 10th Conference on Principles of Distributed Systems (OPODIS), Bordeaux, France, 2006, Lecture Notes in Computer Science
4305, Springer, Heidelberg, pp. 258–272.
The work of B.S. Chlebus was supported by NSF Grant 0310503. 相似文献
5.
We obtain subquadratic algorithms for 3SUM on integers and rationals in several models. On a standard word RAM with w-bit words, we obtain a running time of
. In the circuit RAM with one nonstandard AC
0 operation, we obtain
. In external memory, we achieve O(n
2/(MB)), even under the standard assumption of data indivisibility. Cache-obliviously, we obtain a running time of
. In all cases, our speedup is almost quadratic in the “parallelism” the model can afford, which may be the best possible.
Our algorithms are Las Vegas randomized; time bounds hold in expectation, and in most cases, with high probability. 相似文献
6.
Antoine Chaillet Yacine Chitour Antonio Loría Mario Sigalotti 《Mathematics of Control, Signals, and Systems (MCSS)》2008,20(2):135-156
Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, ${\int_t^{t+T}\alpha(s){\rm d}s \geq \mu}Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, . In particular, when α(t) becomes zero the system dynamics switches to an uncontrollable system. In this paper, we address the following question:
is it possible to find a linear time-invariant state-feedback u = Kx, with K only depending on (A, B) and possibly on μ, T, which globally asymptotically stabilizes the system? We give a positive answer to this question for two cases: when A is neutrally stable and when the system is the double integrator.
Notation A continuous function is of class
, if it is strictly increasing and is of class if it is continuous, non-increasing and tends to zero as its argument tends to infinity. A function is said to be a class
-function if, for any t ≥ 0, and for any s ≥ 0. We use |·| for the Euclidean norm of vectors and the induced L
2-norm of matrices. 相似文献
7.
We study the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication)
in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed based on full
knowledge about the size and the topology of the network. We show that gossiping can be completed in
time units in any radio network of size n, diameter D, and maximum degree Δ=Ω(log n). This is an almost optimal schedule in the sense that there exists a radio network topology, specifically a Δ-regular tree, in which the radio gossiping cannot be completed in less than
units of time. Moreover, we show a
schedule for the broadcast task. Both our transmission schemes significantly improve upon the currently best known schedules
by Gąsieniec, Peleg, and Xin (Proceedings of the 24th Annual ACM SIGACT-SIGOPS PODC, pp. 129–137, 2005), i.e., a O(D+Δlog n) time schedule for gossiping and a D+O(log 3
n) time schedule for broadcast. Our broadcasting schedule also improves, for large D, a very recent O(D+log 2
n) time broadcasting schedule by Kowalski and Pelc.
A preliminary version of this paper appeared in the proceedings of ISAAC’06.
F. Cicalese supported by the Sofja Kovalevskaja Award 2004 of the Alexander von Humboldt Stiftung. F. Manne and Q. Xin supported
by the Research Council of Norway through the SPECTRUM project. 相似文献
8.
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.
A preliminary version of this paper appeared in Proc. 18th Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 4–15,
2007.
Y. Lifshits’ research was supported by the Center for the Mathematics of Information and the Lee Center for Advanced Networking.
S. Mozes’ work conducted while visiting MIT. 相似文献
9.
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.
An extended abstract of this paper appeared in Proceedings of the 14th Annual European Symposium on Algorithms, 2006.
This work is part of D. Segev’s Ph.D. thesis prepared at Tel-Aviv University under the supervision of Prof. Refael Hassin. 相似文献
10.
We consider the problem of approximately integrating a Lipschitz function f (with a known Lipschitz constant) over an interval. The goal is to achieve an additive error of at most ε using as few samples of f as possible. We use the adaptive framework: on all problem instances an adaptive algorithm should perform almost as well
as the best possible algorithm tuned for the particular problem instance. We distinguish between
and
, the performances of the best possible deterministic and randomized algorithms, respectively. We give a deterministic algorithm
that uses
samples and show that an asymptotically better algorithm is impossible. However, any deterministic algorithm requires
samples on some problem instance. By combining a deterministic adaptive algorithm and Monte Carlo sampling with variance reduction,
we give an algorithm that uses at most
samples. We also show that any algorithm requires
samples in expectation on some problem instance (f,ε), which proves that our algorithm is optimal. 相似文献
11.
We consider the problem of finding a stable matching of maximum size when both ties and unacceptable partners are allowed
in preference lists. This problem is NP-hard and the current best known approximation algorithm achieves the approximation
ratio 2−c(log N)/N, where c is an arbitrary positive constant and N is the number of men in an input. In this paper, we improve the ratio to
, where c is an arbitrary constant that satisfies
.
A preliminary version of this paper was presented at the 16th Annual International Symposium on Algorithms and Computation,
ISAAC 2005. 相似文献
12.
Jiří Močkoř 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2009,13(6):591-596
We investigate interpretations of formulas ψ in a first order fuzzy logic in models which are based on objects of a category SetR(Ω) which consists of Ω-sets, i.e. sets with similarity relations with values in a complete MV-algebra Ω and with morphisms
defined as special fuzzy relations between Ω-sets. The interpretations are then morphisms in a category SetR(Ω) from some Ω-set to the object . We define homomorphisms between models in a category SetR(Ω) and we prove that if is a (special) homomorphism of models in a category SetR(Ω) then there is a relation between interpretations of a formula ψ in models .
Supported by MSM6198898701, grant 201/07/0191 of GAČR and grant 1M0572. 相似文献
13.
It is proved that “FIFO” worksharing protocols provide asymptotically optimal solutions to two problems related to sharing
large collections of independent tasks in a heterogeneous network of workstations (HNOW)
. In the
, one seeks to accomplish as much work as possible on
during a prespecified fixed period of L time units. In the
, one seeks to complete W units of work by “renting”
for as short a time as necessary. The worksharing protocols we study are crafted within an architectural model that characterizes
via parameters that measure
’s workstations’ computational and communicational powers. All valid protocols are self-scheduling, in the sense that they determine completely both an amount of work to allocate to each of
’s workstations and a schedule for all related interworkstation communications. The schedules provide either a value for W given L, or a value for L given W, hence solve both of the motivating problems. A protocol observes a FIFO regimen if it has
’s workstations finish their assigned work, and return their results, in the same order in which they are supplied with their
workloads. The proven optimality of FIFO protocols resides in the fact that they accomplish at least as much work as any other
protocol during all sufficiently long worksharing episodes, and that they complete sufficiently large given collections of
tasks at least as fast as any other protocol. Simulation experiments illustrate that the superiority of FIFO protocols is
often observed during worksharing episodes of only a few minutes’ duration.
A portion of this research was presented at the 15th ACM Symp. on Parallelism in Algorithms and Architectures (2003). 相似文献
14.
Avram Sidi 《Journal of scientific computing》2007,31(3):391-417
Variable transformations for numerical integration have been used for improving the accuracy of the trapezoidal rule. Specifically,
one first transforms the integral via a variable transformation that maps [0,1] to itself, and then approximates the resulting transformed integral by the trapezoidal rule. In this work, we propose a new class of symmetric and nonsymmetric variable transformations which
we denote , where r and s are positive scalars assigned by the user. A simple representative of this class is . We show that, in case , or but has algebraic (endpoint) singularities at x = 0 and/or x = 1, the trapezoidal rule on the transformed integral produces exceptionally high accuracies for special values of r and s. In particular, when and we employ , the error in the approximation is (i) O(h
r
) for arbitrary r and (ii) O(h
2r
) if r is a positive odd integer at least 3, h being the integration step. We illustrate the use of these transformations and the accompanying theory with numerical examples.
相似文献
15.
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.
W. Jawor and M. Chrobak supported by NSF grants OISE-0340752 and CCR-0208856.
Work of C. Dürr conducted while being affiliated with the Laboratoire de Recherche en Informatique, Université Paris-Sud,
91405 Orsay. Supported by the CNRS/NSF grant 17171 and ANR Alpage. 相似文献
16.
Chvátal-Gomory cuts are among the most well-known classes of cutting planes for general integer linear programs (ILPs). In
case the constraint multipliers are either 0 or
, such cuts are known as
-cuts. It has been proven by Caprara and Fischetti (Math. Program. 74:221–235, 1996) that separation of
-cuts is
-hard.
In this paper, we study ways to separate
-cuts effectively in practice. We propose a range of preprocessing rules to reduce the size of the separation problem. The
core of the preprocessing builds a Gaussian elimination-like procedure. To separate the most violated
-cut, we formulate the (reduced) problem as integer linear program. Some simple heuristic separation routines complete the
algorithmic framework.
Computational experiments on benchmark instances show that the combination of preprocessing with exact and/or heuristic separation
is a very vital idea to generate strong generic cutting planes for integer linear programs and to reduce the overall computation
times of state-of-the-art ILP-solvers. 相似文献
17.
Tomasz Jurdziński Friedrich Otto František Mráz Martin Plátek 《Theory of Computing Systems》2008,42(4):488-518
The
-automaton is the weakest form of the nondeterministic version of the restarting automaton that was introduced by Jančar et al. to model the so-called analysis by reduction. Here it is shown that the class ℒ(R) of languages that are accepted by
-automata is incomparable under set inclusion to the class
of Church-Rosser languages and to the class
of growing context-sensitive languages. In fact this already holds for the class
of languages that are accepted by 2-monotone
-automata. In addition, we prove that already the latter class contains
-complete languages, showing that already the 2-monotone
-automaton has a surprisingly large expressive power.
The results of this paper have been announced at DLT 2004 in Auckland, New Zealand.
This work was mainly carried out while T. Jurdziński was visiting the University of Kassel, supported by a grant from the
Deutsche Forschungsgemeinschaft (DFG).
F. Mráz and M. Plátek were partially supported by the Grant Agency of the Czech Republic under Grant-No. 201/04/2102 and by
the program ‘Information Society’ under project 1ET100300517. F. Mráz was also supported by the Grant Agency of Charles University
in Prague under Grant-No. 358/2006/A-INF/MFF. 相似文献
18.
We consider labelled r-uniform hypertrees, 2≤r≤n, where n is the number of vertices in the hypertree. Any two hyperedges in a hypertree share at most one vertex and each hyperedge
in an r-uniform hypertree contains exactly r vertices. We show that r-uniform hypertrees can be encoded in linear time using as little as n−2 integers in the range [1,n]. The decoding algorithm also runs in linear time. For general hypertrees, we require codes of length n+p−2 where p is the number of vertices belonging to more than one hyperedge in the given hypertree. Based on our coding technique, we
show that there are at most
distinct labelled r-uniform hypertrees, where f(n,r) is a lower bound on the number of labelled trees with maximum (vertex) degree exceeding
. We suggest a counting scheme for determining such a lower bound f(n,r). 相似文献
19.
A caterpillar is a tree in which all vertices of degree three or more lie on one path, called the backbone. We present a polynomial
time algorithm that produces a linear arrangement of the vertices of a caterpillar with bandwidth at most O(log n/log log n) times the local density of the caterpillar, where the local density is a well known lower bound on the bandwidth. This result is best possible in
the sense that there are caterpillars whose bandwidth is larger than their local density by a factor of Ω(log n/log log n). The previous best approximation ratio for the bandwidth of caterpillars was O(log n). We show that any further improvement in the approximation ratio would require using linear arrangements that do not respect
the order of the vertices of the backbone.
We also show how to obtain a (1+ε) approximation for the bandwidth of caterpillars in time
. This result generalizes to trees, planar graphs, and any family of graphs with treewidth
. 相似文献
20.
We present an algorithm that takes
I/Os (sort(N)=Θ((N/(DB))log
M/B
(N/B)) is the number of I/Os it takes to sort N data items) to compute a tree decomposition of width at most k, for any graph G of treewidth at most k and size N, where k is a constant. Given such a tree decomposition, we use a dynamic programming framework to solve a wide variety of problems
on G in
I/Os, including the single-source shortest path problem and a number of problems that are NP-hard on general graphs. The tree
decomposition can also be used to obtain an optimal separator decomposition of G. We use such a decomposition to perform depth-first search in G in
I/Os.
As important tools that are used in the tree decomposition algorithm, we introduce flippable DAGs and present an algorithm that computes a perfect elimination ordering of a k-tree in
I/Os.
The second contribution of our paper, which is of independent interest, is a general and simple framework for obtaining I/O-efficient
algorithms for a number of graph problems that can be solved using greedy algorithms in internal memory. We apply this framework
in order to obtain an improved algorithm for finding a maximal matching and the first deterministic I/O-efficient algorithm
for finding a maximal independent set of an arbitrary graph. Both algorithms take
I/Os. The maximal matching algorithm is used in the tree decomposition algorithm.
An abstract of this paper was presented at the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, pp. 89–90,
2001.
Research of A. Maheshwari supported by NSERC.
Part of this work was done while the second author was a Ph.D. student at the School of Computer Science of Carleton University. 相似文献