Algorithmic Applications in Management
First International Conference, AAIM 2005, **an, China, June 22-25, 2005. Proceedings
Article
Scientists aim to discover meaningful formulae that accurately describe experimental data. Mathematical models of natural phenomena can be manually created from domain knowledge and fitted to data, or, in cont...
Chapter and Conference Paper
Plankton is one of the most abundant and diverse class of microscopic organisms inhabiting the Earth. Their enormous intra- and inter-species genetic and phenotypic diversity, coupled with the limited amount o...
Chapter and Conference Paper
In this paper we study the traitor tracing problem for re-broadcasting attack. In this attack, instead of building a pirate clone device (or program) based on their secret keys and sell the clone, the attacker...
Chapter and Conference Paper
The standard so-called experts algorithms are methods for utilizing a given set of “experts” to make good choices in a sequential decision-making problem. In the standard setting of experts algorithms, the dec...
Chapter and Conference Paper
Continuity of the map** from initial endowments and utilities to equilibria is an essential property for a desirable model of an economy – without continuity, small errors in the observation of parameters of...
Chapter and Conference Paper
When comparing alternative query execution plans (qeps), a cost-based query optimizer in a relational database management system (rdbms) needs to estimate the selectivity of conjunctive predicates. The optimizer ...
Book and Conference Proceedings
First International Conference, AAIM 2005, **an, China, June 22-25, 2005. Proceedings
Article
The layered-step interior-point algorithm was introduced by Vavasis and Ye. The algorithm accelerates the path following interior-point algorithm and its arithmetic complexity depends only on the coefficient m...
Chapter and Conference Paper
Analysts predominantly use OLAP data cubes to identify regions of anomalies that may represent problem areas or new opportunities. The current OLAP systems support hypothesis-driven exploration of data cubes t...
Article
The complexity of algorithms that compute strategies or operate on them typically depends on the representation length of the strategies involved. One measure for thesize of a mixed strategy is the number of stra...
Article
This paper, of which a preliminary version appeared in ISTCS'92, is concerned with generalized network flow problems. In a generalized network, each edgee = (u, v) has a positive ‘flow multiplier’a ...
Article
Several network-flow problems with additional constraints are considered. They are all special cases of the linear-programming problem and are shown to be ℘-complete. It is shown that the existence of a strong...
Book
Chapter
The analogs of pure, mixed and behavior strategies in the context of algorithms are studied. It is shown that probabilistic machines are more powerful than probability distributions over deterministic ones, th...
Article
As in many primal—dual interior-point algorithms, a primal—dual infeasible-interior-point algorithm chooses a new point along the Newton direction towards a point on the central trajectory, but it does not con...
Article
This paper proposes two sets of rules, Rule G and Rule P, for controlling step lengths in a generic primal—dual interior point method for solving the linear programming problem in standard form and its dual. T...
Article
The problem of integer programming in bounded variables, over constraints with no more than two variables in each constraint is NP-complete, even when all variables are binary. This paper deals with integer li...
Chapter
Blum, Shub, and Smale [2] formalized a model of computation over a general ring. They proved an analogue of Cook’s theorem [3] over the reals. Smale [4] has recently raised the question of existence of NP-comp...
Article
The linear complementarity problem (LCP) can be viewed as the problem of minimizingx T y subject toy=Mx+q andx, y⩾0. We are interested in finding a point withx T y <ε for a givenε > 0. The algorithm proceeds by i...
Chapter and Conference Paper
This paper is concerned with generalized network flow problems. In a generalized network, each edge e=(u, v) has a positive “flow multiplier” a e associated with it. The interpretation is that if a flow of x e en...