Search

This paper formulates a model of advertising prices in which a homogeneous product is not intended for sales at conventional stores. The product is sold by means of advertising instead. Applications of this model can be found on numerous sales activities include, for example, insurance companies, television shopping channels and Internet e-tailers who advertise their products and prices by sending e-mails to potential buyers or by means of popup windows. This paper makes endogenous both firm advertising and price strategies in the model. [ABSTRACT FROM AUTHOR]

This paper investigates the online scheduling problem on parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels. Hence each job and machine are labelled with the GoS levels, and each job can be processed by a particular machine only when the GoS level of the job is not less than that of the machine. The goal is to minimize the makespan. In this paper, we consider the problem with two GoS levels. It assumes that the GoS levels of the first k machines and the last m - k machines are 1 and 2, respectively, and every job has a GoS level of 1 alternatively or 2. We first prove the lower bound of the problem under consideration is at least 2. Then we discuss the performance of algorithm AW presented in [2] for the problem and show it has a tight bound of 4 - 1/m. Finally, We present an approximation algorithm with a competitive ratio of $\frac{12+4\sqrt{2}}{7}\approx 2.522$. Keywords: Online algorithm, Competitive analysis, Parallel machine scheduling, Grade of Service. [ABSTRACT FROM AUTHOR]

In this paper, a branch and bound algorithm for computing the treewidth of a graph is presented. The method incorporates extensions of existing results, and uses new pruning and reduction rules, based upon properties of the adopted branching strategy. We discuss how the algorithm can not only be used to obtain exact bounds for the treewidth, but also to obtain upper and/or lower bounds. Computational results of the algorithm are presented. [ABSTRACT FROM AUTHOR]

Discount auction is a market mechanism for buying heterogeneous items in a single auction. The suppliers submit discount bids, which consist of two parts: the individual cost for each of the items and discounts based on the number of items procured. The winner determination problem faced by the buyer is to determine the winning suppliers and their corresponding winning items, such that the total cost of procurement is minimized. This problem is ${\cal NP}$-hard and in this paper we propose a novel branch and bound algorithm called as branch on price, which uses a tight integer programming formulation with valid inequalities. Computational experiments show that the proposed algorithm is many folds faster than the existing algorithm. [ABSTRACT FROM AUTHOR]

This paper discusses the portfolio selection problem based on the possibilistic theory. The possibilistic portfolio model with general constraints to investment is proposed by means of possibilistic mean value and possibilistic variance. The conventional probabilistic mean-variance model can be simplified under the assumption that the returns of assets are triangular fuzzy numbers. Finally, a numerical example of the portfolio selection problem is given to illustrate our proposed effective means and approaches. [ABSTRACT FROM AUTHOR]

Due to the increasing security threats in the Internet, new overlay network architectures have been proposed to secure privileged services. In these architectures, the application servers are protected by a defense perimeter where only traffic from entities called servelets are allowed to pass. End users must be authorized and can only communicate with entities called access points (APs). APs relay authorized users' requests to servelets, which in turn pass them to the servers. The identity of APs are publicly known while the servelets are typically secret. All communications are done through the public Internet. Thus all the entities involved forms an overlay network. The main component of this distributed system consists of n APs. and m servelets. A design for a network is a bipartite graph with APs on one side, and the servelets on the other side. If an AP is compromised by an attacker, all the servelets that are connected to it are subject to attack. An AP is blocked, if all servelets connected to it are subject to attack. We consider two models for the failures: In the average case model, we assume that each AP i fails with a given probability pi. In the worst case model, we assume that there is an adversary that knowing the topology of the network, chooses at most k APs to compromise. In both models, our objective is to design the connections between APs and servelets to minimize the (expected/worst-case) number of blocked APs. In this paper, we give a polynomial-time algorithm for this problem in the average-case model when the number of servelets is a constant. We also show that if the probability of failure of each AP is at least 1/2, then in the optimal design each AP is connected to only one servelet (we call such designs star-shaped), and give a polynomial-time algorithm to find the best star-shaped design. We observe that this statement is not true if the failure probabilities are small. In the worst-case model, we show that the problem is related to a problem in combinatorial set theory, and use this connection to give bounds on the maximum number of APs that a perfectly failure-resistant design with a given number of servelets can support. Our results provide the first rigorous theoretical foundation for practical secure overlay network design. Keywords: network design, network security, optimization, combinatorics. [ABSTRACT FROM AUTHOR]

In this paper, I present a frequency reassignment problem (FRP) arising from the installation of new base stations for capacity expansion in mobile telecommunication systems, and develop an integer programming (IP) formulation along with some valid inequalities. Also, I develop a novel decomposition based heuristic algorithm. Computational results show that the developed valid inequalities are quite strong, and that the developed heuristic algorithm finds a feasible solution of good quality within reasonable time bound. [ABSTRACT FROM AUTHOR]

