LP rounding and combinatorial algorithms for minimizing active and busy time

We consider fundamental scheduling problems motivated by energy issues. In this framework, we are given a set of jobs, each with a release time, deadline, and required processing length. The jobs need to be scheduled on a machine so that at most g jobs are active at any given time. The duration for which a machine is active (i.e., “on”) is referred to as its active time. The goal is to find a feasible schedule for all jobs, minimizing the total active time. When preemption is allowed at integer time points, we show that a minimal feasible schedule already yields a 3-approximation (and this bound is tight) and we further improve this to a 2-approximation via LP rounding techniques. Our second contribution is for the non-preemptive version of this problem. However, since even asking if a feasible schedule on one machine exists is NP-hard, we allow for an unbounded number of virtual machines, each having capacity of g. This problem is known as the busy time problem in the literature and a 4-approximation is known for this problem. We develop a new combinatorial algorithm that gives a 3-approximation. Furthermore, we consider the preemptive busy time problem, giving a simple and exact greedy algorithm when unbounded parallelism is allowed, i.e., g is unbounded. For arbitrary g, this yields an algorithm that is 2-approximate.     

Stackelberg Network Pricing Games

We study a multi-player one-round game termed Stackelberg Network Pricing Game, in which a leader can set prices for a subset of m priceable edges in a graph. The other edges have a fixed cost. Based on the leader’s decision one or more followers optimize a polynomial-time solvable combinatorial minimization problem and choose a minimum cost solution satisfying their requirements based on the fixed costs and the leader’s prices. The leader receives as revenue the total amount of prices paid by the followers for priceable edges in their solutions. Our model extends several known pricing problems, including single-minded and unit-demand pricing, as well as Stackelberg pricing for certain follower problems like shortest path or minimum spanning tree. Our first main result is a tight analysis of a single-price algorithm for the single follower game, which provides a (1+ε)log?m-approximation. This can be extended to provide a (1+ε)(log?k+log?m)-approximation for the general problem and k followers. The problem is also shown to be hard to approximate within $\mathcal{O}(\log^{\varepsilon}k + \log^{\varepsilon}m)$ for some ε>0. If followers have demands, the single-price algorithm provides an $\mathcal{O}(m^{2})$ -approximation, and the problem is hard to approximate within $\mathcal{O}(m^{\epsilon})$ for some ε>0. Our second main result is a polynomial time algorithm for revenue maximization in the special case of Stackelberg bipartite vertex-cover, which is based on non-trivial max-flow and LP-duality techniques. This approach can be extended to provide constant-factor approximations for any constant number of followers.     

New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs

Given a node-weighted graph, the minimum-weighted dominating set (MWDS) problem is to find a minimum-weighted vertex subset such that, for any vertex, it is contained in this subset or it has a neighbor contained in this set. And the minimum-weighted connected dominating set (MWCDS) problem is to find a MWDS such that the graph induced by this subset is connected. In this paper, we study these two problems on a unit disk graph. A (4 +ε)-approximation algorithm for an MWDS based on a dynamic programming algorithm for a Min-Weight Chromatic Disk Cover is presented. Meanwhile, we also propose a (1 +ε)-approximation algorithm for the connecting part by showing a polynomial-time approximation scheme for a Node-Weighted Steiner Tree problem when the given terminal set is c-local and thus obtain a (5 +ε)-approximation algorithm for an MWCDS.     

Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval

In this article, we consider the non-resumable case of the single machine scheduling problem with a fixed non-availability interval. We aim to minimize the weighted sum of completion times. No polynomial 2-approximation algorithm for this problem has been previously known. We propose a 2-approximation algorithm with O(n²) time complexity where n is the number of jobs. We show that this bound is tight. The obtained result outperforms all the previous polynomial approximation algorithms for this problem.     

A hybrid mechanism for heterogeneous e-procurement involving a combinatorial auction and bargaining

We discuss the design of a hybrid mechanism for e-procurement, which implements a multi-attribute combinatorial auction, followed by a bargaining process to achieve desirable procurement transaction outcomes. For the auction phase of the mechanism, we discuss incentive-compatible bidding strategies for suppliers, and how the buyer should determine the winning suppliers. In the follow-on bargaining phase, the buyer can implement a pricing strategy that views the winning suppliers as though they are in different groups. We develop a model and derive decision conditions for the buyer to formulate procurement strategy in this context. Our most important finding is that, compared with the classical Vickrey–Clarke–Groves mechanism, the proposed mechanism improves the transactional social surplus, by including the possibility of post-auction bargaining. We also consider the likelihood that such a hybrid mechanism will be able to provide sustainable business value so long as there is reasonable symmetry in bargaining power between the buyer and the supplier. We offer some thoughts on how to extend this research with approaches from behavioral economics and experimental methods.     

