We consider a competitive two-agent scheduling problem on multiple identical machines with release dates and preemption. In the scheduling model, there are two agents a and b each having their own job sets J(a) = {J(1...
详细信息
We consider a competitive two-agent scheduling problem on multiple identical machines with release dates and preemption. In the scheduling model, there are two agents a and b each having their own job sets J(a) = {J(1)(a),..., J(na)(a)} and J(b) = {J(1)(b),..., J(nb)(b)}, respectively. Each job J(j) epsilon J(a) boolean OR J(b) has a release date r(i) and the n = n(a) + n(b) jobs need to be preemptively scheduled on m identical machines. For m = 2, we show that the trade-off curve of all the Pareto optimal points can be characterized in polynomialtime. When m is input, we show that P vertical bar r(j), pmtn vertical bar L-max(a) : L-max(b) < Q can be solved in strongly polynomialtime.
This paper addresses a generalization of the coupled-operations scheduling problem in the context of a flow shop environment. We consider the two-machine scheduling problem with the objective of minimizing the makespa...
详细信息
This paper addresses a generalization of the coupled-operations scheduling problem in the context of a flow shop environment. We consider the two-machine scheduling problem with the objective of minimizing the makespan. Each job consists of a coupled-operation to be processed first on the first machine and a single operation to be then processed on the second machine. A coupled-operation contains two operations separated by an exact time delay. The single operation can start on the second machine only when the coupled-operation on the first machine is completed. We prove the NP-completeness of two restricted versions of the general problem, whereas we also exhibit several other well solvable cases.
作者：
Hu, SenLiu, PengUSTC
Sch Math Sci 96 JinZhai RdPOB 230026 Hefei Anhui Peoples R China
For the fundamental representations of the simple Lie algebras of type B-n, C-n and D-n, we derive the braiding and fusion matrices from the generalized Yang-Yang function and prove that the corresponding knot invaria...
详细信息
For the fundamental representations of the simple Lie algebras of type B-n, C-n and D-n, we derive the braiding and fusion matrices from the generalized Yang-Yang function and prove that the corresponding knot invariants are Kauffman polynomial.
This paper is a companion paper to [Yaron Lipman and Ingrid Daubechies, Conformal Wasserstein distances: Comparing surfaces in polynomialtime, Adv. in Math. (ELS), 227 (2011), no. 3, 1047-1077, (2011)]. We provide nu...
详细信息
This paper is a companion paper to [Yaron Lipman and Ingrid Daubechies, Conformal Wasserstein distances: Comparing surfaces in polynomialtime, Adv. in Math. (ELS), 227 (2011), no. 3, 1047-1077, (2011)]. We provide numerical procedures and algorithms for computing the alignment of and distance between two disk-type surfaces. We provide a convergence analysis of the discrete approximation to the arising mass-transportation problems. We furthermore generalize the framework to support sphere-type surfaces, and prove a result connecting this distance to local geodesic distortion. Finally, we perform numerical experiments on several surface datasets and compare them to state-of-the-art methods.
One of the central challenges in the study of quantum many-body systems is the complexity of simulating them on a classical computer. A recent advance (Landau et al. in Nat Phys, 2015) gave a polynomialtime algorithm...
详细信息
One of the central challenges in the study of quantum many-body systems is the complexity of simulating them on a classical computer. A recent advance (Landau et al. in Nat Phys, 2015) gave a polynomialtime algorithm to compute a succinct classical description for unique ground states of gapped 1D quantum systems. Despite this progress many questions remained unsolved, including whether there exist efficient algorithms when the ground space is degenerate (and of polynomial dimension in the system size), or for the polynomially many lowest energy states, or even whether such states admit succinct classical descriptions or area laws. In this paper we give a new algorithm, based on a rigorously justified RG type transformation, for finding low energy states for 1D Hamiltonians acting on a chain of n particles. In the process we resolve some of the aforementioned open questions, including giving a polynomialtime algorithm for poly(n) degenerate ground spaces and an n (O(log) n) algorithm for the poly(n) lowest energy states (under a mild density condition). For these classes of systems the existence of a succinct classical description and area laws were not rigorously proved before this work. The algorithms are natural and efficient, and for the case of finding unique ground states for frustration-free Hamiltonians the running time is , where M(n) is the time required to multiply two n x n matrices.
In this paper we study the classical single machine scheduling problem where the objective is to minimize the weighted number of tardy jobs. Our analysis focuses on the case where one or more of three natural paramete...
详细信息
In this paper we study the classical single machine scheduling problem where the objective is to minimize the weighted number of tardy jobs. Our analysis focuses on the case where one or more of three natural parameters is either constant or is taken as a parameter in the sense of parameterized complexity. These three parameters are the number of different due dates, processing times, and weights in our set of input jobs. We show that the problem belongs to the class of fixed parameter tractable (FPT) problems when combining any two of these three parameters. We also show that the problem is polynomial-time solvable when either one of the latter two parameters are constant, complementing Karp's result who showed that the problem is NP-hard already for a single due date.
Let q be a prime power and let G be an absolutely irreducible subgroup of GL(d)(F), where F is a finite field of the same characteristic as F-q, the field of q elements. Assume that G congruent to G(q), a quasisimple ...
详细信息
Let q be a prime power and let G be an absolutely irreducible subgroup of GL(d)(F), where F is a finite field of the same characteristic as F-q, the field of q elements. Assume that G congruent to G(q), a quasisimple group of exceptional Lie type over F-q which is neither a Suzuki nor a Ree group. We present a Las Vegas algorithm that constructs an isomorphism from G to the standard copy of G(q). If G not congruent to D-3(4)(q) with q even, then the algorithm runs in polynomialtime, subject to the existence of a discrete log oracle.
We study the problem of minimizing a sum of p-norms where p is a fixed real number in the interval [1, infinity]. Several practical algorithms have been proposed to solve this problem. However, none of them has a know...
详细信息
We study the problem of minimizing a sum of p-norms where p is a fixed real number in the interval [1, infinity]. Several practical algorithms have been proposed to solve this problem. However, none of them has a known polynomialtime complexity. In this paper, we transform the problem into standard conic form. Unlike those in most convex optimization problems, the cone for the p-norm problem is not self-dual unless p = 2. Nevertheless, we are able to construct two logarithmically homogeneous self-concordant barrier functions for this problem. The barrier parameter of the first barrier function does not depend on p. The barrier parameter of the second barrier function increases with p. Using both barrier functions, we present a primal-dual potential reduction algorithm to compute an epsilon-optimal solution in polynomialtime that is independent of p. Computational experiences with a Matlab implementation are also reported.
暂无评论