共查询到20条相似文献,搜索用时 31 毫秒
1.
E. A. Ramos 《Discrete and Computational Geometry》1996,15(2):147-167
We consider the problem of determining the smallest dimensiond=Δ(j, k) such that, for anyj mass distributions inR
d
, there arek hyperplanes so that each orthant contains a fraction 1/2
k
of each of the masses. The case Δ(1,2)=2 is very well known. The casek=1 is answered by the ham-sandwich theorem with Δ(j, 1)=j. By using mass distributions on the moment curve the lower bound Δ(j, k)≥j(2
k
−1)/k is obtained. We believe this is a tight bound. However, the only general upper bound that we know is Δ(j, k)≤j2
k−1. We are able to prove that Δ(j, k)=⌈j(2k−1/k⌉ for a few pairs (j, k) ((j, 2) forj=3 andj=2
n
withn≥0, and (2, 3)), and obtain some nontrivial bounds in other cases. As an intermediate result of independent interest we prove
a Borsuk-Ulam-type theorem on a product of balls. The motivation for this work was to determine Δ(1, 4) (the only case forj=1 in which it is not known whether Δ(1,k)=k); unfortunately the approach fails to give an answer in this case (but we can show Δ(1, 4)≤5).
This research was supported by the National Science Foundation under Grant CCR-9118874. 相似文献
2.
Lovász, Saks, and Trotter showed that there exists an on-line algorithm which will color any on-linek-colorable graph onn vertices withO(nlog(2k–3)
n/log(2k–4)
n) colors. Vishwanathan showed that at least (log
k–1
n/k
k
) colors are needed. While these remain the best known bounds, they give a distressingly weak approximation of the number of colors required. In this article we study the case of perfect graphs. We prove that there exists an on-line algorithm which will color any on-linek-colorable perfect graph onn vertices withn
10k/loglogn
colors and that Vishwanathan's techniques can be slightly modified to show that his lower bound also holds for perfect graphs. This suggests that Vishwanathan's lower bound is far from tight in the general case.Research partially supported by Office of Naval Research grant N00014-90-J-1206. 相似文献
3.
T. Lengyel 《P-Adic Numbers, Ultrametric Analysis, and Applications》2012,4(3):179-186
We analyze some 2-adic properties of the sequence defined by the recurrence Z(1) = 1; Z(n) = Σ k=1 n−1 S(n, k)Z(k), n ≥ 2, which counts the number of ultradissimilarity relations, i.e., ultrametrics on an n-set. We prove the 2-adic growth property ν 2(Z(n)) ≥ ⌈log2 n⌉ −1 and present conjectures on the exact values. 相似文献
4.
Tomasz Radzik 《Mathematical Programming》1996,78(1):43-58
In this paper we consider an optimization version of the multicommodity flow problem which is known as the maximum concurrent
flow problem. We show that an approximate solution to this problem can be computed deterministically using O(k(ε
−2 + logk) logn) 1-commodity minimum-cost flow computations, wherek is the number of commodities,n is the number of nodes, andε is the desired precision. We obtain this bound by proving that in the randomized algorithm developed by Leighton et al. (1995)
the random selection of commodities can be replaced by the deterministic round-robin without increasing the total running
time. Our bound significantly improves the previously known deterministic upper bounds and matches the best known randomized
upper bound for the approximation concurrent flow problem.
A preliminary version of this paper appeared inProceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, San Francisco CA, 1995, pp. 486–492. 相似文献
5.
1.IntroductionLetG=(V,E,W)beaconnected,weightedandundirectedgraph,VeEE,w(e)(相似文献
6.
Pravin M. Vaidya 《Discrete and Computational Geometry》1991,6(1):369-381
A setV ofn points ink-dimensional space induces a complete weighted undirected graph as follows. The points are the vertices of this graph and
the weight of an edge between any two points is the distance between the points under someL
p metric. Let ε≤1 be an error parameter and letk be fixed. We show how to extract inO(n logn+ε
−k
log(1/ε)n) time a sparse subgraphG=(V, E) of the complete graph onV such that: (a) for any two pointsx, y inV, the length of the shortest path inG betweenx andy is at most (1+∈) times the distance betweenx andy, and (b)|E|=O(ε−k
n). 相似文献
7.
Raphael Yuster 《Order》2003,20(2):121-133
Let TT
k
denote the transitive tournament on k vertices. Let TT(h,k) denote the graph obtained from TT
k
by replacing each vertex with an independent set of size h≥1. The following result is proved: Let c
2=1/2, c
3=5/6 and c
k
=1−2−k−log k
for k≥4. For every ∈>0 there exists N=N(∈,h,k) such that for every undirected graph G with n>N vertices and with δ(G)≥c
k
n, every orientation of G contains vertex disjoint copies of TT(h,k) that cover all but at most ∈n vertices. In the cases k=2 and k=3 the result is asymptotically tight. For k≥4, c
k
cannot be improved to less than 1−2−0.5k(1+o(1)).
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
8.
Moshe Katz 《Israel Journal of Mathematics》1971,9(1):53-72
Let ℬ(m) be the set of all then-square (0–1) matrices containingm ones andn
2−m zeros, 0<m<n
2. The problem of finding the maximum ofs(A
2) over this set, wheres(A
2) is the sum of the entries ofA
2,A ∈ ℬ (m) is considered. This problem is solved in the particular casesm=n
2 −k
2 andm=k
2,k
2>(n
2/2).
This paper forms part of a thesis in partial fulfillment of the requirements for the degree of Doctor of Science at the Technion-Israel
Institute of Technology. The author wishes to thank Professor B. Schwarz and Dr. D. London for their help in the preparation
of this paper. 相似文献
9.
Jin Kue Wong 《BIT Numerical Mathematics》1981,21(2):157-166
The theoretical presentation and analysis is given for two families of simple in-place merging algorithms and their limiting cases. The first family merges stably inO(k·n) time andO(n
1/k
) additional space with a limiting case running inO(n logn) time and constant space. The second family merges unstably inO (k ·n) time andO(log
k
n) space with a limiting case running inO(nG(n)) time and constant space. HereG(n) is the leastk such thatF(k) n whereF(0)=1 andF(i)=2
F(i–1) fori1. Each algorithm gives rise to a corresponding merge sort. 相似文献
10.
Pankaj K. Agarwal Herbert Edelsbrunner Otfried Schwarzkopf Emo Welzl 《Discrete and Computational Geometry》1991,6(1):407-422
We present an algorithm to compute a Euclidean minimum spanning tree of a given setS ofN points inE
d
in timeO(F
d
(N,N) log
d
N), whereF
d
(n,m) is the time required to compute a bichromatic closest pair amongn red andm green points inE
d
. IfF
d
(N,N)=Ω(N
1+ε), for some fixed ɛ>0, then the running time improves toO(F
d
(N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected timeO((nm logn logm)2/3+m log2
n+n log2
m) inE
3, which yields anO(N
4/3 log4/3
N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE
3. Ind≥4 dimensions we obtain expected timeO((nm)1−1/([d/2]+1)+ε+m logn+n logm) for the bichromatic closest pair problem andO(N
2−2/([d/2]+1)ε) for the Euclidean minimum spanning tree problem, for any positive ɛ.
The first, second, and fourth authors acknowledge support from the Center for Discrete Mathematics and Theoretical Computer
Science (DIMACS), a National Science Foundation Science and Technology Center under NSF Grant STC 88-09648. The second author's
work was supported by the National Science Foundation under Grant CCR-8714565. The third author's work was supported by the
Deutsche Forschungsgemeinschaft under Grant A1 253/1-3, Schwerpunktprogramm “Datenstrukturen und effiziente Algorithmen”.
The last two authors' work was also partially supported by the ESPRIT II Basic Research Action of the EC under Contract No.
3075 (project ALCOM). 相似文献
11.
Let n = (p − 1) · p
k
, where p is a prime number such that 2 is a primitive root modulo p, and 2
p−1 − 1 is not a multiple of p
2. For a standard basis of the field GF(2
n
), a multiplier of complexity O(log log p)n log n log log
p
n and an inverter of complexity O(log p log log p)n log n log log
p
n are constructed. In particular, in the case p = 3 the upper bound
$
5\frac{5}
{8}n\log _3 n\log _2 \log _3 n + O(n\log n)
$
5\frac{5}
{8}n\log _3 n\log _2 \log _3 n + O(n\log n)
相似文献
12.
Vito Lampret 《Central European Journal of Mathematics》2012,10(2):775-787
An asymptotic approximation of Wallis’ sequence W(n) = Π
k=1
n
4k
2/(4k
2 − 1) obtained on the base of Stirling’s factorial formula is presented. As a consequence, several accurate new estimates
of Wallis’ ratios w(n) = Π
k=1
n
(2k−1)/(2k) are given. Also, an asymptotic approximation of π in terms of Wallis’ sequence W(n) is obtained, together with several double inequalities such as, for example,
|
设为首页 | 免责声明 | 关于勤云 | 加入收藏 |
Copyright©北京勤云科技发展有限公司 京ICP备09084417号 |