-
作者：KASPI, H; MANDELBAUM, A
摘要：We show that a continuous-time Markov process X is Harris recurrent if and only if there exists a nonzero sigma-finite measure nu on its state space such that X surely hits sets with positive nu-measure. This simple criterion is applied to some nonparametric closed queueing networks.
-
作者：GOLDSCHMIDT, O; HOCHBAUM, DS
作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley
摘要：The k-cut problem is to find a partition of an edge weighted graph into k nonempty components, such that the total edge weight between components is minimum. This problem is NP-complete for an arbitrary k and its version involving fixing a vertex in each component is NP-hard even for k = 3. We present a polynomial algorithm for k fixed, that runs in O(n(k2/2-3k/2+4)T(n, m)) steps, where T(n, m) is the running time required to find the minimum (s, t)-cut on a graph with n vertices and m edges.
-
作者：KOVALYOV, MY; POTTS, CN; VANWASSENHOVE, LN
作者单位：INSEAD Business School; University of Southampton
摘要：This paper studies approximation algorithms for the problem of nonpreemptively scheduling n jobs on a single machine to minimize total weighted late work, where the late work for a job is the amount of processing of this job that is performed after its due date. A family of approximation algorithms {DP(epsilon)} is derived. For any epsilon > 0, DP(epsilon) delivers a schedule having total weighted late work which does not exceed (1 + epsilon) times that of an optimal schedule. Since DP(epsilon...