Orthogonal incremental extreme learning machine for regression and multiclass classification

Single-hidden-layer feedforward networks with randomly generated additive or radial basis function hidden nodes have been theoretically proved that they can approximate any continuous function. Meanwhile, an incremental algorithm referred to as incremental extreme learning machine (I-ELM) was proposed which outperforms many popular learning algorithms. However, I-ELM may produce redundant nodes which increase the network architecture complexity and reduce the convergence rate of I-ELM. Moreover, the output weight vector obtained by I-ELM is not the least squares solution of equation Hβ = T. In order to settle these problems, this paper proposes an orthogonal incremental extreme learning machine (OI-ELM) and gives the rigorous proofs in theory. OI-ELM avoids redundant nodes and obtains the least squares solution of equation Hβ = T through incorporating the Gram–Schmidt orthogonalization method into I-ELM. Simulation results on nonlinear dynamic system identification and some benchmark real-world problems verify that OI-ELM learns much faster and obtains much more compact neural networks than ELM, I-ELM, convex I-ELM and enhanced I-ELM while keeping competitive performance.     

The Bell Is Ringing in Speed-Scaled Multiprocessor Scheduling

This paper investigates the problem of scheduling jobs on multiple speed-scaled processors, i.e., we have constant α>1 such that running a processor at speed s results in energy consumption s ^α per time unit. We consider the general case where each job has a monotonously increasing cost function that penalizes delay. This includes the so far considered cases of deadlines, flow time, and weighted flow time. For any type of delay cost functions, we obtain the following results: Any β-approximation algorithm for a single processor yields a randomized βB _α -approximation algorithm for multiple processors, where B _α is the αth Bell number, that is, the number of partitions of a set of size α. The generated schedule is without migration, but we compare it to an optimal schedule with migration. Hence, this result holds for migratory and non-migratory schedules. Analogously, we show that any β-competitive online algorithm for a single processor yields a βB _α -competitive online algorithm for multiple processors. Finally, we show that any β-approximation algorithm for multiple processors with migration yields a deterministic βB _α -approximation algorithm for multiple processors without migration. These facts improve several approximation ratios and lead to new results. For instance, we obtain the first constant factor online and offline approximation algorithm for multiple processors without migration for arbitrary release times, deadlines, and job sizes.     

ε-approximations of k-label spaces

In a standard framework of learning a geometric concept from examples, examples are classified into two types: examples contained in the concept (positive examples) and those not contained in the concept (negative examples). However, there exist cases where examples are classified into k(⩾ 2) classes. For example, clustering a concept space by the Voronoi diagram generated by k points is a very common tool in image understanding and many other areas. We call such a space a k-label space. The typical case consisting of positive and negative examples corresponds to the 2-label space in this setting.In this paper, we first extend the ε-approximation for the 2-label space originally considered by Vapnik and Chervonenkis (1971) (see also Blumer et al., 1989; Haussler and Welzl, 1987) to that for the k-label space. Next, the sample complexity for the generalized ε-approximation is analyzed. The generalized ε-approximation is then applied to the randomized algorithm for the assignment problem by Tokuyama and Nakano (1991) to obtain tighter bounds. By combining the generalized ε-approximation with the capacity of a k-label space induced by Voronoi diagrams, bounds for learning noisy data for such a k-label space may be obtained.     

Improved Approximation Algorithms for Label Cover Problems

In this paper we consider both the maximization variant Max Rep and the minimization variant Min Rep of the famous Label Cover problem. So far the best approximation ratios known for these two problems were \(O(\sqrt{n})\) and indeed some authors suggested the possibility that this ratio is the best approximation factor for these two problems. We show, in fact, that there are a O(n ^1/3)-approximation algorithm for Max Rep and a O(n ^1/3log?^2/3 n)-approximation algorithm for Min Rep. In addition, we also exhibit a randomized reduction from Densest k-Subgraph to Max Rep, showing that any approximation factor for Max Rep implies the same factor (up to a constant) for Densest k-Subgraph.     

