Comment on “Approximation algorithms for quadratic programming”

Journal of Combinatorial Optimization - The radius of the outer Dikin ellipsoid of the intersection of m ellipsoids due to Fu et al. (J. Comb. Optim., 2, 29-50, 1998) is corrected from m to...     

Polynomial time approximation scheme for t-latency bounded information propagation problem in?wireless?networks

Latency of information propagating in wireless network is gaining more and more attention recently. This paper studies the problem of t-Latency Bounded Information Propagation (t-LBIP) problem in wireless networks which are represented by unit-disk graphs. So far, no guaranteed approximation algorithm has been achieved for t-LBIP when t≥2. In this paper, we propose a Polynomial Time Approximation Scheme for t-LBIP under the condition that the maximum degree is bounded by a constant.     

Efficient algorithms for the max k -vertex cover problem

Given a graph  \(G(V,E)\) of order  \(n\) and a constant \(k \leqslant n\) , the max  \(k\) -vertex cover problem consists of determining  \(k\) vertices that cover the maximum number of edges in  \(G\) . In its (standard) parameterized version, max  \(k\) -vertex cover can be stated as follows: “given  \(G,\) \(k\) and parameter  \(\ell ,\) does  \(G\) contain  \(k\) vertices that cover at least  \(\ell \) edges?”. We first devise moderately exponential exact algorithms for max  \(k\) -vertex cover, with time-complexity exponential in  \(n\) but with polynomial space-complexity by developing a branch and reduce method based upon the measure-and-conquer technique. We then prove that, there exists an exact algorithm for max  \(k\) -vertex cover with complexity bounded above by the maximum among  \(c^k\) and  \(\gamma ^{\tau },\) for some \(\gamma < 2,\) where  \(\tau \) is the cardinality of a minimum vertex cover of  \(G\) (note that \({\textsc {max}}\,\) k \({\textsc {\!-vertex cover}}{} \notin \mathbf{FPT}\) with respect to parameter  \(k\) unless \(\mathbf{FPT} = \mathbf{W[1]}\) ), using polynomial space. We finally study approximation of max  \(k\) -vertex cover by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch-up on polynomial inapproximability, by providing algorithms achieving, with worst-case running times importantly smaller than those needed for exact computation, approximation ratios unachievable in polynomial time.     

Approximation and hardness results for label cut and related problems

We investigate a natural combinatorial optimization problem called the Label Cut problem. Given an input graph G with a source s and a sink t, the edges of G are classified into different categories, represented by a set of labels. The labels may also have weights. We want to pick a subset of labels of minimum cardinality (or minimum total weight), such that the removal of all edges with these labels disconnects s and t. We give the first non-trivial approximation and hardness results for the Label Cut problem. Firstly, we present an \(O(\sqrt{m})\)-approximation algorithm for the Label Cut problem, where m is the number of edges in the input graph. Secondly, we show that it is NP-hard to approximate Label Cut within \(2^{\log ^{1-1/\log\log^{c}n}n}\) for any constant c<1/2, where n is the input length of the problem. Thirdly, our techniques can be applied to other previously considered optimization problems. In particular we show that the Minimum Label Path problem has the same approximation hardness as that of Label Cut, simultaneously improving and unifying two known hardness results for this problem which were previously the best (but incomparable due to different complexity assumptions).     

Optimal on-line algorithms for one batch machine with grouped processing times

In this paper, we study on-line scheduling problems on a batch machine with the assumption that all jobs have their processing times in [p, (1+φ)p], where p>0 and \(\phi=(\sqrt{5}-1)/2\). Jobs arrive over time. First, we deal with the on-line problem on a bounded batch machine with the objective to minimize makespan. A class of algorithms with competitive ratio \((\sqrt{5}+1)/2\) are given. Then we consider the scheduling on an unbounded batch machine to minimize the time by which all jobs have been delivered, and provide a class of on-line algorithms with competitive ratio \((\sqrt{5}+1)/2\). The two class of algorithms are optimal for the problems studied here.     

An extension of the relaxation algorithm for solving a special case of capacitated arc routing problems

In this paper, we propose an exact method for solving a special integer program associated with the classical capacitated arc routing problems (CARPs) called split demand arc routing problems (SDARP). This method is developed in the context of monotropic programming theory and bases a promising foundation for developing specialized algorithms in order to solve general integer programming problems. In particular, the proposed algorithm generalizes the relaxation algorithm developed by Tseng and Bertsekas (Math. Oper. Res. 12(4):569–596, 1987) for solving linear programming problems. This method can also be viewed as an alternative for the subgradient method for solving Lagrangian relaxed problems. Computational experiments show its high potential in terms of efficiency and goodness of solutions on standard test problems.     

New algorithms for online rectangle filling with <Emphasis Type="BoldItalic">k</Emphasis>-lookahead

We study the online rectangle filling problem which arises in channel aware scheduling of wireless networks, and present deterministic and randomized results for algorithms that are allowed a k-lookahead for k≥2. Our main result is a deterministic min {1.848,1+2/(k−1)}-competitive online algorithm. This is the first algorithm for this problem with a competitive ratio approaching 1 as k approaches +∞. The previous best-known solution for this problem has a competitive ratio of 2 for any k≥2. We also present a randomized online algorithm with a competitive ratio of 1+1/(k+1). Our final result is a closely matching lower bound (also proved in this paper) of $1+1/(\sqrt{k+2}+\sqrt{k+1})^{2}>1+1/(4(k+2))$1+1/(\sqrt{k+2}+\sqrt{k+1})^{2}>1+1/(4(k+2)) on the competitive ratio of any randomized online algorithm against an oblivious adversary. These are the first known results for randomized algorithms for this problem.     

The role of self-determination theory in marketing science: An integrative review and agenda for research

The marketing literature is replete with the repeated use of traditional theories of behaviour, such as ‘the consumer decision model,’ the ‘theory of buyer behaviour,’ the ‘theory of reasoned action,’ the ‘theory of planned behaviour,’ and ‘the model of goal-directed behaviour.’ The conclusions and criticisms that are drawn from these theories stem from the many ways in which these theories are applied, which reduces the efficiency of these approaches in the sense of predictability and generalizability across different cultures. Moreover, these theories have minimal influence on autonomously motivated behaviours. Despite these limitations, marketing scientists have overwhelmingly applied these theories to predict consumer intention and behaviour. However, theories that are actually capable of explaining consumers' motivations have been surprisingly ignored in the marketing literature; for instance, ‘self-determination theory’ (SDT) is a leading theory of human motivation that has been proven effective at identifying the contingencies that affect motivation and behaviour. Therefore, the goal is to review the marketing research in which SDT is used. To this end, we review all empirical studies published on the subject over a 20-year period. Several clusters of research are identified in which SDT appears to be more promising in addressing marketing problems. Finally, we provide directions for future research in greater detail.