We consider the problem of routing n users on m parallel links, under the restriction that each user may only be routed on a link from a certain set of allowed links for the user. Thus, the problem is equivalent to th...
详细信息
We consider the problem of routing n users on m parallel links, under the restriction that each user may only be routed on a link from a certain set of allowed links for the user. Thus, the problem is equivalent to the correspondingly restricted problem of assigning n jobs to m parallel machines. In a pure Nash equilibrium, no user may improve its own individual cost (delay) by unilaterally switching to another link from its set of allowed links. As our main result, we introduce a polynomial time algorithm to compute from any given assignment a pure Nash equilibrium with non-increased makospan. The algorithm gradually changes a given assignment by pushing unsplittable user traffics through a network that is defined by the users and the links. Here, we use ideas from blocking flows. Furthermore, we use similar techniques as in the generic PREFLOW-PUSH algorithm to approximate a schedule with minimum makespan, gaining an improved approximation factor of 2 - 1/w1 for identical links, where w1 is the largest user traffic. We extend this result to related links, gaining an approximation factor of 2. Our approximation algorithms run in polynomial time. We close with tight upper bounds on the coordination ratio for pure Nash equilibria.
Let P be a set of n points in R3, not all in a common plane. We solve a problem of Scott (1970) by showing that the connecting lines of P assume at least 2n - 7 different directions if n is even and at least 2n - 5 if...
详细信息
Let P be a set of n points in R3, not all in a common plane. We solve a problem of Scott (1970) by showing that the connecting lines of P assume at least 2n - 7 different directions if n is even and at least 2n - 5 if n is odd. The bound for odd n is sharp.
Reusable software architecture (RSA) is playing an integral role in Component-Based Software Development (CBSD). This should assist productivity and increase software quality. This work looks at the identification of ...
详细信息
Reusable software architecture (RSA) is playing an integral role in Component-Based Software Development (CBSD). This should assist productivity and increase software quality. This work looks at the identification of the key factors that will assist with the development of an RSA. The work involves a formal specification of an RSA and its structures.
In the area of information retrieval, the dimension of document vectors plays an important role. Firstly, with higher index dimensions the indexing structures suffer from the "curse of dimensionality" and th...
详细信息
ISBN:
(纸本)193241536X
In the area of information retrieval, the dimension of document vectors plays an important role. Firstly, with higher index dimensions the indexing structures suffer from the "curse of dimensionality" and their efficiency rapidly decreases. Secondly, we may not use exact words when looking for a document, thus we miss some relevant documents. LSI (Latent Semantic Indexing) is a numerical method, which discovers latent semantic in documents by creating concepts from existing terms. In this article we present a basic method of mapping LSI concepts on given ontology (WordNet), used both for retrieval recall improvement and dimension reduction. We offer experimental results for this method on a subset of TREC collection, consisting of Los Angeles Times articles.
Let P be a set of n points in general position in the plane. Let X k(P) denote the number of empty convex k-gons determined by P. We derive, using elementary proof techniques, several equalities and inequalities invol...
详细信息
Let P be a set of n points in general position in the plane. Let X k(P) denote the number of empty convex k-gons determined by P. We derive, using elementary proof techniques, several equalities and inequalities involving the quantities Xk(P) and several related quantities. Most of these equalities and inequalities are new, except for a couple that have been proved earlier using a considerably more complex machinery from matroid and polytope theory, algebraic topology and commutative algebra. Some of these relationships are also extended to higher dimensions. We present several implications of these relationships, and discuss their connection with several long-standing open problems, the most notorious of which is the existence of an empty convex hexagon in any point set with sufficiently many points.
Tool support for Information Systems development can be considered from many perspectives, and it is not surprising that different stakeholders perceive such tools very differently. This can contribute on one side to ...
详细信息
ISBN:
(纸本)9728865007
Tool support for Information Systems development can be considered from many perspectives, and it is not surprising that different stakeholders perceive such tools very differently. This can contribute on one side to poor selection processes and ineffective deployment of CASE, and on another to inappropriate tool development. In this paper we consider the relationship between CASE tools and Information Systems development methods from three stakeholder perspectives: concept developer, Information Systems developer and product developer. These perspectives, and the tensions between them, are represented within a 'stakeholder triangle', which we use to consider how the concept of method-in-action affects and is affected by the concept of method-in-tool. We believe that the triangle helps when interpreting seemingly conflicting views about CASE adoption and development.
We present an automatic camera and mirrors placement method for visualizing 3D scenes such that complete and nonredundant visibility is guaranteed, as well as highest image resolution. We provide algorithms and geomet...
详细信息
We present an automatic camera and mirrors placement method for visualizing 3D scenes such that complete and nonredundant visibility is guaranteed, as well as highest image resolution. We provide algorithms and geometries for optimal object-independent mirrors and viewpoint placement for all objects in a specific class. We also briefly consider object-dependent algorithmic problems, where mirrors and viewpoints are positioned as a function of the object.
There are three major classes of lossless compression: fixed-to-variable (FV) length codes, variable-to-fixed (VF) length codes, and finally variable-to-variable (VV) length codes. This paper presents the construction...
详细信息
There are three major classes of lossless compression: fixed-to-variable (FV) length codes, variable-to-fixed (VF) length codes, and finally variable-to-variable (VV) length codes. This paper presents the construction and analysis of a VV-code with small average and maximal redundancy that decays to zero as the average code length increases. A variable-to-variable (VV) code is a concatenation of variable-to-fixed and fixed-to-variable codes.
The logistic delay equation with a linear delay harvesting term (Equation presented) is considered. The existence and the bounds of positive solutions are studied. Sufficient conditions for the extinction of the solut...
详细信息
This paper focuses on some robust control ideas applied to congestion control problems in high-performance network systems. Thus, we shall focus on the asymptotic stability of two nonlinear continuous-time fluid appro...
详细信息
ISBN:
(纸本)0889864012
This paper focuses on some robust control ideas applied to congestion control problems in high-performance network systems. Thus, we shall focus on the asymptotic stability of two nonlinear continuous-time fluid approximation models including constant or time-varying delays in their systems' representation. The key idea of our approach is represented by an uncertainty interpretation of the delays, combined with the construction of appropriate Lyapunov-Krasovskii functional for performing the stability analysis.
暂无评论