Greedy Δ-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost

This paper describes a simple greedy Δ-approximation algorithm for any covering problem whose objective function is submodular and non-decreasing, and whose feasible region can be expressed as the intersection of arbitrary (closed upwards) covering constraints, each of which constrains at most Δ variables of the problem. (A simple example is Vertex Cover, with Δ=2.) The algorithm generalizes previous approximation algorithms for fundamental covering problems and online paging and caching problems.     

Multiprocessor Scheduling with Machine Allotment and Parallelism Constraints

Abstract. Modern computer systems distribute computation among several machines to speed up the execution of programs. Yet, setup and communication costs, as well as parallelism constraints, bound the number of machines that can share the execution of a given application, and the number of machines by which it can be processed simultaneously . We study the resulting scheduling problem, stated as follows. Given a set of n jobs and m uniform machines, assign the jobs to the machines subject to parallelism and machine allotment constraints, such that the overall completion time of the schedule (or makespan ) is minimized. Indeed, the multiprocessor scheduling problem (where each job can be processed by a single machine) is a special case of our problem; thus, our problem is strongly NP-hard. We present a (1+ α) -approximation algorithm for this problem, where α ∈ (0,1] depends on the minimal number of machine allotments and the minimal parallelism allowed for any job. Also, we show that when the maximal number of machines that can share the execution of a job is some fixed constant, our problem has a polynomial time approximation scheme ; for other special cases we give optimal polynomial time algorithms. Finally, through the relation of our problem to the classic preemptive scheduling problem on multiple machines, we shed some fresh light on what is known in scheduling folklore as the power of preemption.     

A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties

We consider the facility location problem with submodular penalties (FLPSP), introduced by Hayrapetyan et?al. (Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 933–942, 2005), who presented a 2.50-approximation algorithm that is non-combinatorial because this algorithm has to solve the LP-relaxation of an integer program with exponential number of variables. The only known polynomial algorithm for this exponential LP is via the ellipsoid algorithm as the corresponding separation problem for its dual program can be solved in polynomial time. By exploring the properties of the submodular function, we offer a primal-dual 3-approximation combinatorial algorithm for this problem.     

Improved Approximation Algorithms for the Min-max Tree Cover and Bounded Tree Cover Problems

In this paper we provide improved approximation algorithms for the Min-Max Tree Cover and Bounded Tree Cover problems. Given a graph G=(V,E) with weights w:E→?⁺, a set T ₁,T ₂,…,T _k of subtrees of G is called a tree cover of G if $V=\bigcup_{i=1}^{k} V(T_{i})$ . In the Min-Max k-tree Cover problem we are given graph G and a positive integer k and the goal is to find a tree cover with k trees, such that the weight of the largest tree in the cover is minimized. We present a 3-approximation algorithm for this improving the two different approximation algorithms presented in Arkin et al. (J. Algorithms 59:1–18, 2006) and Even et al. (Oper. Res. Lett. 32(4):309–315, 2004) with ratio 4. The problem is known to have an APX-hardness lower bound of $\frac{3}{2}$ (Xu and Wen in Oper. Res. Lett. 38:169–173, 2010). In the Bounded Tree Cover problem we are given graph G and a bound λ and the goal is to find a tree cover with minimum number of trees such that each tree has weight at most λ. We present a 2.5-approximation algorithm for this, improving the 3-approximation bound in Arkin et al. (J. Algorithms 59:1–18, 2006).     

Survivable network design: the capacitated minimum spanning network problem

We are given an undirected graph G=(V,E) with positive weights on its vertices representing demands, and non-negative costs on its edges. Also given are a capacity constraint k, and root vertex r∈V. In this paper, we consider the capacitated minimum spanning network (CMSN) problem, which asks for a minimum cost spanning network such that the removal of r and its incident edges breaks the network into a number of components (groups), each of which is 2-edge-connected with a total weight of at most k. We show that the CMSN problem is NP-hard, and present a 4-approximation algorithm for graphs satisfying triangle inequality. We also show how to obtain similar approximation results for a related 2-vertex-connected CMSN problem.     

MMA: a multi-view and multi-modality benchmark dataset for human action recognition

