Springer Science and Business Media LLC

In this paper we study the problem of scheduling a set of periodic tasks nonpreemptively in hard-real-time systems, where it is critical for all requests of the tasks to be processed in time. A taskT is characterized by itsarrival time A, itsperiod P, and itsexecution time C. Starting fromA, a new request ofT arrives in everyP units of time, requestingC units of processing time, and itsdeadline coincides with the arrival of the next request ofT. All requests must be processed nonpreemptively to meet their corresponding deadlines. We show that the problem of testing the feasibility of a given task set {T 1,T 2,⋯,T n} satisfyingP 1+1=ki pi, wherek i; is an integer ≥ 1 for 1≤i ≤ n−1, on a single processor is NP-hard in the strong sense, even if all tasks have the same arrival time. For task sets satisfyingP i+1=K Pi, whereK is an integer ≥ 2 for 1≤ i ≤ n−1 and all tasks have the same arrival time, we present linear-time (in the number of requests) optimal scheduling algorithms as well as linear-time (in the number of tasks, i.e.,n) algorithms for testing feasibility in both uniprocessor and multiprocessor systems. We also extend our results to more general task sets.

Chúng tôi nghiên cứu bài toán phân bổ công bằng max-min trong đó một tập hợp gồm m vật phẩm không thể chia được sẽ được phân phối cho n tác nhân sao cho lượng tiện ích tối thiểu giữa tất cả các tác nhân được tối đa hóa. Trong bối cảnh hạn chế, tiện ích của mỗi vật phẩm j đối với tác nhân i là hoặc 0 hoặc một trọng số không âm $$w_j$$. Đối với bối cảnh này, Asadpour và cộng sự (ACM Trans Algorithms 8(3):24, 2012) đã chỉ ra rằng một cấu hình-LP nhất định có thể được sử dụng để ước lượng giá trị tối ưu trong một tỷ lệ $$4+\delta $$, với bất kỳ $$\delta >0$$, điều này gần đây đã được Annamalai và cộng sự (trong: Indyk (biên soạn) Kỷ yếu của hội nghị ACMSIAM năm thứ hai mươi sáu về các thuật toán rời rạc, SODA 2015, San Diego, CA, Mỹ, từ ngày 4 đến 6 tháng 1 năm 2015) mở rộng để đưa ra một thuật toán xấp xỉ bậc đa thức 13 cho bài toán. Đối với các kết quả về độ khó, Bezáková và Dani (SIGecom Exch 5(3):11–18, 2005) đã chỉ ra rằng bài toán này là $$\mathsf {NP}$$-khó để xấp xỉ trong bất kỳ tỷ lệ nào nhỏ hơn 2. Trong bài báo này, chúng tôi xem xét bài toán phân bổ công bằng max-min hạn chế $$ (1,\epsilon )$$ trong đó mỗi vật phẩm j là nặng $$ (w_j = 1)$$ hoặc nhẹ $$ (w_j = \epsilon )$$, với một số tham số $$\epsilon \in (0,1)$$. Chúng tôi chứng minh rằng trường hợp $$ (1,\epsilon )$$-hạn chế cũng là $$\mathsf {NP}$$-khó để xấp xỉ trong bất kỳ tỷ lệ nào nhỏ hơn 2. Sử dụng cấu hình-LP, chúng tôi có thể ước lượng giá trị tối ưu của bài toán trong một tỷ lệ $$3+\delta $$, với bất kỳ $$\delta >0$$. Mở rộng ý tưởng này, chúng tôi cũng thu được một thuật toán xấp xỉ thời gian quasi-bậc đa thức $$ (3+4\epsilon )$$ và một thuật toán xấp xỉ bậc đa thức 9. Hơn nữa, chúng tôi chứng minh rằng khi $$\epsilon $$ tiến tới 0, tỷ lệ xấp xỉ của thuật toán thời gian bậc đa thức của chúng tôi tiếp cận $$3+2\sqrt{2}\approx 5.83$$.

This paper studies the natural linear programming relaxation of the path coloring problem. We prove constructively that finding an optimal fractional path coloring is Fixed Parameter Tractable (FPT), with the degree of the tree as parameter: the fractional coloring of paths in a bounded degree trees can be done in a time which is linear in the size of the tree, quadratic in the load of the set of paths, while exponential in the degree of the tree. We give an algorithm based on the generation of an efficient polynomial size linear program. Our algorithm is able to explore in polynomial time the exponential number of different fractional colorings, thanks to the notion of trace of a coloring that we introduce. We further give an upper bound on the cost of such a coloring in binary trees and extend this algorithm to bounded degree graphs with bounded treewidth. Finally, we also show some relationships between the integral and fractional problems, and derive a 1+5/3e≈1.61—approximation algorithm for the path coloring problem in bounded degree trees, improving on existing results. This classic combinatorial problem finds applications in the minimization of the number of wavelengths in wavelength division multiplexing (wdm) optical networks.

We consider a multi-stage facility reallocation problems on the real line, where a facility is being moved between time stages based on the locations reported by n agents. The aim of the reallocation algorithm is to minimise the social cost, i.e., the sum over the total distance between the facility and all agents at all stages, plus the cost incurred for moving the facility. We study this problem both in the offline setting and online setting. In the offline case the algorithm has full knowledge of the agent locations in all future stages, and in the online setting the algorithm does not know these future locations and must decide the location of the facility on a stage-per-stage basis. We derive the optimal algorithm in both cases. For the online setting we show that its competitive ratio is $$(n+2)/(n+1)$$ . As neither of these algorithms turns out to yield a strategy-proof mechanism, we propose another strategy-proof mechanism which has a competitive ratio of $$(n+3)/(n+1)$$ for odd n and $$(n+4)/n$$ for even n, which we conjecture to be the best possible. We also consider a generalisation with multiple facilities and weighted agents, for which we show that the optimum can be computed in polynomial time for a fixed number of facilities.

Nondeterministic weighted finite-state automata are a key abstraction in automatic speech recognition systems. The efficiency of automatic speech recognition depends directly on the sizes of these automata and the degree of nondeterminism present, so recent research has studied ways to determinize and minimize them, using analogues of classical automata determinization and minimization. Although, as we describe here, determinization can in the worst case cause poly-exponential blowup in the number of states of a weighted finite-state automaton, in practice it is remarkably successful. In extensive experiments in automatic speech recognition systems, deterministic weighted finite-state automata tend to be smaller than the corresponding nondeterministic inputs. Our observations show that these size reductions depend critically on the interplay between weights and topology in nondeterministic weighted finite-state automata. We exploit these observations to design a new approximate determinizationalgorithm, which produces a deterministic weighted finite-state automaton that preserves the strings of a weighted language but not necessarily their weights. We apply our algorithm to two different types of weighted finite-state automata that occur in automatic speech recognition systems and in each case provide extensive experimental results showing that, compared with current techniques, we achieve significant size reductions without affecting performance. In particular, for a standard test bed, we can reduce automatic speech recognition memory requirements by 25—35\percent with negligible effects on recognition time and accuracy.

A generalization of a theorem of Lomonosov and Polesskii is proved, which provides a novel method for determining upper bounds on the probability that a graph contains a Steiner tree (k-terminal reliability).

In Ritt's method, a prime ideal is given by a characteristic set. A characteristic set of a prime ideal is generally not a set of generators of this ideal. In this paper we present a simple algorithm for constructing Gröbner bases of a prime ideal from its characteristic set. We give a method for finding new theorems in geometry as an application of this algorithm.