We study the λ-seed problem of a string in this paper. Given a string x of length n and an integer λ, the λ-seed problem is to find all the sets of λ substrings of x that cover a superstring of x, assuming that each element of the set is of equal length. We present an efficient algorithm that can compute all the λ-seeds of x in O(n2) time. [ABSTRACT FROM AUTHOR]

In this paper we present the first set of approximation and inapproximability results for the Exemplar Breakpoint Distance Problem. Our inapproximability results hold for the simplest case between only two genomes ${\cal G}$ and ${\cal H}$, each containing only one sequence of genes (possibly with repetitions). - For the general Exemplar Breakpoint Distance Problem, we prove that the problem does not admit any approximation unless P=NP; in fact, this result holds even when a gene appears in ${\cal G}$ (${\cal H}$) at most three times. - Even on a weaker definition of approximation (which we call weak approximation), we show that the problem does not admit a weak approximation with a factor m1-ε, where m is the maximum length of ${\cal G}$ and ${\cal H}$. - We present a factor-2(1 + logn) approximation for an interesting special case, namely, one of the two genomes is a k-span genome (i.e., all genes in the same gene family are within a distance k = O(logn)), where n is the number of gene families in ${\cal G}$ and ${\cal H}$. [ABSTRACT FROM AUTHOR]

In this paper, we consider the quickest flow problem in a network which consists of a directed graph with capacities and transit times on its arcs. We present an O(n logn) time algorithm for the quickest flow problem in a network of grid structure with uniform arc capacity which has a single sink where n is the number of vertices in the network. [ABSTRACT FROM AUTHOR]

The bottleneck optimization problem is to find a feasible solution that minimizes the bottleneck cost. In this paper, we consider the inverse bottleneck optimization problems with bound constraints on modification under weighted l1 norm, weighted sum-Hamming distance and weighted bottleneck-Hamming distance. That is, given a feasible solution F*, we aim to modify the cost function under some measure such that F* becomes an optimal solution to the bottleneck optimization problem. We show that the inverse problem under weighted l1 norm and weighted sum-Hamming distance can be reduced to O(m) minimum cut problems, while the inverse problem under weighted bottleneck-Hamming distance can be reduced to O(logm) cut feasibility problems, where m = E. [ABSTRACT FROM AUTHOR]

In this paper we deal with sensitivity analysis of combinatorial optimization problems and its fundamental term, the tolerance. For three classes of objective functions ($\Sigma, \Pi, {\mbox{MAX}}$) we give some basic properties on upper and lower tolerances. We show that the upper tolerance of an element is well defined, how to compute the upper tolerance of an element, and give equivalent formulations when the upper tolerance is +∞ or > 0. Analogous results are given for the lower tolerance and some results on the relationship between lower and upper tolerances are given. Keywords: Sensitivity analysis, upper tolerance, lower tolerance. [ABSTRACT FROM AUTHOR]

It is well known that faithful (i.e. dependency preserving) decompositions of relational database schemas into Boyce-Codd Normal Form (BCNF) do not always exist, depending on the set of functional dependencies given, and that the corresponding decision problem is NP-hard. The only algorithm to guarantee both faithfulness and BCNF (if possible) proposed so far in [Os79] is a brute-force approach which always requires exponential time. To be useful in practice, e.g. in automated design tools, we require more efficient means. In this paper we present an algorithm which always finds a faithful BCNF decomposition if one exists, and which is usually efficient, and exponential only in notorious cases. [ABSTRACT FROM AUTHOR]

We study the nonpreemptive online scheduling of jobs with deadlines and weights. The goal of the scheduling algorithm is to maximize the total weight of jobs completed by their deadlines. As a special case, the weights may be given as the processing times of jobs, where the job instance is said to have uniform value density. Most previous work of nonpreemptively scheduling jobs online concentrates on a single machine and uniform value density. For the single machine, Goldwasser [6] shows a matching upper bound and lower bound of $(2 + \frac{1}{\kappa})$ on the best competitive ratio, where every job can be delayed for at least κ times its processing time before meeting its deadline. This paper is concerned with multiple machines. We provide a $(7 + 3\sqrt{\frac{1}{\kappa}})$-competitive algorithm defined on multiple machines. Also we consider arbitrary value density, where jobs have arbitrary weights. We derive online scheduling algorithms on a single machine as well as on multiple machines. [ABSTRACT FROM AUTHOR]

In this paper, motivated by on-line admission control in the hard deadline model, we deal with the following scheduling problem. We are given m identical machines (multi-streams). All jobs (requests) have identical processing time. Each job is associated with a release time and a deadline, neither of which is known until the job arrives. As soon as a job is available, we must immediately decide if the job is accepted or rejected. If a job is accepted, then it must be completed no later than its deadline. The goal is to maximize the total number of jobs accepted. The one-machine case has been extensively studied while little is known for multiple machines. Our main result is deriving a nontrivial optimal online algorithm with competitive ratio $\frac{3}{2}$ for the two-machine case by carefully investigating various strategies. Deterministic lower bounds for the general case are also given. [ABSTRACT FROM AUTHOR]