Human action recognition is an active research topic in both computer vision and machine learning communities, which has broad applications including surveillance, biometrics and human computer interaction. In the past decades, although some famous action datasets have been released, there still exist limitations, including the limited action categories and samples, camera views and variety of scenarios. Moreover, most of them are designed for a subset of the learning problems, such as single-view learning problem, cross-view learning problem and multi-task learning problem. In this paper, we introduce a multi-view, multi-modality benchmark dataset for human action recognition (abbreviated to MMA). MMA consists of 7080 action samples from 25 action categories, including 15 single-subject actions and 10 double-subject interactive actions in three views of two different scenarios. Further, we systematically benchmark the state-of-the-art approaches on MMA with respective to all three learning problems by different temporal-spatial feature representations. Experimental results demonstrate that MMA is challenging on all three learning problems due to significant intra-class variations, occlusion issues, views and scene variations, and multiple similar action categories. Meanwhile, we provide the baseline for the evaluation of existing state-of-the-art algorithms.     

APX-hardness of domination problems in circle graphs

We show that the problem of finding a minimum dominating set in a circle graph is APX-hard: there is a constant δ>0 such that there is no (1+δ)-approximation algorithm for the minimum dominating set problem on circle graphs unless P=NP. Hence a PTAS for this problem seems unlikely. This hardness result complements the (2+?)-approximation algorithm for the problem [M. Damian, S.V. Pemmaraju, A (2+?)-approximation scheme for minimum domination on circle graphs, J. Algorithms 42 (2) (2002) 255-276].     

Equation of SVM-rebalancing: the point-normal form of a plane for class imbalance problem

The task of detecting a rare but important class has extensively been studied in the machine learning community. It is commonly agreed that traditional classifiers are certainly limited to imbalanced datasets and do not perform well. A number of solutions to the problem were proposed at both data and algorithmic levels. We propose the point-normal form of a plane, namely SVM-rebalancing, to be based on the second type. In this learning process, the assumption of pseudo-prior probabilities provides a rebalanced recipe for countering the imbalance inspired by Bayesian decision theory. Thus, we set a rebalancing programming problem by incorporating a rebalanced heuristics into the fitting of model to raise the class separability. In addition, various measures are used to characterize the performance of classifiers. Compared with several popular decision tree splitting criteria and cost-sensitive learning, the proposed method gives comparable separability with minority class to avoid heavy biasing of the majority class.

     

Learning from positive and unlabeled examples

In many machine learning settings, labeled examples are difficult to collect while unlabeled data are abundant. Also, for some binary classification problems, positive examples which are elements of the target concept are available. Can these additional data be used to improve accuracy of supervised learning algorithms? We investigate in this paper the design of learning algorithms from positive and unlabeled data only. Many machine learning and data mining algorithms, such as decision tree induction algorithms and naive Bayes algorithms, use examples only to evaluate statistical queries (SQ-like algorithms). Kearns designed the statistical query learning model in order to describe these algorithms. Here, we design an algorithm scheme which transforms any SQ-like algorithm into an algorithm based on positive statistical queries (estimate for probabilities over the set of positive instances) and instance statistical queries (estimate for probabilities over the instance space). We prove that any class learnable in the statistical query learning model is learnable from positive statistical queries and instance statistical queries only if a lower bound on the weight of any target concept f can be estimated in polynomial time. Then, we design a decision tree induction algorithm POSC4.5, based on C4.5, that uses only positive and unlabeled examples and we give experimental results for this algorithm. In the case of imbalanced classes in the sense that one of the two classes (say the positive class) is heavily underrepresented compared to the other class, the learning problem remains open. This problem is challenging because it is encountered in many real-world applications.     

Improved Approximation Algorithms for the Spanning Star Forest Problem

A star graph is a tree of diameter at most two. A star forest is a graph that consists of node-disjoint star graphs. In the spanning star forest problem, given an unweighted graph G, the objective is to find a star forest that contains all vertices of G and has the maximum number of edges. This problem is the complement of the dominating set problem in the following sense: On a graph with n vertices, the size of the maximum spanning star forest is equal to n minus the size of the minimum dominating set. We present a 0.71-approximation algorithm for this problem, improving upon the approximation factor of 0.6 of Nguyen et al. (SIAM J. Comput. 38:946–962, 2008). We also present a 0.64-approximation algorithm for the problem on node-weighted graphs. Finally, we present improved hardness of approximation results for the weighted (both edge-weighted and node-weighted) versions of the problem. Our algorithms use a non-linear rounding scheme, which might be of independent interest.