We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple ...
详细信息
We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple machines can process the jobs of an order concurrently. No setup is required if a machine switches over from one job to another. Each order is released at time zero and has a positive weight. Preemptions are not allowed. The completion time of an order is the time at which all jobs of that order have been completed. The objective is to minimize the total weighted completion time of the orders. The problem is NP-hard for any fixed number (>= 2) of machines. Because of this, we focus our attention on two classes of heuristics, which we refer to as sequential two-phase heuristics and dynamic two-phase heuristics. We perform a worst case analysis as well as an empirical analysis of nine heuristics. Our analyses enable us to rank these heuristics according to their effectiveness, taking solution quality as well as running time into account. (C) 2006 Wiley Peribdicals, Inc.
Training a one-node neural network with the ReLU activation function via optimization, which we refer to as the ON-ReLU problem, is a fundamental problem in machine learning. In this paper, we begin by proving the NP-...
详细信息
Training a one-node neural network with the ReLU activation function via optimization, which we refer to as the ON-ReLU problem, is a fundamental problem in machine learning. In this paper, we begin by proving the NP-hardness of the ON-ReLU problem. We then present an approximation algorithm to solve the ON-ReLU problem, whose running time is O(n(k)) where n is the number of samples, and k is a predefined integral constant as an algorithm parameter. We analyze the performance of this algorithm under two regimes and show that: (1) given any arbitrary set of training samples, the algorithm guarantees an (n/k)-approximation for the ON-ReLU problem - to the best of our knowledge, this is the first time that an algorithm guarantees an approximation ratio for arbitrary data scenario;thus, in the ideal case (i.e., when the training error is zero) the approximation algorithm achieves the globally optimal solution for the ON-ReLU problem;and (2) given training sample with Gaussian noise, the same approximation algorithm achieves a much better asymptotic approximation ratiowhich is independent of the number of samples n. Extensive numerical studies show that our approximation algorithm can perform better than the gradient descent algorithm. Our numerical results also show that the solution of the approximation algorithm can provide a good initialization for gradient descent, which can significantly improve the performance.
Given a graph G = (V. E) a clique is a maximal subset of pairwise adjacent vertices of V of size at least 2. A clique transversal is a subset of vertices that intersects the vertex set of each clique of G. Finding a m...
详细信息
Given a graph G = (V. E) a clique is a maximal subset of pairwise adjacent vertices of V of size at least 2. A clique transversal is a subset of vertices that intersects the vertex set of each clique of G. Finding a minimum-cardinality clique transversal is NP-hard for the following classes: planar, line and bounded degree graphs. For line graphs we present a 3-approximation for the unweighted case and a 4-approximation for the weighted case with nonnegative weights;a inverted right perpendicular(G) + 1)/2inverted left perpendicular-approximation for bounded degree graphs and a 3-approximation for planar graphs. (C) 2015 Elsevier B.V. All rights reserved.
Given a weighted graph G=(V,E)with weight w:E→Z+,a k-cycle transversal is an edge subset A of E such that G−A has no *** minimum weight of kcycle transversal is the weighted transversal number on k-cycle,denoted byτ...
详细信息
Given a weighted graph G=(V,E)with weight w:E→Z+,a k-cycle transversal is an edge subset A of E such that G−A has no *** minimum weight of kcycle transversal is the weighted transversal number on k-cycle,denoted byτk(Gw).In this paper,we design a(k−1/2)-approximation algorithm for the weighted transversal number on k-cycle when k is *** a weighted graph G=(V,E)with weight w:E→Z+,a k-clique transversal is an edge subset A of E such that G−A has no *** minimum weight of k-clique transversal is the weighted transversal number on k-clique,denoted byτapproximation algorithm for the weighted transversal number on k(Gw).In this paper,we design a(k2−k−1)/***,we discuss the relationship between k-clique covering and k-clique packing in complete graph Kn.
We consider the following two deterministic inventory optimization problems with non-stationary demands. Submodular joint replenishment problem. This involves multiple item types and a single retailer who faces demand...
详细信息
We consider the following two deterministic inventory optimization problems with non-stationary demands. Submodular joint replenishment problem. This involves multiple item types and a single retailer who faces demands over a finite planning horizon of T periods. In each time period, any subset of item-types can be ordered incurring a joint ordering cost which is submodular. Moreover, items can be held in inventory while incurring a holding cost. The objective is to find a sequence of orders that satisfies all demands and minimizes the total ordering and holding costs. Inventory routing problem. This involves a single depot that stocks items, and multiple retailer locations facing demands over a finite planning horizon of T periods. In each time period, any subset of locations can be visited using a vehicle originating from the depot. There is also cost incurred for holding items at any retailer. The objective here is to satisfy all demands while minimizing the sum of routing and holding costs. We present a unified approach that yields -factor approximation algorithms for both problems when the holding costs are polynomial functions. A special case is the classic linear holding cost model, wherein this is the first sub-logarithmic approximation ratio for either problem.
In this paper we consider the maximization of the weighted number of early jobs on a single machine with non-availability constraints. We deal with the resumable and the non-resumable cases. We show that the resumable...
详细信息
In this paper we consider the maximization of the weighted number of early jobs on a single machine with non-availability constraints. We deal with the resumable and the non-resumable cases. We show that the resumable version of this problem has a fully polynomial time approximation scheme (FPTAS) even if the number of the non-availability intervals is variable and a subset of jobs has deadlines instead of due dates. For the non-resumable version we remark that the problem cannot admit an FPTAS even if all due dates are equal and only one non-availability interval occurs. Nevertheless, we show in this case that it admits a polynomial time approximation scheme (PTAS) for a constant number of non-availability intervals and arbitrary due dates.
Motivated by a real world application, we study the multiple knapsack problem with assignment restrictions (MKAR). We are given a set of items, each with a positive real weight, and a set of knapsacks, each with a pos...
详细信息
Motivated by a real world application, we study the multiple knapsack problem with assignment restrictions (MKAR). We are given a set of items, each with a positive real weight, and a set of knapsacks, each with a positive real capacity. In addition, for each item a set of knapsacks that can hold that item is specified. In a feasible assignment of items to knapsacks, each item is assigned to at most one knapsack, assignment restrictions are satisfied, and knapsack capacities are not exceeded. We consider the objectives of maximizing assigned weight and minimizing utilized capacity. We focus on obtaining approximate solutions in polynomial computational time. We show that simple greedy approaches yield 1/3-approximation algorithms for the objective of maximizing assigned weight. We give two different 1/2-approximation algorithms: the first one solves single knapsack problems successively and the second one is based on rounding the LP relaxation solution. For the bicriteria problem of minimizing utilized capacity subject to a minimum requirement on assigned weight, we give an (1/3,2)-approximation algorithm.
We consider the problem of designing a minimum cost access network to carry traffic from a set of endnodes to a core network. Trunks are available in K types reflecting economies of scale. A trunk type with a high ini...
详细信息
We consider the problem of designing a minimum cost access network to carry traffic from a set of endnodes to a core network. Trunks are available in K types reflecting economies of scale. A trunk type with a high initial overhead cost has a low cost per unit bandwidth and a trunk type with a low overhead cost has a high cost per unit bandwidth. We formulate the problem as an integer program. We first use a primal-dual approach to obtain a solution whose cost is within O(K-2) of optimal. Typically the value of K is small. This is the first combinatorial algorithm with an approximation ratio that is polynomial in K and is independent of the network size and the total traffic to be carried. We also explore linear program rounding techniques and prove a better approximation ratio of O(K). Both bounds are obtained under weak assumptions on the trunk costs. Our primal-dual algorithm is motivated by the work of Jain and Vazirani on facility location [7]. Our rounding algorithm is motivated by the facility location algorithm of Shmoys et al. [12].
We consider the interval constrained coloring problem, which appears in the interpretation of experimental data in biochemistry. Monitoring hydrogen-deuterium exchange rates via mass spectroscopy experiments is a meth...
详细信息
We consider the interval constrained coloring problem, which appears in the interpretation of experimental data in biochemistry. Monitoring hydrogen-deuterium exchange rates via mass spectroscopy experiments is a method used to obtain information about protein tertiary structure. The output of these experiments provides data about the exchange rate of residues in overlapping segments of the protein backbone. These segments must be re-assembled in order to obtain a global picture of the protein structure. The interval constrained coloring problem is the mathematical abstraction of this re-assembly process. The objective of the interval constrained coloring problem is to assign a color (exchange rate) to a set of integers (protein residues) such that a set of constraints is satisfied. Each constraint is made up of a closed interval (protein segment) and requirements on the number of elements that belong to each color class (exchange rates observed in the experiments). We show that the problem is NP-complete for arbitrary number of colors and we provide algorithms that given a feasible instance find a coloring that satisfies all the coloring requirements within +/- 1 of the prescribed value. In light of our first result, this is essentially the best one can hope for. Our approach is based on polyhedral theory and randomized rounding techniques. Furthermore, we consider a variant of the problem where we are asked to find a coloring satisfying as many fragments as possible. If we relax the coloring requirements by a small factor of (1+epsilon), we propose an algorithm that finds a coloring "satisfying" this maximum number of fragments and that runs in quasi-polynomial time if the number of colors is polylogarithmic.
We study traffic grooming in optical network design, where the goal is to aggregate low-bandwidth traffic streams to utilize efficiently high-bandwidth media such as wavelength channels. More precisely, given traffic ...
详细信息
We study traffic grooming in optical network design, where the goal is to aggregate low-bandwidth traffic streams to utilize efficiently high-bandwidth media such as wavelength channels. More precisely, given traffic demands to be routed in a network, the design problem is to define a collection of light paths such that each demand can follow a sequence of consecutive light paths. Each light path has a unit-wavelength bandwidth, and multiple sub-wavelength demands may share a common light path. Traffic must enter and depart from a light path at its two endpoints only. Most previous work on grooming focused on the ring topology and typically involved only uniform bandwidth demands, whereas we deal with more general settings. Two objectives are considered. One is to minimize the total cost of equipment necessary to support the light paths;the other is simply to minimize the number of light paths. Even for the extremely restricted special case of a line topology and traffic demands that request half wavelength bandwidth, we show that both objectives are APX-hard to optimize, which means we cannot approximate the optimum arbitrarily closely. On the other extreme of generality, for arbitrary network topologies and traffic demands that request arbitrary amounts of bandwidth, we show a logarithmic approximation for cost minimization and a 2-approximation for minimizing light path counts. Furthermore, we discover that the special case of half-wavelength demands has rich combinatorial properties, closely related to graph problems such as cycle packing and pattern matching problems such as interchange distance in strings. We show how to approximate both objectives up to small constant factors in this case, while similarly improving the approximation and hardness of the interchange distance problem as well. (C) 2011 Elsevier B.V. All rights reserved.
暂无评论