共查询到20条相似文献,搜索用时 31 毫秒
1.
A note on hierarchical scheduling on two uniform machines 总被引:1,自引:0,他引:1
This paper studies online hierarchical scheduling on two uniform machines with the objective to minimize makespan. Machines
are provided with different capability, i.e., the one with speed s can schedule all jobs, while the other one with speed 1 can only process partial jobs. Optimal algorithms for any 0<s<∞ are given in the paper. For 0<s<1, it has a competitive ratio of
min{1+s,1+\frac1+s1+s+s2}\min\{1+s,1+\frac{1+s}{1+s+s^{2}}\}
. For s>1, the competitive ratio is
min{\frac1+ss,1+\frac2s1+s+s2}\min\{\frac{1+s}{s},1+\frac{2s}{1+s+s^{2}}\}
. 相似文献
2.
Motivated by the existence of an APTAS (Asymptotic PTAS) for bin packing problem, we consider the batch scheduling problem
with nonidentical job sizes to minimize makespan. For the proportional special version, i.e., there exists a fixed number
α such that p
j
=α
s
j
for every 1≤j≤n, we first present a lower bound of 3/2 for the approximation ratio and then design an APTAS.
Supported by NNSF of China (No.10671108). 相似文献
3.
Weijia Jia Hanxing Wang Wanqing Tu Wei Zhao 《Journal of Combinatorial Optimization》2006,12(1-2):127-149
This paper presents a novel control algorithm to decrease the worst-case delay bound for high rate homogeneous and heterogeneous
real-time flows when the network traffic load becomes heavy. The algorithm is adaptive based on the instantaneous network
situations. It employs a generalized form of traditional (σ,ρ) regulator called the generalized (σ,ρ,λ) regulator that operates
like the (σ,ρ) regulator under the normal network traffic load situation, but provides more regulations for the heavy network
traffic load situation. For a set of real-time flows, we can show that D
rg
≤D
g
where D
rg
and D
g
are the worst-case delay bounds with the (σ,ρ,λ) regulator and the (σ,ρ) regulator respectively. More specifically, we have
developed a set of formulas to set the parameters for the new regulator so as to reduce the worst-case delay bounds for the
real-time flows. We can prove that there exists a threshold input rate ρ* such that D
rg
= D
g
for ρ≤ρ* and D
rg
< D
g
for ρ > ρ*. When the average input rate of real-time flows is very high, the generalized regulator can effectively control the delay.
The extensive experiment data match our theoretical results.
The part of this paper has been appeared in The 23
rd
IEEE International Conference on Distributed Computing Systems, 2003. The work is supported by CityU strategic grant Nos: 7001777 and 7001709 and CityU ARP Project No. 9610027. H. Wang
was partially supported by National Natural Science Foundation of China (10471088, 60572126) and CityU strategic grant no.
7001709. Wanqing Tu is now with Department of Computer Science, The Hong Kong University of Science and Technology. Clear
Water Bay, New Territories, Kowloon, Hong Kong. 相似文献
4.
Energy efficient multicast problem is one of important issues in ad hoc networks. In this paper, we address the energy efficient
multicast problem for discrete power levels in ad hoc wireless networks. The problem of our concern is: given n nodes deployed over 2-D plane and each node v has l(v) transmission power levels and a multicast request (s,D) (clearly, when D is V∖{s}, the multicast request is a broadcast request), how to find a multicast tree rooted at s and spanning all destinations in D such that the total energy cost of the multicast tree is minimized. We first prove that this problem is NP-hard and it is
unlikely to have an approximation algorithm with performance ratio ρlnn(ρ<1). Then, we propose a general algorithm for the multicast/broadcast tree problem. And based on the general algorithm, we
propose an approximation algorithm and a heuristics for multicast tree problem. Especially, we also propose an efficient heuristic
for broadcast tree problem. Simulations ensure our algorithms are efficient. 相似文献
5.
在很多市场环境中,消费者喜欢尝试不同产品的特性,重复消费同一商品会产生滞留成本。本文通过构建两期动态博弈模型,研究了滞留成本对企业折扣券定价行为的影响,并与其他定价策略的市场绩效进行了比较。本文研究结果表明:(1)企业会通过折扣券奖励忠诚的消费者,即企业会对重复购买自己产品的消费者给予价格优惠,而对新消费者制定高价格;(2)在均衡中,随着滞留成本的提升,消费者剩余和社会总福利降低,企业利润上升;(3)与其他定价机制相比较,折扣券定价策略下的社会总福利较低,政策制定者应当限制此类策略的应用。 相似文献
6.
We consider some inverse min-max (or max-min) network problems. Such an inverse problem is to modify the weights with bound
constraints so that a given feasible solution becomes an optimal solution of a min-max (or max-min) network problem, and the
deviation of the weights, measured by the weighted l
1 norm or weighted l
∞ norm, is minimum. In this paper, we present strongly polynomial time algorithms to solve the inverse min-max spanning tree
problem and the inverse maximum capacity path problem. 相似文献
7.
In this paper, we present a combinatorial theorem on labeling disjoint axis-parallel squares of edge length two using points.
Given an arbitrary set of disjoint axis-parallel squares of edge length two, we show that if we label points on the boundary
of all squares (one for each square) and define a distance label graph such that there is an edge between any two labeling
points if and only if their L∞-distance is at most 1 − ε (0 < ε < 1), then the maximum connected component of the graph contains Θ(1/ε) vertices, which is tight. With this theorem we present a new and simple factor-(3 + ε) approximation for labeling points with axis-parallel squares under the slider model.
This research is supported by NSF CARGO Grant DMS-0138065. 相似文献
8.
A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The maximum cardinality of a minimal paired-dominating set of G is the upper paired-domination number of G, denoted by Γpr(G). We establish bounds on Γpr(G) for connected claw-free graphs G in terms of the number n of vertices in G with given minimum degree δ. We show that Γpr(G)≤4n/5 if δ=1 and n≥3, Γpr(G)≤3n/4 if δ=2 and n≥6, and Γpr(G)≤2n/3 if δ≥3. All these bounds are sharp. Further, if n≥6 the graphs G achieving the bound Γpr(G)=4n/5 are characterized, while for n≥9 the graphs G with δ=2 achieving the bound Γpr(G)=3n/4 are characterized. 相似文献
9.
On minimum <Emphasis Type="Italic">m</Emphasis>-connected <Emphasis Type="Italic">k</Emphasis>-dominating set problem in unit disc graphs 总被引:1,自引:1,他引:0
Weiping Shang Frances Yao Pengjun Wan Xiaodong Hu 《Journal of Combinatorial Optimization》2008,16(2):99-106
Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset S⊆V of minimal size such that every vertex in V∖S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation
algorithms with constant performance ratios for m≤2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m.
This work was supported in part by the Research Grants Council of Hong Kong under Grant No. CityU 1165/04E, the National Natural
Science Foundation of China under Grant No. 70221001, 10531070 and 10771209. 相似文献
10.
We consider the scheduling of n family jobs with release dates on m identical parallel batching machines. Each batching machine can process up to b jobs simultaneously as a batch. In the bounded model, b<n, and in the unbounded model, b=∞. Jobs from different families cannot be placed in the same batch. The objective is to minimize the maximum completion time
(makespan). When the number of families is a constant, for both bounded model and unbounded model, we present polynomial-time
approximation schemes (PTAS). 相似文献
11.
Finding an anti-risk path between two nodes in undirected graphs 总被引:1,自引:0,他引:1
Given a weighted graph G=(V,E) with a source s and a destination t, a traveler has to go from s to t. However, some of the edges may be blocked at certain times, and the traveler only observes that upon reaching an adjacent
site of the blocked edge. Let ℘={P
G
(s,t)} be the set of all paths from s to t. The risk of a path is defined as the longest travel under the assumption that any edge of the path may be blocked. The paper
will propose the Anti-risk Path Problem of finding a path P
G
(s,t) in ℘ such that it has minimum risk. We will show that this problem can be solved in O(mn+n
2log n) time suppose that at most one edge may be blocked, where n and m denote the number of vertices and edges in G, respectively.
This research is supported by NSF of China under Grants 70525004, 60736027, 70121001 and Postdoctoral Science Foundation of
China under Grant 20060401003. 相似文献
12.
Tz-Liang Kueng Cheng-Kuan Lin Tyne Liang Jimmy J. M. Tan Lih-Hsing Hsu 《Journal of Combinatorial Optimization》2009,17(3):312-322
In the paper “Fault-free Mutually Independent Hamiltonian Cycles in Hypercubes with Faulty Edges” (J. Comb. Optim. 13:153–162,
2007), the authors claimed that an n-dimensional hypercube can be embedded with (n−1−f)-mutually independent Hamiltonian cycles when f≤n−2 faulty edges may occur accidentally. However, there are two mistakes in their proof. In this paper, we give examples to
explain why the proof is deficient. Then we present a correct proof.
This work was supported in part by the National Science Council of the Republic of China under Contract NSC 95-2221-E-233-002. 相似文献
13.
This paper studies the group testing problem in graphs as follows. Given a graph G=(V,E), determine the minimum number t(G) such that t(G) tests are sufficient to identify an unknown edge e with each test specifies a subset X⊆V and answers whether the unknown edge e is in G[X] or not. Damaschke proved that ⌈log 2
e(G)⌉≤t(G)≤⌈log 2
e(G)⌉+1 for any graph G, where e(G) is the number of edges of G. While there are infinitely many complete graphs that attain the upper bound, it was conjectured by Chang and Hwang that
the lower bound is attained by all bipartite graphs. Later, they proved that the conjecture is true for complete bipartite
graphs. Chang and Juan verified the conjecture for bipartite graphs G with e(G)≤24 or
for k≥5. This paper proves the conjecture for bipartite graphs G with e(G)≤25 or
for k≥6.
Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.
J.S.-t.J. is supported in part by the National Science Council under grant NSC89-2218-E-260-013.
G.J.C. is supported in part by the National Science Council under grant NSC93-2213-E002-28. Taida Institute for Mathematical
Sciences, National Taiwan University, Taipei 10617, Taiwan. National Center for Theoretical Sciences, Taipei Office. 相似文献
14.
As far as we know, for most polynomially solvable network optimization problems, their inverse problems under l
1 or l
norm have been studied, except the inverse maximum-weight matching problem in non-bipartite networks. In this paper we discuss the inverse problem of maximum-weight perfect matching in a non-bipartite network under l
1 and l
norms. It has been proved that the inverse maximum-weight perfect matching under l
norm can be formulated as a maximum-mean alternating cycle problem of an undirected network, and can be solved in polynomial time by a binary search algorithm and in strongly polynomial time by an ascending algorithm, and under l
1 norm it can be solved by the ellipsoid method. Therefore, inverse problems of maximum-weight perfect matching under l
1 and l
norms are solvable in polynomial time. 相似文献
15.
We study the probabilistic model in the key tree management problem. Users have different behaviors. Normal users have probability
p to issue join/leave request while the loyal users have probability zero. Given the numbers of such users, our objective is
to construct a key tree with minimum expected updating cost. We observe that a single LUN (Loyal User Node) is enough to represent
all loyal users. When 1−p≤0.57 we prove that the optimal tree that minimizes the cost is a star. When 1−p>0.57, we try to bound the size of the subtree rooted at every non-root node. Based on the size bound, we construct the optimal
tree using dynamic programming algorithm in O(n⋅K+K
4) time where K=min {4(log (1−p)−1)−1,n} and n is the number of normal users. 相似文献
16.
Chung-Haw Chang Chao-Ming Sun Hua-Min Huang Lih-Hsing Hsu 《Journal of Combinatorial Optimization》2007,14(2-3):349-364
Let G be a finite undirected bipartite graph. Let u, v be two vertices of G from different partite sets. A collection of k internal vertex disjoint paths joining u to v is referred as a k-container C
k
(u,v). A k-container is a k
*-container if it spans all vertices of G. We define G to be a k
*-laceable graph if there is a k
*-container joining any two vertices from different partite sets. A k
*-container C
k
*(u,v)={P
1,…,P
k
} is equitable if ||V(P
i
)|−|V(P
j
)||≤2 for all 1≤i,j≤k. A graph is equitably k
*-laceable if there is an equitable k
*-container joining any two vertices in different partite sets. Let Q
n
be the n-dimensional hypercube. In this paper, we prove that the hypercube Q
n
is equitably k
*-laceable for all k≤n−4 and n≥5.
Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.
The work of H.-M. Huang was supported in part by the National Science Council of the Republic of China under NSC94-2115-M008-013. 相似文献
17.
An important task in the theory of hypercubes is to establish the maximum integer f
n
such that for every set ℱ of f vertices in the hypercube
Qn,{\mathcal {Q}}_{n},
with 0≤f≤f
n
, there exists a cycle of length at least 2
n
−2f in the complement of ℱ. Until recently, exact values of f
n
were known only for n≤4, and the best lower bound available for f
n
with n≥5 was 2n−4. We prove that f
5=8 and obtain the lower bound f
n
≥3n−7 for all n≥5. Our results and an example provided in the paper support the conjecture that
fn=((n) || 2)-2f_{n}={n\choose 2}-2
for each n≥4. New results regarding the existence of longest fault-free paths with prescribed ends are also proved. 相似文献
18.
A linear extension problem is defined as follows: Given a poset P=(E,≤), we want to find a linear order L such that x≤y in L whenever x≤yin P. In this paper, we assign each pair of elements x,y∈E with a cost, and to find a linear extension of P with the minimum sum cost. For the general case, it is NP-complete and we present a greedy approximation algorithm which
can be finished in polynomial time. Also we consider a special case which can be solved in polynomial time. 相似文献
19.
Céline Engelbeen Samuel Fiorini Antje Kiesel 《Journal of Combinatorial Optimization》2011,22(4):609-629
In this paper we consider the following closest vector problem. We are given a set of 0–1 vectors, the generators, an integer vector, the target vector, and a nonnegative integer C. Among all vectors that can be written as nonnegative integer linear combinations of the generators, we seek a vector whose
ℓ
∞-distance to the target vector does not exceed C, and whose ℓ
1-distance to the target vector is minimum. 相似文献
20.
Lih-Hsing Hsu Shu-Chung Liu Yeong-Nan Yeh 《Journal of Combinatorial Optimization》2007,14(2-3):197-204
Let R and F be two disjoint edge sets in an n-dimensional hypercube Q
n
. We give two constructing methods to build a Hamiltonian cycle or path that includes all the edges of R but excludes all of F. Besides, considering every vertex of Q
n
incident to at most n−2 edges of F, we show that a Hamiltonian cycle exists if (A) |R|+2|F|≤2n−3 when |R|≥2, or (B) |R|+2|F|≤4n−9 when |R|≤1. Both bounds are tight. The analogous property for Hamiltonian paths is also given.
Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.
Lih-Hsing Hsu’s research project is partially supported by NSC 95-2221-E-233-002.
Shu-Chung Liu’s research project is partially supported by NSC 90-2115-M-163-003 and 95-2115-M-163-002.
Yeong-Nan Yeh’s research project is partially supported by NSC 95-2115-M-001-009. 相似文献