ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • Articles  (15,093)
  • Springer  (15,041)
  • Blackwell Publishers Inc  (52)
  • American Chemical Society
  • 1995-1999  (15,093)
  • Computer Science  (15,093)
Collection
  • Articles  (15,093)
Source
Keywords
Publisher
Years
Year
Journal
Topic
  • 1
    Electronic Resource
    Electronic Resource
    Scalability in Formal Concept Analysis (1999)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: Formal Concept Analysis is a symbolic learning technique derived from mathematical algebra and order theory. The technique has been applied to a broad range of knowledge representation and exploration tasks in a number of domains. Most recorded applications of Formal Concept Analysis deal with a small number of objects and attributes, in which case the complexity of the algorithms used for indexing and retrieving data is not a significant issue. However, when Formal Concept Analysis is applied to exploration of a large numbers of objects and attributes, the size of the data makes issues of complexity and scalability crucial.This paper presents the results of experiments carried out with a set of 4,000 medical discharge summaries in which were recognized 1,962 attributes from the Unified Medical Language System (UMLS). In this domain, the objects are medical documents (4,000) and the attributes are UMLS terms extracted from the documents (1,962). When Formal Concept Analysis is used to iteratively analyze and visualize these data, complexity and scalability become critically important.Although the amount of data used in this experiment is small compared with the size of primary memory in modern computers, the results are still important because the probability distributions that determine the efficiencies are likely to remain stable as the size of the data is increased.Our work presents two outcomes. First, we present a methodology for exploring knowledge in text documents using Formal Concept Analysis by employing conceptual scales created as the result of direct manipulation of a line diagram. The conceptual scales lead to small derived purified contexts that are represented using nested line diagrams. Second, we present an algorithm for the fast determination of purified contexts from compressed representation of the large formal context. Our work draws on existing encoding and compression techniques to show how rudimentary data analysis can lead to substantial efficiency improvements in knowledge visualization.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00079
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Referees (1998)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 14 (1998), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00071
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Utilizing Moment Invariants and Gröbner Bases to Reason About Shapes (1998)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 14 (1998), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: Shapes such as triangles or rectangles can be defined in terms of geometric properties invariant under a group of transformations. Complex shapes can be described by logic formulas with simpler shapes as the atoms. A standard technique for computing invariant properties of simple shapes is the method of moment invariants, known since the early 1960s. We generalize this technique to shapes described by arbitrary monotone formulas (formulas in propositional logic without negation). Our technique produces a reduced Gröbner basisfor approximate shape descriptions. We show how to use this representation to solve decision problems related to shapes. Examples include determining if a figure has a particular shape, if one description of a shape is more general than another, and whether a specific geometric property is really necessary for specifying a shape. Unlike geometry theorem proving, our approach does not require the shapes to be explicitly defined. Instead, logic formulas combined with measurements performed on actual shape instances are used to compute well-characterized least squares approximations to the shapes. Our results provide a proof that decision problems stated in terms of these approximations can be solved in a finite number of steps.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00072
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Inferring dependencies from relations: a conceptual clustering approach (1999)
    Oxford, UK and Boston, USA : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: In this paper we consider two related types of data dependencies that can hold in a relation: conjunctive implication rules between attribute-value pairs, and functional dependencies. We present a conceptual clustering approach that can be used, with some small modifications, for inferring a cover for both types of dependencies. The approach consists of two steps. First, a particular clustered representation of the relation, called concept (or Galois) lattice, is built. Then, a cover is extracted from the lattice built in the earlier step. Our main emphasis is on the second step. We study the computational complexity of the proposed approach and present an experimental comparison with other methods that confirms its validity. The results of the experiments show that our algorithm for extracting implication rules from concept lattices clearly outperforms an earlier algorithm, and suggest that the overall lattice-based approach to inferring functional dependencies from relations can be seen as an alternative to traditional methods.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00100
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Constructing and Utilizing a Model of User Preferences in Collaborative Consultation Dialogues (1999)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: A natural language collaborative consultation system must take user preferences into account. A model of user preferences allows a system to appropriately evaluate alternatives using criteria of importance to the user. Additionally, decision research suggests both that an accurate model of user preferences could enable the system to improve a user's decision-making by ensuring that all important alternatives are considered, and that such a model of user preferences must be built dynamically by observing the user's actions during the decision-making process. This paper presents two strategies: one for dynamically recognizing user preferences during the course of a collaborative planning dialogue and the other for exploiting the model of user preferences to detect suboptimal solutions and suggest better alternatives. Our recognition strategy utilizes not only the utterances themselves but also characteristics of the dialogue in developing a model of user preferences. Our generation strategy takes into account both the strength of a preference and the closeness of a potential match in evaluating actions in the user's plan and suggesting better alternatives. By modeling and utilizing user preferences, our system is able to fulfill its role as a collaborative agent.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00091
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Compiling Ramification Constraints into Effect Axioms (1999)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: We present a method to derive a solution to the combined frame and ramification problems for certain classes of theories of action written in the situation calculus. The theories of action considered include the causal laws of the domain, in the form of a set of effect axioms, as well as a set of ramification state constraints. The causal laws state the direct effects that actions have on the world, and ramification state constraints allow one to derive indirect effects of actions on the domain.To solve the combined frame and ramification problems, the causal laws and ramification state constraints are replaced by a set of successor state axioms. Given a state of the world, these axioms uniquely determine the truth value of dynamic properties after an action is performed. In this article, we extend previous work by formulating an approach for the mechanical generation of these successor state axioms. We make use of the notions of implicate and support that have been developed in the context of propositional theories. The approach works for classes of syntactically restricted sets of ramification state constraints.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00094
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Knowledge Retrieval, Use and Storage for Efficiency (1999)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: The Knowledge Retrieval, Use and Storage for Efficiency (KRUSE) symposiums aim at providing a forum for research related to efficient processing and management of complex information and knowledge. This special issue presents selected articles from the KURSE'97 symposium held in Vancouver, Canada. In this introductory article we describe the goals of KRUSE and present some background topics that are fundamental to the articles herein. In particular, we provide an overview of partial order theory, formal concept analysis and taxonomic encoding. We also outline the articles that follow.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00078
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Probabilistic Inference in Influence Diagrams (1998)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 14 (1998), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: This paper is about reducing influence diagram (ID) evaluation into Bayesian network (BN) inference problems that are as easy to solve as possible. Such reduction is interesting because it enables one to readily use one's favorite BN inference algorithm to efficiently evaluate IDs. Two such reduction methods have been proposed previously (Cooper 1988; Shachter and Peot 1992). This paper proposes a new method. The BN inference problems induced by the new method are much easier to solve than those induced by the two previous methods.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00073
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Toward a Model Theory of Actions: How Agents do it in Branching Time (1998)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 14 (1998), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: A clear understanding and formalization of actions is essential to computing, and especially so to reasoning about and constructing intelligent agents. Several approaches have been proposed over the years. However, most approaches concentrate on the causes and effects of actions, but do not give general characterizations of actions themselves. A useful formalization of actions would be based on a general, possibly nondiscrete, model of time that allows branching (to capture agents’ choices). A desirable formalization would also allow actions to be of arbitrary duration and would permit multiple agents to act concurrently. We develop a branching-time framework that allows great flexibility in how time and action are modeled. We motivate and formalize several coherence constraints on our models, which capture some nice intuitions and validate some useful inferences relating actions with time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00064
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Pattern Databases (1998)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 14 (1998), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: The efficiency of A* searching depends on the quality of the lower bound estimates of the solution cost. Pattern databases enumerate all possible subgoals required by any solution, subject to constraints on the subgoal size. Each subgoal in the database provides a tight lower bound on the cost of achieving it. For a given state in the search space, all possible subgoals are looked up in the pattern database, with the maximum cost over all lookups being the lower bound. For sliding tile puzzles, the database enumerates all possible patterns containing N tiles and, for each one, contains a lower bound on the distance to correctly move all N tiles into their correct final location. For the 15-Puzzle, iterative-deepening A* with pattern databases(N ="8) reduces the total number of nodes searched on a standard problem set of 100 positions by over 1000-fold.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00065
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 11
    Electronic Resource
    Electronic Resource
    A Temporal Knowledge Representation Approach Based on Elementary Calculus (1997)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 13 (1997), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: The standard AI method for representing temporal information in a first-order logic is to directly associate the information with a time point or interval via a relation. We present a new paradigm for temporal knowledge representation. All point-based temporal information is translated to real-valued functions in the Cartesian plane. For example, information that is true/false at a point becomes a 0–1 function. Other types of information, such as velocity, are directly represented with real-valued functions. The unique feature of the proposed approach is the use of the Riemann integral to represent interval-based information. Our approach is based on the fact that what is true at every point in an interval completely determines what is true over the interval. We conclude with a formal presentation of a first-order logic that is based on the proposed representation.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00048
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 12
    Electronic Resource
    Electronic Resource
    Types of Contexts and Their Role in Multimodal Communication (1997)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 13 (1997), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: In this paper the idea is presented that human communication is carried through messages that are the result of the integration of a set of communicative acts, some of which are, in a traditional view, contextual phenomena with respect to a main (linguistic) communication act. A formalization of the notion of communicative situation is attempted, which eliminates the distinction between context and main communication acts. The ideas presented in this paper come from a re-thinking of a prototype implemented in 1989 for the ESPRIT Project 527, CFID whose main features are presented in Section 4.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00045
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 13
    Electronic Resource
    Electronic Resource
    A Pattern-Based Approach Using Compound Unit Recognition and Its Hybridization with Rule-Based Translation (1999)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: This paper describes a compound unit (CU) recognizer as a pattern-based approach and its hybridization with rule-based translation. A compound unit is a combined concept including collocations, idioms, and compound nouns. CU recognition reduces part of speech ambiguities by combining several words into a unit and consequently lessening the parsing load. It also provides pretranslated natural equivalents. Our focus in this paper is to obtain flexibility and efficiency from pattern-based machine translation, and high-quality translation by hybridization. A modified trie, our search index structure using “method” strategy is used to manage heterogeneous property of the constituents. Syntactic verification is integrated to obtain precise CU recognition by means of pruning wrongly recognized units that are caused by improper variable hypotheses. The experimental result with verification shows that the precision of CU recognition is increased to 99.69% with 31 CFG rules on the cyclic trie structure for 1,268 Wall Street Journal articles of the Penn Treebank. Another experiment with CU recognition also shows that it raises the understandability of translation for Web documents.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00087
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 14
    Electronic Resource
    Electronic Resource
    English-Thai Translation: Initial Experiments with a Multiphase Translation System (1999)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: A multiphase machine translation approach, Generate and Repair Machine Translation (GRMT), is proposed. GRMT is designed to generate accurate translations that focus primarily on retaining the linguistic meaning of the source language sentence. GRMT presently incorporates a limited multilingual translation capability. The central idea behind the GRMT approach is to generate a translationcandidate (TC) by quick and dirty machine translation (QDMT), then investigate the accuracy of that TC by translation candidate evaluation (TCE), and, if necessary, revise the translation in the repair and iterate (RI) phase. To demonstrate the GRMT approach, a translation system that translates from English to Thai has been developed. This paper presents the design characteristics and some experimental results of QDMT and also the initial design, some experiments, and proposed ideas behind TCE and RI.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00088
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 15
    Electronic Resource
    Electronic Resource
    The 6-49 Lottery Paradox (1998)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 14 (1998), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: The paradox of the preface and the lottery paradox are paradoxes of practical certainty sharing certain features. The paradox of the lottery argues that rational agents are at once practically certain that each ticket in a lottery will lose but also practically certain some ticket will win. The paradox of the preface argues that rational agents are at once practically certain that all facts in a written volume are true, yet are also practically certain that some fact is wrong. A difference between real lotteries and prefaces is that a winning lottery ticket is generally an intended feature of the lottery, whereas incorrect facts are generally unintended.Despite these similarities, Pollock gives a novel argument suggesting that the preface paradox warrants qualitatively different treatment from the lottery, using as a rationale the differences between real lotteries and prefaces. This draws a clear line between the work of Pollock and the work of Kyburg, both of whom have had a prominent influence in recent thinking on nonmonotonic reasoning in AI.This note shows there are real lotteries with the formal structure of the preface paradox and possibly prefaces with the formal structure of lotteries. The surprising conclusion is that within Pollock's framework, the treatment of any problem with a formal structure resembling the lottery (or the preface) depends on the process by which winning tickets (or publishing errors) are generated. The rationales given by Pollock seem to be unrelated to the actual mechanisms implemented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00063
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 16
    Electronic Resource
    Electronic Resource
    Decomposing and Solving Timetabling Constraint Networks (1997)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 13 (1997), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: The binary version of the school timetabling (STT) problem is a real-world example of a constraint network that includes only constraints of inequality. A new and useful representation for this real-world problem, the STT_Grid, leads to a generic decomposition technique. The paper presents proofs of necessary and sufficient conditions for the existence of a solution to decomposed STT_Grids. The decomposition procedure is of low enough complexity to be practical for large problems, such as a real-world high school.To test the decomposition approach, a typical high school was analyzed and used as a model for generating STT_Grids of various sizes. Experiments were conducted to test the difficulty of large STT networks and their solution by decomposition. The experimental results show that the decomposition procedure enables the solution of large STT_Grids (620 variables for a real school) in reasonable time. The constraint network of a typical STT_Grid is sparse and belongs to the class of easy problems. Still, due to the sizes of STTs, good constraint satisfaction problem search techniques (i.e., BackJumping and ForwardChecking) do not terminate in reasonable times for STT_Grids that are larger than 300 variables.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00049
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 17
    Electronic Resource
    Electronic Resource
    Regularity-based Perceptual Grouping (1997)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 13 (1997), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: This paper investigates perceptual grouping from a logical point of view, defining a grouping interpretation as a particular kind of logical expression, and then developing an explicit inference theory in terms of such expressions. First, a regularity-based interpretation language is presented, in which an observed configuration is characterized in terms of the regularities(special configurational classes, e.g. nonaccidental properties) it obeys. The most preferred interpretation in such a system is shown to be the most-regular (maximum “codimension”) model the observed configuration obeys, which is also the unique model in which it is generic(typical). Inference then reduces to a straiightforward exercise in LogicProgramming. Because generic model assignment involves negation, this reduction requires that a version of the Closed World Assumption (CWA) be adopted.Next, this entire regularity-based machinery is generalized to the grouping problem: here an interpretation is a hierarchical recursive) version of a model called a parse tree.For a given number of dots and a fixed choice of regularity set, it is possible to explicitly enumerate the complete set of possible grouping interpretations, partially ordered by their degree of regularity (codimension). The most preferred interpretation is the one with maximum codimension (i.e., the most regular interpretation), which we call the qualitative parse. An efficient procedure (worst case $O(n^2)$) for finding the qualitative parse is presented. The qualitative parse has a unique epistemic status: given a choice of regularity set, it is the only grouping interpretation that both (a) is maximally regular, and (b) satisfies the CWA. This unique status, it is argued, accounts for the perceptually compelling quality of the qualitative parse.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00052
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 18
    Electronic Resource
    Electronic Resource
    Aggregation in Natural Language Generation (1999)
    Oxford, UK and Boston, USA : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: The content of real-world databases, knowledge bases, database models, and formal specifications is often highly redundant and needs to be aggregated before these representations can be successfully paraphrased into natural language. To generate natural language from these representations, a number of processes must be carried out, one of which is sentence planning where the task of aggregation is carried out. Aggregation, which has been called ellipsis or coordination in Linguistics, is the process that removes redundancies during generation of a natural language discourse, without losing any information.The article describes a set of corpus studies that focus on aggregation, provides a set of aggregation rules, and finally, shows how these rules are implemented in a couple of prototype systems. We develop further the concept of aggregation and discuss it in connection with the growing literature on the subject. This work offers a new tool for the sentence planning phase of natural language generation systems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00099
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 19
    Electronic Resource
    Electronic Resource
    Title Index for Volume 15 (1999)
    Oxford, UK and Boston, USA : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/1467-8640.00102
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 20
    Electronic Resource
    Electronic Resource
    Introduction to the Special Issue on PACLING '97 (1999)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00084
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 21
    Electronic Resource
    Electronic Resource
    Retrieving Domain-Specific Collocations by Co-occurrences and Word Order Constraints (1999)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: In this paper, we describe a method for automatically retrieving collocations from large text corpora. This method comprises the following stages: (1) extracting strings of characters as units of collocations, and (2) extracting recurrent combinations of strings as collocations. Through this method, various types of domain-specific collocations can be retrieved simultaneously. This method is practical because it uses plain text with no specific-language-dependent information, such as lexical knowledge and parts of speech. Experimental results using English and Japanese text corpora show that the method is equally applicable to both languages.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00085
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 22
    Electronic Resource
    Electronic Resource
    Cooperative Understanding of Utterances and Gestures in a Dialogue-Based Problem Solving System (1999)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: A dialogue plays an important role in learning how to solve a problem and form a concept. We are developing a problem solving and knowledge acquisition system based on co-reference between drill texts and dialogue with a teacher, focusing on first-grade mathematics. This paper presents a method of cooperative understanding of utterances and gestures within dialogue. We first describe our system design principles, which provide the basis for the integration of multimodal information during a dialogue. We define a principle of complementarity, explain its implementation, and describe the architecture of the problem solving system. We then show how to integrate our algorithms for utterance and gesture analysis within that software architecture. A feature-based approach is used for gesture recognition, derived from a sequence of images arising during the cooperative analysis of utterances. We conclude with an evaluation of the system against the design principles.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00089
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 23
    Electronic Resource
    Electronic Resource
    Default Reasoning and Generics (1997)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 13 (1997), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: There are numerous logical formalisms capable of drawing conclusions using default rules. Such systems, however, do not normally determine where the default rules come from; i.e., what it is that makes Birds flya good rule, but Birds drive trucksa bad one.Generic sentences such as Birds fly are often used informally to describe default rules. I propose to take this characterization seriously, and claim that a default rule is adequate if the corresponding generic sentence is true. Thus, if we know that Tweety is a bird, we may conclude by default that Tweety flies, just in case Birds fly is a true sentence.In this paper, a quantificational account of the semantics of generic sentences is presented. It is argued that a generic sentence is evaluated not in isolation, but with respect to a set of relevant alternatives. For example, Mammals bear live young is true because among mammals that bear live young, lay eggs, undergo mitosis, or engage in some alternative form of procreation, the majority bear live young. Since male mammals do not procreate in any form, they do not count. Some properties of alternatives are presented, and their interactions with the phenomena of focus and presupposition is investigated.It is shown how this account of generics can be used to characterize adequate default reasoning systems, and several desirable properties of such systems are proved. The problems of the automatic acquisition of rules from natural language are discussed. Because rules are often explicitly expressed as generics, it is argued that the interpretation of generic sentences plays a crucial role in this endeavor, and it is shown how the theory presented here can facilitate such interpretation.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00050
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 24
    Electronic Resource
    Electronic Resource
    Conversational Actions and Discourse Situations (1997)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 13 (1997), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: We use the idea that actions performed in a conversation become part of the common ground as the basis for a model of context that reconciles in a general and systematic fashion the differences between the theories of discourse context used for reference resolution, intention recognition, and dialogue management. We start from the treatment of anaphoric accessibility developed in discourse representation theory (DRT), and we show first how to obtain a discourse model that, while preserving DRT's basic ideas about referential accessibility, includes information about the occurrence of speech acts and their relations. Next, we show how the different kinds of ‘structure’ that play a role in conversation—discourse segmentation, turn-taking, and grounding—can be formulated in terms of information about speech acts, and use this same information as the basis for a model of the interpretation of fragmentary input.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00042
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 25
    Electronic Resource
    Electronic Resource
    AI Can Rival Control Theory for Goal Achievement in a Challenging Dynamical System (1999)
    Oxford, UK and Boston, USA : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: Nonlinear dynamical systems are notoriously difficult to control. The Acrobot is an under-actuated double pendulum in a gravitational field. Under most driving schemes the Acrobot exhibits chaotic behavior. But with careful applications of energy it is possible to gradually pump the system so as to swing it over its supporting joint. This swing-up task is of current interest to control theory researchers.Conventional notions of AI planning are not easily extended to domains with interacting continuously varying quantities. Such continuous domains are often dynamic; important properties change over time even when no action is taken. Noise and error propagation can preclude accurately characterizing the effects of actions or predicting the trajectory of an undisturbed system through time. A plan must be a conditional action policy or a control strategy that carefully nudges the system as it strays from a desired course. Automatically generating such plans or action strategies is the subject of this research.An AI system successfully learns to perform the swing-up task using an approach called explanation-based control (EBC). The approach combines a plausible qualitative domain theory with empirical observation. Results are in some respects superior to the known control theory strategies. Of particular importance to AI is EBC's notion of a “plan” or “strategy” and its method for automatic synthesis. Experimental evidence confirms EBC's ability and generality.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00097
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 26
    Electronic Resource
    Electronic Resource
    Efficient Processing of Queries and Assertions about Qualitative and Quantitative Temporal Constraints (1999)
    Oxford, UK and Boston, USA : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: A critical problem for managers of temporal information is the treatment of assertions and of complex types of queries because in many cases the treatment could involve reasoning on the whole knowledge base of temporal constraints. We propose an efficient approach to this problem. First, we show how different types of queries can be answered (in a complete way) in a time polynomial in the dimension of the query and independently of the dimension of the knowledge base. Second, we provide an efficient (and complete) procedure to deal with sessions of interleaved assertions and queries to the knowledge base. We provide both analytical and experimental evaluations of our approach, and we discuss some application areas.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00101
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 27
    Electronic Resource
    Electronic Resource
    Feasible Formation of Coalitions Among Autonomous Agents in Nonsuperadditive Environments (1999)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: Cooperating and sharing resources by creating coalitions of agents are important ways for autonomous agents to execute tasks and to maximize payoff. Such coalitions will form only if each member of a coalition gains more by joining the coalition than it could gain otherwise. There are several ways of creating such coalitions and dividing the joint payoff among the members. In this paper we present algorithms for coalition formation and payoff distribution in nonsuperadditive environments. We focus on a low-complexity kernel-oriented coalition formation algorithm. The properties of this algorithm were examined via simulations. These have shown that the model increases the benefits of the agents within a reasonable time period, and more coalition formations provide more benefits to the agents.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00092
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 28
    Electronic Resource
    Electronic Resource
    Integrating Case-Based and Rule-Based Reasoning to Meet Multiple Design Constraints (1999)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: Although case-based reasoning (CBR) was introduced as an alternative to rule-based reasoning (RBR), there is a growing interest in integrating it with other reasoning paradigms, including RBR. New hybrid approaches are being piloted to achieve new synergies and improve problem-solving capabilities. In our approach to integration, CBR is used to satisfy multiple numeric constraints, and RBR allows the performance of “what if” analysis needed for creative design.The domain of our investigation is nutritional menu planning. The task of designing nutritious, yet appetizing, menus is one at which human experts consistently outperform computer systems. Tailoring a menu to the needs of an individual requires satisfaction of multiple numeric nutrition constraints plus personal preference goals and aesthetic criteria.We first constructed and evaluated independent CBR and RBR menu planning systems, then built a hybrid system incorporating the strengths of each system. The hybrid outperforms either single strategy system, designing superior menus, while synergistically providing functionality that neither single strategy system could provide. In this paper, we present our hybrid approach, which has applicability to other design tasks in which both physical constraints and aesthetic criteria must be met.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00095
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 29
    Electronic Resource
    Electronic Resource
    Resolving Ambiguous Segmentation of Korean Compound Nouns Using Statistics and Rules (1999)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: Korean compound nouns may be written as a sequence of characters without blanks between unit nouns. For Korean processing systems, Korean compound nouns have to be first segmented into a sequence of unit nouns. However, the segmentation task is difficult because a sequence of characters may be ambiguously segmented to several sequences of appropriate unit nouns. Moreover, this task is not trivial because Korean compound nouns may include many unknown unit nouns.This paper proposes a new method for KCNS (Korean Compound Noun Segmentation) and reports on the appliccation of such a segmentationtechnique to enhance the performance of an information retrieval system. According to our method, compound nouns are first segmented by using a dictionary and structure patterns. If they are ambiguously segmented, we resolve the ambiguities by using statistical information and a preference rule. Moreover, we employ three kinds of heuristics in order to segment compound nouns with unknown unit nouns.To evaluate KCNS, we use three kinds of data from various domains. Experimental results show that the precision of KCNS's output is approximately 96% on average, regardless of domains. The effectiveness of using the segmented unit nouns provided by KCNS for indexing is proved by improving retrieval performance of our information retrieval system.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00086
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 30
    Electronic Resource
    Electronic Resource
    Knowledge Discovery in Complex Objects (1999)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: Learning concepts and rules from structured (complex) objects is a quite challenging but very relevant problem in the area of machine learning and knowledge discovery. In order to take into account and exploit the semantic relationships that hold between atomic components of structured objects, we propose a knowledge discovery process, which starts from a set of complex objects to produce a set of related atomic objects (called contexts). The second step of the process makes use of the concatenation product to get a global context in which binary relations of individual contexts coexist with relations produced by the application of some operators to individual contexts. The last step permits the discovery of concepts and implication rules using the concept lattice as a framework in order to discover and interpret nontrivial concepts and rules that may relate different components of complex objects. This paper focuses on two main steps of the knowledge discovery process, namely data mining and interpretation.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00080
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 31
    Electronic Resource
    Electronic Resource
    Efficient Implementation of Semantic Relations in Lexical Databases (1999)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: In this paper we develop a formalization of semantic relations that facilitates efficient implementations of relations in lexical databases or knowledge representation systems using bases. The formalization of relations is based on a modeling of hierarchical relations in Formal Concept Analysis. Further, relations are analyzed according to Relational Concept Analysis, which allows a representation of semantic relations consisting of relational components and quantificational tags. This representation utilizes mathematical properties of semantic relations. The quantificational tags imply inheritance rules among semantic relations that can be used to check the consistency of relations and to reduce the redundancy in implementations by storing only the basis elements of semantic relations. The research presented in this paper is an example of an application of Relational Concept Analysis to lexical databases and knowledge representation systems (cf. Priss 1996) which is part of a larger framework of research on natural language analysis and formalization.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00083
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 32
    Electronic Resource
    Electronic Resource
    Expressing Time Intervals and Repetition Within a Formalization of Calendars (1998)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 14 (1998), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: We investigate a formal representation of time units, calendars, and time unit instances as restricted temporal entities for reasoning about repeated events. We generalize Allen's interval relations to a class level, and based on interval classes we define time units. We examine characteristics of time units, and provide a categorization of the hierarchical relations among them. Hence we define an abstract hierarchical unit structure (a calendar structure) that expresses specific relations and properties among the units that compose it. Specific objects in the time line are represented based on this formalism, including nonconvex intervals corresponding to repeated events. A goal of this research is to be able to represent and reason efficiently about repetition in time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00075
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 33
    Electronic Resource
    Electronic Resource
    Title Index, Volume 14, 1998 (1998)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 14 (1998), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/1467-8640.00077
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 34
    Electronic Resource
    Electronic Resource
    Multimodal Interaction for Information Access: Exploiting Cohesion (1997)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 13 (1997), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: Multimodality is a powerful concept for dealing with dialogue cohesion in a human–computer natural language (NL)-centered system. This work is a modest step toward more effective exploitation of the potentially large bandwidth of communication provided by this situation. The relations between exploration, navigation, and NL-based communication are discussed in general and with reference to two prototypes. Light cognitive load feedback and direct manipulation are proposed so that user and system can cooperate in mutually establishing the structure of the ongoing dialogue. The main points are: (i) use of an appropriate dialogue structure to constrain inference in the anaphora resolution process; (ii) use of a graphical representation of the structure, to limit the problem of opacity; (iii) allowance for the possibility of direct manipulation on this representation, to avoid the necessity of operating linguistically at the metalevel. The context of the work is within NL-centered multimodal information access systems, in which basic entities are pairs (most commonly question and answer). A dialogue model is provided by a modified version of the centering model; it is both sufficiently simple to be displayed in an intuitive fashion on the screen, and sufficiently powerful to give accurate results. An extension of the discourse model, oriented to the treatment of deixis, is also proposed. Finally, steps toward an overall approach to the integration of navigational and mediated aspects of interaction are discussed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00047
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 35
    Electronic Resource
    Electronic Resource
    Simulated Annealing and the Generation of the Objective Function: A Model of Learning During Problem Solving (1997)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 13 (1997), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: A computational model of problem solving based on significant aspects of human problem solving is introduced. It is observed that during problem solving humans often start searching more or less randomly, becoming more deterministic over time as they learn more about the problem. This two-phase aspect of problem-solving behavior and its relation to learning is one of the important features this model accounts for. The model uses an accelerated simulated annealing technique as a search mechanism within a real-time dynamic programming-like framework upon a connected graph of neighboring problem states. The objective value of each node is adjusted as the model moves between nodes, learning more accurate values for the nodes and also compensating for misleading heuristic information as it does so. In this manner the model is shown to learn to more effectively solve isomorphs of the Balls and Boxes and Tower of Hanoi problems. The major issues investigated with the model are (a) whether such a simulated annealing-based model exhibits the kind of random-to-directed transition in behavior exhibited by people, and (b) whether the progressive discovery of the objective function, even when given very little or poor initial information, is a plausible method for representing the learning that occurs during problem solving and the knowledge that results from that learning.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00051
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 36
    Electronic Resource
    Electronic Resource
    Interpreting Presuppositions Using Active Logic: From Contexts to Utterances (1997)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 13 (1997), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: Presuppositionis a pervasive feature of human language. It involves many interesting interactions between the utterances of a discourse and the contextof the discourse. In this paper we focus on issues of logical form connected with the interaction of presupposition and discourse context, and illustrate our theory with some implementational work using the active logicframework. After reviewing some of the major issues in presupposition theory we turn to a largely successful unified approach of Heim. We show how the main principles of this theory can be implemented in active logic. But we also find two serious difficulties. These consist in (a) a straightforward counterexample and (b) a type of discourse that we call a garden-path discourse. We maintain that both the counterexample and the garden-path type of discourse can be handled by our active-logic version of Heim's theory. This requires us to reformulate and extend Heim's theorey. Although this work is largely theoretical, both Heim's theory and ours have important things to say about the incremental processing of the utterances that make up discourse. And we present our theory as a specification of a processing device that takes logical form of a sentence along with current discourse context as input and delivers an updated discourse context as output. As an experiment, we have implemented portions of this device.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00044
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 37
    Electronic Resource
    Electronic Resource
    Introduction to the Special Issue on Context in Natural Language Processing (1997)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 13 (1997), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00041
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 38
    Electronic Resource
    Electronic Resource
    Reasoning with Intensional Negative Adjectivals: Semantics, Pragmatics, and Context (1997)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 13 (1997), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: Intensional negative adjectives alleged, artificial, fake, false, former, and toyare unusual adjectives that depending on context may or may not be restricting functions. A formal theory of their semantics, pragmatics, and context that uniformly accounts for their complex mathematical and computational characteristics and captures some peculiarities of individual adjectives is presented.Such adjectives are formalized as new concept builders, negation-like functions that operate on the values of intensional properties of the concepts denoted by their arguments and yield new concepts whose intensional properties have values consistent with the negation of the old values. Understanding these new concepts involves semantics, pragmatics and context-dependency of natural language. It is argued that intensional negative adjectives can be viewed as a special-purpose, weaker, conntext-dependent negationin natural language. The theory explains and predicts many inferences licensed by expressions involving such adjectives. Implementation of sample examples demonstrates its computational feasibility. Computation of context-dependent interpretation is discussed.The theory allows one to enhance a knowledge representation system with similar concept building, negation-like, context-dependent functions, the availability of which appears to be a distinct characteristic of natural languages.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00043
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 39
    Electronic Resource
    Electronic Resource
    An Algorithm for Minimal Insertion in a Type Lattice (1999)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: The problem of inserting a new element x into a lattice of types L is addressed in the paper. As the poset L+x obtained by the direct insertion of x in L is not necessarily a lattice, some set of auxiliary elements should be added to restore the lattice properties. An approach toward the lattice insertion is presented which allows the set of auxiliary elements to be kept minimal. The key idea is to build the final lattice L+ as isomorphic to the Dedekind–McNeille completion of the order L+x. Our strategy is based on a global definition of the set of auxiliary elements and their locations in L+. Each auxiliary is related to a specific element of L, an odd, which represents GLB (LUB) of some elements in L superior (inferior) to x. An appropriate computation scheme for the auxiliary types is given preserving the subtyping in the lattice L+. The insertion strategy presented is more general than the existing ones, since it deals with general kinds of lattices and makes no hypothesis on the location of x in L. An algorithm computing L+ from L and x of time complexity O(|L||J(L)|ω^3(L)) is provided.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00082
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 40
    Electronic Resource
    Electronic Resource
    Encoding of Multiple Inheritance Hierarchies and Partial Orders (1999)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: Efficient implementation of type inclusion is an important feature of object oriented programming languages with multiple inheritance. The idea is to associate to each type a subset of a set S={1,...,k} such that type inclusion coincides with subset inclusion. Such an embedding of types into 2S (the lattice of all subsets of S) is called a bit-vector encoding of the type hierarchy. In this paper, we show that most known bit-vector encoding methods can be inserted on a general theoretical framework using graph coloration, namely the notion of a simple encoding. We use the word simple because all these methods are heuristics for the general bit-vector encoding problem, known as the 2-dimension problem. First we provide a correct algorithm for partial orders based on simple encoding, improving the algorithm of Krall, Vitek, and Horspool (1997). Second we show that finding an optimal simple encoding is an NP-hard problem. We end with a discussion on some practical issues.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00081
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 41
    Electronic Resource
    Electronic Resource
    Perceiving and Reasoning about a Changing World (1998)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 14 (1998), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: A rational agent (artificial or otherwise) residing in a complex changing environment must gather information perceptually, update that information as the world changes, and combine that information with causal information to reason about the changing world. Using the system of defeasible reasoning that is incorporated into the OSCAR architecture for rational agents, a set of reason-schemas is proposed for enabling an agent to perform some of the requisite reasoning. Along the way, solutions are proposed for the Frame Problem, the Qualification Problem, and the Ramification Problem. The principles and reasoning described have all been implemented in OSCAR.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00074
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 42
    Electronic Resource
    Electronic Resource
    The Foundations of Taxonomic Encoding (1998)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 14 (1998), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: Taxonomies (partially ordered sets and lattices) are important in many areas of computing science, particularly object-oriented languages, machine learning, and knowledge representation. Taxonomic encoding strives to enhance the efficiency of taxonomic representation and use, which becomes increasingly important as the size of taxonomies grows. In this paper, we describe a formal structure, called a spanning set, in which taxonomic encoding techniques can be characterized. Any taxonomic encoding scheme implements a mapping from the original ordered set into a structure, such as the lattice of bit-vectors or logical terms, in which operations can be performed efficiently. We analyze the fundamental properties any such mapping must satisfy in order to preserve subsumption, joins, or meets. Spanning sets are an abstract framework within which we portray and compare existing encoding techniques, and provide a context in which new encoding problems can be analyzed, leading to existing, related algorithms or, using other results we develop in this paper, guiding the development of new algorithms. We also explore the limits of minimal-sized encodings, proving a lower bound for simple forms of encoding and showing that, in general, finding minimal-sized encodings is NP-hard. This paper can thus be viewed as both a synthesis of current research in taxonomic encoding and a repository of new results and directions for encoding as viewed from the perspective of spanning sets.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00076
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 43
    Electronic Resource
    Electronic Resource
    Logic for Nested Graphs (1998)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 14 (1998), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: We study the expressiveness of Nested Graphs, an extension of conceptual graphs. Nesting is introduced as a formal version of the intuitive “zooming in” on descriptions of individuals. Projections are defined inductively as the formal tool for “reasoning with nested graphs.” Nested graphs are translated to “colored” formulas. Coloring represents anaphoras in a way similar to conceptual graphs. A system of Gentzen sequents is shown to be adequate and complete with respect to projections of nested graphs.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00066
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 44
    Electronic Resource
    Electronic Resource
    On the Correctness and Reasonableness of Cox's Theorem for Finite Domains (1998)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 14 (1998), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: Halpern has recently claimed a counterexample to Cox's Theorem, a well-known existence result for subjective probability distributions, but stated that the counterexample can be defeated by a specific assumption. Cox made this assumption, and so escapes the counterexample. Although Halpern questioned whether the assumption is reasonable for finite sets of sentences, it supports features that distinguish Cox's work from other, more restrictive motivations of probabilism. Paris has recently offered a new proof of Cox's Theorem whose correctness is satisfactory to Halpern, one that depends on a premise consistent with Cox's later work. As with any deductive argument, denial of a premise licenses denial of the conclusion, but Cox's conclusion does follow from premises plainly acceptable to him.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00070
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 45
    Electronic Resource
    Electronic Resource
    On Social Constraints for Rational Agents (1999)
    Oxford, UK and Boston, USA : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: We define and study social constraints for rational agents. Our work is complementary to work on mechanism design in economics and Distributed Artificial Intelligence, as well as to work on artificial social systems. In our setting agents are rational but obey social laws that are imposed by the system's designer. Agents can be obliged to obey some social constraints, but not any constraint can serve as part of the social law. The main theme of our work is the study of settings where there are restrictions on the constraints that can serve as social laws. In such settings the designer should find social laws that can be imposed on the agents, and that will lead rational agents to satisfactory behavior. Our study is carried out in the context of zero-sum and general-sum games (with complete and with incomplete information) in extensive form.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00098
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 46
    Electronic Resource
    Electronic Resource
    Note of Appreciation from the Editors (1999)
    Oxford, UK and Boston, USA : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/1467-8640.00096
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 47
    Electronic Resource
    Electronic Resource
    Time Series Prediction With Genetic-Algorithm Designed Neural Networks: An Empirical Comparison With Modern Statistical Models (1999)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: Neural networks whose architecture is determined by genetic algorithms outperform autoregressive integrated moving average forecasting models in six different time series examples. Refinements to the autoregressive integrated moving average model improve forecasting performance over standard ordinary least squares estimation by 8% to 13%. In contrast, neural networks achieve dramatic improvements of 10% to 40%. Additionally, neural networks give evidence of detecting patterns in data which remain hidden to the autoregression and moving average models. The consequent forecasting potential of neural networks makes them a very promising addition to the variety of techniques and methodologies used to anticipate future movements in time series.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00090
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 48
    Electronic Resource
    Electronic Resource
    Experimentation-Driven Knowledge Acquisition for Planning (1999)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 15 (1999), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: Knowledge engineering for planning is expensive and the resulting knowledge can be imperfect. To autonomously learn a plan operator definition from environmental feedback, our learning system WISER explores an instantiated literal space using a breadth-first search technique. Each node of the search tree represents a state, a unique subset of the instantiated literal space. A state at the root node is called a seed state. WISER can generate seed states with or without utilizing imperfect expert knowledge. WISER experiments with an operator at each node. The positive state, in which an operator can be successfully executed, constitutes initial preconditions of an operator. We analyze the number of required experiments as a function of the number of missing preconditions in a seed state. We introduce a naive domain assumption to test only a subset of the exponential state space. Since breadth-first search is expensive, WISER introduces two search techniques to reorder literals at each level of the search tree. We demonstrate performance improvement using the naive domain assumption and literal-ordering heuristics. To learn the effects of an operator, WISER computes the delta state, composed of the add list and the delete list, and parameterizes it. Unlike previous systems, WISER can handle unbound objects in the delta state. We show that machine-generated effects definitions are often simpler in representation than expert-provided definitions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00093
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 49
    Electronic Resource
    Electronic Resource
    An Approach for Merging Plans Hierarchically in Decomposable Domains (1998)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 14 (1998), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: Recent works in domain-independent plan merging have shown that the optimal plan-merging problem is NP-hard, and heuristic algorithms have been proposed to generate near-optimal solutions. These works have shown heuristic algorithms which assume that the mergeability of two actions can be determined by considering only the actions themselves. In this paper, we show that it is often that case that the surrounding actions in the plan must also be considered when determining the mergeability of two or more actions; therefore, the context in which the actions are used affects their mergeability. To address this problem, we have developed a plan-merging methodology that merges partial-order plans based on the the notion of plan fragments, which encapsulate actions with the context in which they are being utilized. This methodology applies to a class of planning domains, called decomposable domains, which consist of actions that follow all or some portion of a type sequence. Merging is performed hierarchically by action type. We also investigate the previously unexplored notion of alternative actions in domain-independent plan merging, which can improve the quality of the resulting merged plan. A novel approach is presented for removing cyclic dependencies that may occur during the plan-merging process.A key part of the methodology is the computation of a minimum cost cover of plan fragments. We provide theoretical analyses of two optimal algorithms and a greedy-based algorithm for computing the minimum cost cover. We support the theoretical analysis of these algorithms with experimental data to show that the greedy approach is near-optimal and efficient.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00067
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 50
    Electronic Resource
    Electronic Resource
    Analysis of Heuristics for Number Partitioning (1998)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 14 (1998), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: We illustrate the use of phase transition behavior in the study of heuristics. Using an “annealed” theory, we define a parameter that measures the “constrainedness” of an ensemble of number partitioning problems. We identify a phase transition at a critical value of constrainedness. We then show that constrainedness can be used to analyze and compare algorithms and heuristics for number partitioning in a precise and quantitative manner. For example, we demonstrate that on uniform random problems both the Karmarkar–Karp and greedy heuristics minimize the constrainedness, but that the decisions made by the Karmarkar–Karp heuristic are superior at reducing constrainedness. This supports the better performance observed experimentally for the Karmarkar–Karp heuristic. Our results refute a conjecture of Fu that phase transition behavior does not occur in number partitioning. Additionally, they demonstrate that phase transition behavior is useful for more than just simple benchmarking. It can, for instance, be used to analyze heuristics, and to compare the quality of heuristic solutions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00069
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 51
    Electronic Resource
    Electronic Resource
    Utility Models for Goal-Directed, Decision-Theoretic Planners (1998)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 14 (1998), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: AI planning agents are goal-directed: success is measured in terms of whether an input goal is satisfied. The goal gives structure to the planning problem, and planning representations and algorithms have been designed to exploit that structure. Strict goal satisfaction may be an unacceptably restrictive measure of good behavior, however.A general decision-theoretic agent, on the other hand, has no explicit goals: success is measured in terms of an arbitrary preference model or utility function defined over plan outcomes. Although it is a very general and powerful model of problem solving, decision-theoretic choice lacks structure, which can make it difficult to develop effective plan-generation algorithms.This paper establishes a middle ground between the two models. We extend the traditional AI goal model in several directions: allowing goals with temporal extent, expressing preferences over partial satisfaction of goals, and balancing goal satisfaction against the cost of the resources consumed in service of the goals. In doing so we provide a utility model for a goal-directed agent.An important quality of the proposed model is its tractability. We claim that our model, like classical goal models, makes problem structure explicit. This structure can then be exploited by a problem-solving algorithm. We support this claim by reporting on two implemented planning systems that adopt and exploit our model.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00068
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 52
    Electronic Resource
    Electronic Resource
    The Use of Situation Theory in Context Modeling (1997)
    Boston, USA and Oxford, UK : Blackwell Publishers Inc
    Computational intelligence 13 (1997), S. 0 
    Details
    ISSN: 1467-8640
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Computer Science
    Notes: At the heart of natural language processing is the understanding of context dependent meanings. This paper presents a preliminary model of formal contexts based on situation theory. It also gives a worked-out example to show the use of contexts in lifting, i.e., how propositions holding in a particular context transform when they are moved to another context. This is useful in NLP applications where preserving meaning is a desideratum.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/0824-7935.00046
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 53
    Electronic Resource
    Electronic Resource
    A numerical approach to optimization problems with variational inequality constraints (1995)
    Springer
    Mathematical programming 68 (1995), S. 105-130 
    Details
    ISSN: 1436-4646
    Keywords: primary 49B34 ; secondary 90C31 ; 93C30 ; Variational inequalities ; Sensitivity analysis ; Generalized Jacobian
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Optimization problems with variational inequality constraints are converted to constrained minimization of a local Lipschitz function. To this minimization a non-differentiable optimization method is used; the required subgradients of the objective are computed by means of a special adjoint equation. Besides tests with some academic examples, the approach is applied to the computation of the Stackelberg—Cournot—Nash equilibria and to the numerical solution of a class of quasi-variational inequalities.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585759
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 54
    Electronic Resource
    Electronic Resource
    A cutting plane algorithm for convex programming that uses analytic centers (1995)
    Springer
    Mathematical programming 69 (1995), S. 1-43 
    Details
    ISSN: 1436-4646
    Keywords: Mathematical programming ; Cutting planes ; Analytic center
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Anoracle for a convex setS ⊂ ℝ n accepts as input any pointz in ℝ n , and ifz ∈S, then it returns ‘yes’, while ifz ∉S, then it returns ‘no’ along with a separating hyperplane. We give a new algorithm that finds a feasible point inS in cases where an oracle is available. Our algorithm uses the analytic center of a polytope as test point, and successively modifies the polytope with the separating hyperplanes returned by the oracle. The key to establishing convergence is that hyperplanes judged to be ‘unimportant’ are pruned from the polytope. If a ball of radius 2−L is contained inS, andS is contained in a cube of side 2 L+1, then we can show our algorithm converges after O(nL 2) iterations and performs a total of O(n 4 L 3+TnL 2) arithmetic operations, whereT is the number of arithmetic operations required for a call to the oracle. The bound is independent of the number of hyperplanes generated in the algorithm. An important application in which an oracle is available is minimizing a convex function overS.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585551
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 55
    Electronic Resource
    Electronic Resource
    A cutting plane method from analytic centers for stochastic programming (1995)
    Springer
    Mathematical programming 69 (1995), S. 45-73 
    Details
    ISSN: 1436-4646
    Keywords: Cutting plane ; Stochastic programming ; Analytic center ; Interior-point method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The stochastic linear programming problem with recourse has a dual block-angular structure. It can thus be handled by Benders' decomposition or by Kelley's method of cutting planes; equivalently the dual problem has a primal block-angular structure and can be handled by Dantzig-Wolfe decomposition—the two approaches are in fact identical by duality. Here we shall investigate the use of the method of cutting planes from analytic centers applied to similar formulations. The only significant difference form the aforementioned methods is that new cutting planes (or columns, by duality) will be generated not from the optimum of the linear programming relaxation, but from the analytic center of the set of localization.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585552
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 56
    Electronic Resource
    Electronic Resource
    A continuation method for monotone variational inequalities (1995)
    Springer
    Mathematical programming 69 (1995), S. 237-253 
    Details
    ISSN: 1436-4646
    Keywords: Variational inequality ; Nonlinear complementarity ; Nonlinear programming ; Continuation method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents a continuation method for monotone variational inequality problems based on a new smooth equation formulation. The existence, uniqueness and limiting behavior of the path generated by the method are analyzed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585559
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 57
    Electronic Resource
    Electronic Resource
    About strongly polynomial time algorithms for quadratic optimization over submodular constraints (1995)
    Springer
    Mathematical programming 69 (1995), S. 269-309 
    Details
    ISSN: 1436-4646
    Keywords: Quadratic programming ; Submodular constraints ; Kuhn-Tucker conditions ; Lexicographically optimal flow ; Parametric maximum flow
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present new strongly polynomial algorithms for special cases of convex separable quadratic minimization over submodular constraints. The main results are: an O(NM log(N 2/M)) algorithm for the problemNetwork defined on a network onM arcs andN nodes; an O(n logn) algorithm for thetree problem onn variables; an O(n logn) algorithm for theNested problem, and a linear time algorithm for theGeneralized Upper Bound problem. These algorithms are the best known so far for these problems. The status of the general problem and open questions are presented as well.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585561
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 58
    Electronic Resource
    Electronic Resource
    Worst-case comparison of valid inequalities for the TSP (1995)
    Springer
    Mathematical programming 69 (1995), S. 335-349 
    Details
    ISSN: 1436-4646
    Keywords: Polyhedral combinatorics ; Valid inequalities ; Travelling salesman ; Worst-case analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider most of the known classes of valid inequalities for the graphical travelling salesman polyhedron and compute the worst-case improvement resulting from their addition to the subtour polyhedron. For example, we show that the comb inequalities cannot improve the subtour bound by a factor greater than 10/9. The corresponding factor for the class of clique tree inequalities is 8/7, while it is 4/3 for the path configuration inequalities.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585563
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 59
    Electronic Resource
    Electronic Resource
    Solution of and bounding in a linearly constrained optimization problem with convex, polyhedral objective function (1995)
    Springer
    Mathematical programming 70 (1995), S. 1-16 
    Details
    ISSN: 1436-4646
    Keywords: Stochastic programming ; Polyhedral functions ; Simplicial functions
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A dual method is presented to solve a linearly constrained optimization problem with convex, polyhedral objective function, along with a fast bounding technique, for the optimum value. The method can be used to solve problems, obtained from LPs, where some of the constraints are not required to be exactly satisfied but are penalized by piecewise linear functions, which are added to the objective function of the original problem. The method generalizes an earlier solution technique developed by Prékopa (1990). Applications to stochastic programming are also presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585925
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 60
    Electronic Resource
    Electronic Resource
    The curvature integral and the complexity of linear complementarity problems (1995)
    Springer
    Mathematical programming 70 (1995), S. 107-122 
    Details
    ISSN: 1436-4646
    Keywords: Linear complementarity problem ; Predictor—corrector algorithm ; Complexity analysis ; Central trajectory ; Curvature integral ; Interior-point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper, we propose a predictor—corrector-type algorithm for solving the linear complementarity problem (LCP), and prove that the actual number of iterations needed by the algorithm is bounded from above and from below by a curvature integral along the central trajectory of the problem. This curvature integral is not greater than, and possibly smaller than, the best upper bound obtained in the literature to date.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585931
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 61
    Electronic Resource
    Electronic Resource
    Directional derivatives of the solution of a parametric nonlinear program (1995)
    Springer
    Mathematical programming 70 (1995), S. 159-172 
    Details
    ISSN: 1436-4646
    Keywords: Parametric nonlinear programming ; Directional differentiability ; B-derivative ; Piecewise smooth function ; Nonunique multipliers ; Degeneracy
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Consider a parametric nonlinear optimization problem subject to equality and inequality constraints. Conditions under which a locally optimal solution exists and depends in a continuous way on the parameter are well known. We show, under the additional assumption of constant rank of the active constraint gradients, that the optimal solution is actually piecewise smooth, hence B-differentiable. We show, for the first time to our knowledge, a practical application of quadratic programming to calculate the directional derivative in the case when the optimal multipliers are not unique.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585934
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 62
    Electronic Resource
    Electronic Resource
    On the equivalence of nonlinear complementarity problems and least-element problems (1995)
    Springer
    Mathematical programming 70 (1995), S. 191-200 
    Details
    ISSN: 1436-4646
    Keywords: Strictly pseudomonotone map ; Z-map ; Complementarity problem ; Least element problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Strictly pseudomonotoneZ-maps operating on Banach lattices are considered. Equivalence of complementarity problems and least-element problems is established under certain regularity and growth conditions. This extends a recent result by Riddell (1981) for strictly monotoneZ-maps to the pseudomonotone case. Some other problems equivalent to the above are discussed as well.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585936
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 63
    Electronic Resource
    Electronic Resource
    Primal—dual methods for linear programming (1995)
    Springer
    Mathematical programming 70 (1995), S. 251-277 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Barrier methods ; Interior-point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Many interior-point methods for linear programming are based on the properties of the logarithmic barrier function. After a preliminary discussion of the convergence of the (primal) projected Newton barrier method, three types of barrier method are analyzed. These methods may be categorized as primal, dual and primal—dual, and may be derived from the application of Newton's method to different variants of the same system of nonlinear equations. A fourth variant of the same equations leads to a new primal—dual method. In each of the methods discussed, convergence is demonstrated without the need for a nondegeneracy assumption or a transformation that makes the provision of a feasible point trivial. In particular, convergence is established for a primal—dual algorithm that allows a different step in the primal and dual variables and does not require primal and dual feasibility. Finally, a new method for treating free variables is proposed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585940
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 64
    Electronic Resource
    Electronic Resource
    The fleet assignment problem: Solving a large-scale integer program (1995)
    Springer
    Mathematical programming 70 (1995), S. 211-232 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Mixed-integer programming ; Large-scale optimization ; Airline fleet assignment
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a flight schedule and set of aircraft, the fleet assignment problem is to determine which type of aircraft should fly each flight segment. This paper describes a basic daily, domestic fleet assignment problem and then presents chronologically the steps taken to solve it efficiently. Our model of the fleet assignment problem is a large multi-commodity flow problem with side constraints defined on a time-expanded network. These problems are often severely degenerate, which leads to poor performance of standard linear programming techniques. Also, the large number of integer variables can make finding optimal integer solutions difficult and time-consuming. The methods used to attack this problem include an interior-point algorithm, dual steepest edge simplex, cost perturbation, model aggregation, branching on set-partitioning constraints and prioritizing the order of branching. The computational results show that the algorithm finds solutions with a maximum optimality gap of 0.02% and is more than two orders of magnitude faster than using default options of a standard LP-based branch-and-bound code.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585938
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 65
    Electronic Resource
    Electronic Resource
    An interior-proximal method for convex linearly constrained problems and its extension to variational inequalities (1995)
    Springer
    Mathematical programming 71 (1995), S. 77-100 
    Details
    ISSN: 1436-4646
    Keywords: Convex linearly constrained problems ; Variational inequalities ; Interior methods ; Entropy-like proximal method ; Maximal monotone operator
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper, an entropy-like proximal method for the minimization of a convex function subject to positivity constraints is extended to an interior algorithm in two directions. First, to general linearly constrained convex minimization problems and second, to variational inequalities on polyhedra. For linear programming, numerical results are presented and quadratic convergence is established.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01592246
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 66
    Electronic Resource
    Electronic Resource
    One-third-integrality in the max-cut problem (1995)
    Springer
    Mathematical programming 71 (1995), S. 29-50 
    Details
    ISSN: 1436-4646
    Keywords: Max-cut ; Cut polytope ; Metric polytope ; Linear relaxation ; One-third-integrality ; Box one-third-integrality ; Forbidden minor
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a graphG = (V, E), the metric polytopeS (G) is defined by the inequalitiesx(F) − x(C∖F) ⩽ |F| − 1 for $$F \subseteq C$$ , |F| odd,C cycle ofG, and 0 ⩽x e ⩽ 1 fore ∈ E. Optimization overS (G) provides an approximation for the max-cut problem. The graphG is called 1/d-integral if all the vertices ofS(G) have their coordinates in{i/d ∣ 0 ⩽ i ⩽ d}. We prove that the class of 1/d-integral graphs is closed under minors, and we present several minimal forbidden minors for 1/3-integrality. In particular, we characterize the 1/3-integral graphs on seven nodes. We study several operations preserving 1/d-integrality, in particular, thek-sum operation for 0 ⩽k ⩽ 3. We prove that series parallel graphs are characterized by the following stronger property. All vertices of the polytopeS (G) ∩ {x ∣ ℓ ⩽ x ⩽ u} are 1/3-integral for every choice of 1/3-integral boundsℓ, u on the edges ofG.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01592243
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 67
    Electronic Resource
    Electronic Resource
    On minquantile and maxcovering optimisation (1995)
    Springer
    Mathematical programming 71 (1995), S. 101-112 
    Details
    ISSN: 1436-4646
    Keywords: Minmax ; Maximal covering problems ; Multi criteria decision-making
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we introduce the parametric minquantile problem, a weighted generalisation ofkth maximum minimisation. It is shown that, under suitable quasiconvexity assumptions, its resolution can be reduced to solving a polynomial number of minmax problems. It is also shown how this simultaneously solves (parametric) maximal covering problems. It follows that bicriteria problems, where the aim is to both maximize the covering and minimize the cover-level, are reducible to a discrete problem, on which any multiple criteria method may be applied.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01592247
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 68
    Electronic Resource
    Electronic Resource
    The Fermat—Weber location problem revisited (1995)
    Springer
    Mathematical programming 71 (1995), S. 71-76 
    Details
    ISSN: 1436-4646
    Keywords: Location theory ; Fermat—Weber problem ; Weiszfeld's iterative algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The Fermat—Weber location problem requires finding a point in ℝ N that minimizes the sum of weighted Euclidean distances tom given points. A one-point iterative method was first introduced by Weiszfeld in 1937 to solve this problem. Since then several research articles have been published on the method and generalizations thereof. Global convergence of Weiszfeld's algorithm was proven in a seminal paper by Kuhn in 1973. However, since them given points are singular points of the iteration functions, convergence is conditional on none of the iterates coinciding with one of the given points. In addressing this problem, Kuhn concluded that whenever them given points are not collinear, Weiszfeld's algorithm will converge to the unique optimal solution except for a denumerable set of starting points. As late as 1989, Chandrasekaran and Tamir demonstrated with counter-examples that convergence may not occur for continuous sets of starting points when the given points are contained in an affine subspace of ℝ N . We resolve this open question by proving that Weiszfeld's algorithm converges to the unique optimal solution for all but a denumerable set of starting points if, and only if, the convex hull of the given points is of dimensionN.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01592245
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 69
    Electronic Resource
    Electronic Resource
    An efficient cost scaling algorithm for the assignment problem (1995)
    Springer
    Mathematical programming 71 (1995), S. 153-177 
    Details
    ISSN: 1436-4646
    Keywords: Network optimization ; Assignment problem ; Algorithms ; Experimental evaluation ; Cost scaling
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The cost scaling push-relabel method has been shown to be efficient for solving minimum-cost flow problems. In this paper we apply the method to the assignment problem and investigate implementations of the method that take advantage of assignment's special structure. The results show that the method is very promising for practical use.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585996
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 70
    Electronic Resource
    Electronic Resource
    Superfluous matrices in linear complementarity (1995)
    Springer
    Mathematical programming 71 (1995), S. 195-206 
    Details
    ISSN: 1436-4646
    Keywords: Superfluous matrix ; Linear complementarity problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Superfluous matrices were introduced by Howe (1983) in linear complementarity. In general, producing examples of this class is tedious (a few examples can be found in Chapter 6 of Cottle, Pang and Stone (1992)). To overcome this problem, we define a new class of matrices $$\bar Z$$ and establish that in $$\bar Z$$ superfluous matrices of any ordern ⩾ 4 can easily be constructed. For every integerk, an example of a superfluous matrix of degreek is exhibited in the end.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585998
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 71
    Electronic Resource
    Electronic Resource
    Balanced 0, ±1-matrices, bicoloring and total dual integrality (1995)
    Springer
    Mathematical programming 71 (1995), S. 249-258 
    Details
    ISSN: 1436-4646
    Keywords: Combinatorial optimization ; Integrality of polyhedra ; Generalized set packing ; Covering
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A 0, ±1-matrixA is balanced if, in every submatrix with two nonzero entries per row and column, the sum of the entries is a multiple of four. This definition was introduced by Truemper (1978) and generalizes the notion of a balanced 0, 1-matrix introduced by Berge (1970). In this paper, we extend a bicoloring theorem of Berge (1970) and total dual integrality results of Fulkerson, Hoffman and Oppenheim (1974) to balanced 0, ±1-matrices.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01590956
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 72
    Electronic Resource
    Electronic Resource
    A note on locally Lipschitzian functions (1995)
    Springer
    Mathematical programming 71 (1995), S. 369-370 
    Details
    ISSN: 1436-4646
    Keywords: Local Lipschitz property ; Infinite-dimensional Hilbert space
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An oversight in a paper of Correa and Lemaréchal (this journal, 1993) is noted; a counterexample is given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01590961
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 73
    Electronic Resource
    Electronic Resource
    Strongly polynomial dual simplex methods for the maximum flow problem (1998)
    Springer
    Mathematical programming 80 (1998), S. 17-33 
    Details
    ISSN: 1436-4646
    Keywords: Dual simplex method ; Maximum flow ; Strongly polynomial ; Preflow algorithm ; Valid distance labels
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents dual network simplex algorithms that require at most 2nm pivots and O(n 2 m) time for solving a maximum flow problem on a network ofn nodes andm arcs. Refined implementations of these algorithms and a related simplex variant that is not strictly speaking a dual simplex algorithm are shown to have a complexity of O(n 3). The algorithms are based on the concept of apreflow and depend upon the use of node labels that are underestimates of the distances from the nodes to the sink node in the extended residual graph associated with the current flow. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582129
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 74
    Electronic Resource
    Electronic Resource
    Partitioning mathematical programs for parallel solution (1998)
    Springer
    Mathematical programming 80 (1998), S. 35-61 
    Details
    ISSN: 1436-4646
    Keywords: Graph partitioning ; Linear programming ; Bundle method ; Parallel optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper describes heuristics for partitioning a generalM × N matrix into arrowhead form. Such heuristics are useful for decomposing large, constrained, optimization problems into forms that are amenable to parallel processing. The heuristics presented can be easily implemented using publicly available graph partitioning algorithms. The application of such techniques for solving large linear programs is described. Extensive computational results on the effectiveness of our partitioning procedures and their usefulness for parallel optimization are presented. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582130
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 75
    Electronic Resource
    Electronic Resource
    Local convergence of predictor—corrector infeasible-interior-point algorithms for SDPs and SDLCPs (1998)
    Springer
    Mathematical programming 80 (1998), S. 129-160 
    Details
    ISSN: 1436-4646
    Keywords: Semidefinite programming ; Infeasible-interior-point method ; Predictor—correctormethod ; Superlinear convergence ; Primal—dual nondegeneracy
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An example of an SDP (semidefinite program) exhibits a substantial difficulty in proving the superlinear convergence of a direct extension of the Mizuno—Todd—Ye type predictor—corrector primal-dual interior-point method for LPs (linear programs) to SDPs, and suggests that we need to force the generated sequence to converge to a solution tangentially to the central path (or trajectory). A Mizuno—Todd—Ye type predictor—corrector infeasible-interior-point algorithm incorporating this additional restriction for monotone SDLCPs (semidefinite linear complementarity problems) enjoys superlinear convergence under strict complementarity and nondegeneracy conditions. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581723
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 76
    Electronic Resource
    Electronic Resource
    A reduction method for variational inequalities (1998)
    Springer
    Mathematical programming 80 (1998), S. 161-169 
    Details
    ISSN: 1436-4646
    Keywords: Variational inequalities ; Complementarity problems ; Walrasian equilibrium ; Computational general equilibrium
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper explains a method by which the number of variables in a variational inequality having a certain form can be substantially reduced by changing the set over which the variational inequality is posed. The method applies in particular to certain economic equilibrium problems occurring in applications. We explain and justify the method, and give examples of its application, including a numerical example in which the solution time for the reduced problem was approximately 2% of that for the problem in its original form. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581724
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 77
    Electronic Resource
    Electronic Resource
    Cutting planes for integer programs with general integer variables (1998)
    Springer
    Mathematical programming 81 (1998), S. 201-214 
    Details
    ISSN: 1436-4646
    Keywords: Integer programming ; Cutting planes ; Cover inequalities ; Lifting ; Gomory mixed integer cuts ; Cut-and-branch
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We investigate the use of cutting planes for integer programs with general integer variables. We show how cutting planes arising from knapsack inequalities can be generated and lifted as in the case of 0–1 variables. We also explore the use of Gomory's mixed-integer cuts. We address both theoretical and computational issues and show how to embed these cutting planes in a branch-and-bound framework. We compare results obtained by using our cut generation routines in two existing systems with a commercially available branch-and-bound code on a range of test problems arising from practical applications. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581105
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 78
    Electronic Resource
    Electronic Resource
    The node capacitated graph partitioning problem: A computational study (1998)
    Springer
    Mathematical programming 81 (1998), S. 229-256 
    Details
    ISSN: 1436-4646
    Keywords: Branch-and-cut algorithm ; Clustering ; Compiler design ; Equipartitioning ; Finite element method ; Graph partitioning ; Layout of electronic circuits ; Separation heuristics
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we consider the problem ofk-partitioning the nodes of a graph with capacity restrictions on the sum of the node weights in each subset of the partition, and the objective of minimizing the sum of the costs of the edges between the subsets of the partition. Based on a study of valid inequalities, we present a variety of separation heuristics for cycle, cycle with ears, knapsack tree and path-block cycle inequalities among others. The separation heuristics, plus primal heuristics, have been implemented in a branch-and-cut routine using a formulation including variables for the edges with nonzero costs and node partition variables. Results are presented for three classes of problems: equipartitioning problems arising in finite element methods and partitioning problems associated with electronic circuit layout and compiler design. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581107
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 79
    Electronic Resource
    Electronic Resource
    Second-order global optimality conditions for convex composite optimization (1998)
    Springer
    Mathematical programming 81 (1998), S. 327-347 
    Details
    ISSN: 1436-4646
    Keywords: Convex composite function ; Second-order global optimality ; Second-order duality ; Variational inequality
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In recent years second-order sufficient conditions of an isolated local minimizer for convex composite optimization problems have been established. In this paper, second-order optimality conditions are obtained of aglobal minimizer for convex composite problems with a non-finite valued convex function and a twice strictly differentiable function by introducing a generalized representation condition. This result is applied to a minimization problem with a closed convex set constraint which is shown to satisfy the basic constraint qualification. In particular, second-order necessary and sufficient conditions of a solution for a variational inequality problem with convex composite inequality constraints are obtained. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580087
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 80
    Electronic Resource
    Electronic Resource
    Preface (1998)
    Springer
    Mathematical programming 82 (1998), S. 1-1 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585862
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 81
    Electronic Resource
    Electronic Resource
    Minimizing symmetric submodular functions (1998)
    Springer
    Mathematical programming 82 (1998), S. 3-12 
    Details
    ISSN: 1436-4646
    Keywords: Symmetric submodular function minimization ; Submodular function minimization ; Symmetric submodular functions ; Submodular functions ; Submodular systems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We describe a purely combinatorial algorithm which, given a submodular set functionf on a finite setV, finds a nontrivial subsetA ofV minimizingf[A] + f[V ∖ A]. This algorithm, an extension of the Nagamochi—Ibaraki minimum cut algorithm as simplified by Stoer and Wagner [M. Stoer, F. Wagner, A simple min cut algorithm, Proceedings of the European Symposium on Algorithms ESA '94, LNCS 855, Springer, Berlin, 1994, pp. 141–147] and by Frank [A. Frank, On the edge-connectivity algorithm of Nagamochi and Ibaraki, Laboratoire Artémis, IMAG, Université J. Fourier, Grenbole, 1994], minimizes any symmetric submodular function using O(|V|3) calls to a function value oracle. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585863
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 82
    Electronic Resource
    Electronic Resource
    Random sampling and greedy sparsification for matroid optimization problems (1998)
    Springer
    Mathematical programming 82 (1998), S. 41-81 
    Details
    ISSN: 1436-4646
    Keywords: Random sampling ; Greedy algorithm ; Matroid basis ; Matroid partitioning
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Random sampling is a powerful tool for gathering information about a group by considering only a small part of it. We discuss some broadly applicable paradigms for using random sampling in combinatorial optimization, and demonstrate the effectiveness of these paradigms for two optimization problems on matroids: finding an optimum matroid basis and packing disjoint matroid bases. Application of these ideas to the graphic matroid led to fast algorithms for minimum spanning trees and minimum cuts. An optimum matroid basis is typically found by agreedy algorithm that grows an independent set into an optimum basis one element at a time. This continuous change in the independent set can make it hard to perform the independence tests needed by the greedy algorithm. We simplify matters by using sampling to reduce the problem of finding an optimum matroid basis to the problem of verifying that a givenfixed basis is optimum, showing that the two problems can be solved in roughly the same time. Another application of sampling is to packing matroid bases, also known as matroid partitioning. Sampling reduces the number of bases that must be packed. We combine sampling with a greedy packing strategy that reduces the size of the matroid. Together, these techniques give accelerated packing algorithms. We give particular attention to the problem of packing spanning trees in graphs, which has applications in network reliability analysis. Our results can be seen as generalizing certain results from random graph theory. The techniques have also been effective for other packing problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585865
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 83
    Electronic Resource
    Electronic Resource
    The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases (1998)
    Springer
    Mathematical programming 82 (1998), S. 125-158 
    Details
    ISSN: 1436-4646
    Keywords: Quadratic assignment ; Special cases ; Polynomially solvable ; Anti-Monge matrices ; Toeplitz matrices
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper investigates a restricted version of the Quadratic Assignment Problem (QAP), where one of the coefficient matrices is an Anti-Monge matrix with non-decreasing rows and columns and the other coefficient matrix is a symmetric Toeplitz matrix. This restricted version is called the Anti-Monge—Toeplitz QAP. There are three well-known combinatorial problems that can be modeled via the Anti-Monge—Toeplitz QAP: (Pl) The “Turbine Problem”, i.e. the assignment of given masses to the vertices of a regular polygon such that the distance of the center of gravity of the resulting system to the center of the polygon is minimized. (P2) The Traveling Salesman Problem on symmetric Monge distance matrices. (P3) The arrangement of data records with given access probabilities in a linear storage medium in order to minimize the average access time. We identify conditions on the Toeplitz matrixB that lead to a simple solution for the Anti-Monge—Toeplitz QAP: The optimal permutation can be given in advance without regarding the numerical values of the data. The resulting theorems generalize and unify several known results on problems (P1), (P2), and (P3). We also show that the Turbine Problem is NP-hard and consequently, that the Anti-Monge—Toeplitz QAP is NP-hard in general. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585868
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 84
    Electronic Resource
    Electronic Resource
    Bound constrained quadratic programming via piecewise quadratic functions (1999)
    Springer
    Mathematical programming 85 (1999), S. 135-156 
    Details
    ISSN: 1436-4646
    Keywords: Key words: bound constrained quadratic programming – Huber’s M–estimator – condition estimation – Newton iteration – factorization update
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 1 , the smallest eigenvalue of a symmetric, positive definite matrix, and is solved by Newton iteration with line search. The paper describes the algorithm and its implementation including estimation of λ1, how to get a good starting point for the iteration, and up- and downdating of Cholesky factorization. Results of extensive testing and comparison with other methods for constrained QP are given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050049
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 85
    Electronic Resource
    Electronic Resource
    Bimatrix games have quasi-strict equilibria (1999)
    Springer
    Mathematical programming 85 (1999), S. 35-49 
    Details
    ISSN: 1436-4646
    Keywords: Key words: bimatrix game – quasi-strict equilibrium ; Mathematics Subject Classification (1991): 90D05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050045
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 86
    Electronic Resource
    Electronic Resource
    A smoothing method for mathematical programs with equilibrium constraints (1999)
    Springer
    Mathematical programming 85 (1999), S. 107-134 
    Details
    ISSN: 1436-4646
    Keywords: Key words: equilibrium constraints – variational inequality problems – strong monotonicity – optimality conditions – global convergence ; Mathematics Subject Classification (1991): 90C30, 90C33, 65K05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s10107990015a
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 87
    Electronic Resource
    Electronic Resource
    Tight representation of logical constraints as cardinality rules (1999)
    Springer
    Mathematical programming 85 (1999), S. 363-377 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 1 ,...,Am are true, then at least ℓ of the propositions B1,...,Bn are true. The main result of the paper is that the procedure in fact provides a convex hull description.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050061
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 88
    Electronic Resource
    Electronic Resource
    Using continuous nonlinear relaxations to solve. constrained maximum-entropy sampling problems (1999)
    Springer
    Mathematical programming 85 (1999), S. 221-240 
    Details
    ISSN: 1436-4646
    Keywords: Key words: maximum-entropy sampling – branch and bound – nonlinear programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050055
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 89
    Electronic Resource
    Electronic Resource
    Q-matrix recognition via secondary and universal polytopes (1999)
    Springer
    Mathematical programming 85 (1999), S. 259-276 
    Details
    ISSN: 1436-4646
    Keywords: Key words: linear complementary problems – Q-matrices – polyhedral combinatorics – triangulations of point configurations – 0-1 polytopes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: T (Mx+q)=0, Mx+q≥0, x≥0 has a solution. We explain how one can use the polyhedral structure of the set of all triangulations of a finite point set to determine if an n×n matrix M is a Q-matrix. Our implementation of the algorithm is practical for deciding the Q-nature for all M with n≤8.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050057
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 90
    Electronic Resource
    Electronic Resource
    Finiteness of conical algorithms with ω-subdivisions (1999)
    Springer
    Mathematical programming 85 (1999), S. 593-616 
    Details
    ISSN: 1436-4646
    Keywords: Key words: concave optimization – conical algorithms –ω-subdivisions Mathematics Subject Classification (1991): 90C26, 65K05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. In this paper the problem of finding the global optimum of a concave function over a polytope is considered. A well-known class of algorithms for this problem is the class of conical algorithms. In particular, the conical algorithm based on the so called ω-subdivision strategy is considered. It is proved that, for any given accuracy ε〉0, this algorithm stops in a finite time by returning an ε-optimal solution for the problem, while it is convergent for ε=0.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050073
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 91
    Electronic Resource
    Electronic Resource
    Lifted flow cover inequalities for mixed 0-1 integer programs (1999)
    Springer
    Mathematical programming 85 (1999), S. 439-467 
    Details
    ISSN: 1436-4646
    Keywords: Mathematics Subject Classification (1991): 90C11
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We investigate strong inequalities for mixed 0-1 integer programs derived from flow cover inequalities. Flow cover inequalities are usually not facet defining and need to be lifted to obtain stronger inequalities. However, because of the sequential nature of the standard lifting techniques and the complexity of the optimization problems that have to be solved to obtain lifting coefficients, lifting of flow cover inequalities is computationally very demanding. We present a computationally efficient way to lift flow cover inequalities based on sequence independent lifting techniques and give computational results that show the effectiveness of our lifting procedures.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050067
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 92
    Electronic Resource
    Electronic Resource
    Conditioning of semidefinite programs (1999)
    Springer
    Mathematical programming 85 (1999), S. 525-540 
    Details
    ISSN: 1436-4646
    Keywords: Key words: semidefinite programming – perturbation theory – Kantorovi theory – condition number Mathematics Subject Classification (1991): 90C31, 90C25, 90C05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: theory. This approach also quantifies the size of permissible perturbations. We include a discussion of these results for block diagonal semidefinite programs, of which linear programming is a special case.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050070
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 93
    Electronic Resource
    Electronic Resource
    Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard (1999)
    Springer
    Mathematical programming 86 (1999), S. 219-223 
    Details
    ISSN: 1436-4646
    Keywords: Key words: linear programming – computational complexity – complexity measure Mathematics Subject Classification (1991): 90C05, 90C60, 68Q25
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Given an m×n integer matrix A of full row rank, we consider the problem of computing the maximum of ∥B -1 A∥2 where B varies over all bases of A. This quantity appears in various places in the mathematical programming literature. More recently, logarithm of this number was the determining factor in the complexity bound of Vavasis and Ye’s primal-dual interior-point algorithm. We prove that the problem of approximating this maximum norm, even within an exponential (in the dimension of A) factor, is NP-hard. Our proof is based on a closely related result of L. Khachiyan [1].
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050087
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 94
    Electronic Resource
    Electronic Resource
    Global convergence of a class of non-interior point algorithms using Chen-Harker-Kanzow-Smale functions for nonlinear complementarity problems (1999)
    Springer
    Mathematical programming 86 (1999), S. 105-133 
    Details
    ISSN: 1436-4646
    Keywords: Key words: non-interior point method – complementarity problem – smoothing function – homotopy method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We propose a class of non-interior point algorithms for solving the complementarity problems(CP): Find a nonnegative pair (x,y)∈ℝ 2n satisfying y=f(x) and x i y i =0 for every i∈{1,2,...,n}, where f is a continuous mapping from ℝ n to ℝ n . The algorithms are based on the Chen-Harker-Kanzow-Smale smoothing functions for the CP, and have the following features; (a) it traces a trajectory in ℝ 3n which consists of solutions of a family of systems of equations with a parameter, (b) it can be started from an arbitrary (not necessarily positive) point in ℝ 2n in contrast to most of interior-point methods, and (c) its global convergence is ensured for a class of problems including (not strongly) monotone complementarity problems having a feasible interior point. To construct the algorithms, we give a homotopy and show the existence of a trajectory leading to a solution under a relatively mild condition, and propose a class of algorithms involving suitable neighborhoods of the trajectory. We also give a sufficient condition on the neighborhoods for global convergence and two examples satisfying it.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050082
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 95
    Electronic Resource
    Electronic Resource
    Linear convergence of epsilon-subgradient descent methods for a class of convex functions (1999)
    Springer
    Mathematical programming 86 (1999), S. 41-50 
    Details
    ISSN: 1436-4646
    Keywords: Key words: resolvent method – proximal point method – bundle method – bundle-trust region method – subgradient Mathematics Subject Classification (1991): 90C25, 49M45
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. This paper establishes a linear convergence rate for a class of epsilon-subgradient descent methods for minimizing certain convex functions on ℝ n . Currently prominent methods belonging to this class include the resolvent (proximal point) method and the bundle method in proximal form (considered as a sequence of serious steps). Other methods, such as a variant of the proximal point method given by Correa and Lemaréchal, can also fit within this framework, depending on how they are implemented. The convex functions covered by the analysis are those whose conjugates have subdifferentials that are locally upper Lipschitzian at the origin, a property generalizing classical regularity conditions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050078
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 96
    Electronic Resource
    Electronic Resource
    On existence and uniqueness of stationary points in semi-infinite optimization (1999)
    Springer
    Mathematical programming 86 (1999), S. 387-415 
    Details
    ISSN: 1436-4646
    Keywords: Key words: semi-infinite optimization – reduction approach – stationary point – strong stability – extended Mangasarian-Fromovitz constraint qualification Mathematics Subject Classification (1991): 90C30, 90C31, 90C34, 49M39
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. The paper deals with semi-infinite optimization problems which are defined by finitely many equality constraints and infinitely many inequality constraints. We generalize the concept of strongly stable stationary points which was introduced by Kojima for finite problems; it refers to the local existence and uniqueness of a stationary point for each sufficiently small perturbed problem, where perturbations up to second order are allowed. Under the extended Mangasarian-Fromovitz constraint qualification we present equivalent conditions for the strong stability of a considered stationary point in terms of first and second derivatives of the involved functions. In particular, we discuss the case where the reduction approach is not satisfied.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050095
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 97
    Electronic Resource
    Electronic Resource
    An infeasible-interior-point potential-reduction algorithm for linear programming (1999)
    Springer
    Mathematical programming 86 (1999), S. 313-334 
    Details
    ISSN: 1436-4646
    Keywords: Key words: linear programming – potential functions – infeasible-interior-point methods – homogeneity – self-dual
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050091
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 98
    Electronic Resource
    Electronic Resource
    Basis- and partition identification for quadratic programming and linear complementarity problems (1999)
    Springer
    Mathematical programming 86 (1999), S. 261-282 
    Details
    ISSN: 1436-4646
    Keywords: Key words: basis recovery – partition – principal pivot transforms – Balinski-Tucker tableaus – quadratic programming – linear complementarity problems – interior point methods – sufficient matrices – crossover – Criss-Cross method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Optimal solutions of interior point algorithms for linear and quadratic programming and linear complementarity problems provide maximally complementary solutions. Maximally complementary solutions can be characterized by optimal partitions. On the other hand, the solutions provided by simplex–based pivot algorithms are given in terms of complementary bases. A basis identification algorithm is an algorithm which generates a complementary basis, starting from any complementary solution. A partition identification algorithm is an algorithm which generates a maximally complementary solution (and its corresponding partition), starting from any complementary solution. In linear programming such algorithms were respectively proposed by Megiddo in 1991 and Balinski and Tucker in 1969. In this paper we will present identification algorithms for quadratic programming and linear complementarity problems with sufficient matrices. The presented algorithms are based on the principal pivot transform and the orthogonality property of basis tableaus.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050089
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 99
    Electronic Resource
    Electronic Resource
    Decision-making by hierarchies of discordant agents (1999)
    Springer
    Mathematical programming 86 (1999), S. 417-431 
    Details
    ISSN: 1436-4646
    Keywords: Mathematics Subject Classification (1991): 90A11, 90B50, 90C90, 90D65
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We study the following decision-making scenario: A linear program is solved by a set of agents arranged hierarchically in a tree, where each agent decides the level of certain variables, and has a distinct objective function, known to all agents. Authority is reflected in two ways: Agents higher in the tree set their variables first; and agents that are siblings in the tree resolve their game by focusing on the Nash equilibrium that is optimum for the agent above them. We give a necessary and sufficient condition for such a hierarchy to be efficient (i.e., to have perfect coordination, to ultimately optimize the objective of the firm). We study problems related to designing a hierarchy (assigning decision makers to positions in the tree) in order to achieve efficiency or otherwise optimize coordination.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050096
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 100
    Electronic Resource
    Electronic Resource
    A non-interior continuation method for generalized linear complementarity problems (1999)
    Springer
    Mathematical programming 86 (1999), S. 533-563 
    Details
    ISSN: 1436-4646
    Keywords: Key words: generalized linear complementarity problem – non-interior continuation method – Newton method – Q-quadratical convergence Mathematics Subject Classification (1991): 90C33
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. In this paper, we propose a non-interior continuation method for solving generalized linear complementarity problems (GLCP) introduced by Cottle and Dantzig. The method is based on a smoothing function derived from the exponential penalty function first introduced by Kort and Bertsekas for constrained minimization. This smoothing function can also be viewed as a natural extension of Chen-Mangasarian’s neural network smooth function. By using the smoothing function, we approximate GLCP as a family of parameterized smooth equations. An algorithm is presented to follow the smoothing path. Under suitable assumptions, it is shown that the algorithm is globally convergent and local Q-quadratically convergent. Few preliminary numerical results are also reported.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050104
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...