We present a convex conic relaxation for a problem of maximising an indefinite quadratic form over a set of convex constraints on the squared variables. We show that for all these problems we get at least 12/37 relative accuracy of the approximation. In the second part of the paper we derive the...

We propose an alternative approach to stochastic programming based on Monte-Carlo sampling and stochastic gradient optimization. The procedure is by essence probabilistic and the computed solution is a random variable.

We consider semidefinite programs, where all the matrices defining the problem commute. We show that in this case the semidefinite program can be solved through an ordinary linear program. As an application, we consider the max-cut problem, where the underlying graph arises from an association...

We consider the problem of scheduling unrelated parallel machines subject to release dates so as to minimize the total weighted completion time of jobs. The main contribution of this paper is a probably good convex quadratic programming relaxation of strongly polynomial size of this problem.

Parallel machine scheduling problems concern the scheduling of "n" jobs on "m" machines to minimize some function of the job completion time. If preemption is not allowed, then most problems are not only NP-hard, but also very hard from a practical point of view. In this paper, we show that...

We consider the scheduling problem of minimizing the average wighted completion time of n jobs with release dates on a single machine. We first study two linear programming relaxations of the problem, one based on time-indexed formulation, the other on a completion-time formulation. We show...

We consider the problem of scheduling a set of n jobs on m identical parallel machines so as to minimize the weighted sum of job completion times.

In this paper we present several "infeasible-start" path-following and potential-reduction primal-dual interior-point methods for non-linear conic problems. These methods try to find a recession direction of the feasible set of a self-dual homogeneous primal-dual problem.

In this paper we study the concepts of equilibrium and optimum in static transportation networks with elastic and non-elastic demands. The main mathematical tool of our paper is the theory of variational inequalities. We demonstrate that this theory is useful for proving the existence theorems....

In this paper we consider a labor constrained scheduling problem (LCSP) which is a simplification of a practical problem arising in industry. Jobs are subject to precedence constraints and have specified processing times. Moreover, for each job the labor requirements varies as the job is...