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
  • computational learning theory  (2)
  • Mathematics Subject Classification (1991): 90C27, 90C35, 68Q25  (1)
  • Springer  (3)
  • 1
    Electronic Resource
    Electronic Resource
    A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem (2000)
    Springer
    Mathematical programming 87 (2000), S. 519-542 
    Details
    ISSN: 1436-4646
    Keywords: Key words: neighborhood – local search – search problem – Travelling Salesman Problem – Quadratic Assignment Problem – polynomial time algorithm – NP-completeness – combinatorial optimization ; Mathematics Subject Classification (1991): 90C27, 90C35, 68Q25
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. This paper deals with exponential neighborhoods for combinatorial optimization problems. Exponential neighborhoods are large sets of feasible solutions whose size grows exponentially with the input length. We are especially interested in exponential neighborhoods over which the TSP (respectively, the QAP) can be solved in polynomial time, and we investigate combinatorial and algorithmical questions related to such neighborhoods.¶First, we perform a careful study of exponential neighborhoods for the TSP. We investigate neighborhoods that can be defined in a simple way via assignments, matchings in bipartite graphs, partial orders, trees and other combinatorial structures. We identify several properties of these combinatorial structures that lead to polynomial time optimization algorithms, and we also provide variants that slightly violate these properties and lead to NP-complete optimization problems. Whereas it is relatively easy to find exponential neighborhoods over which the TSP can be solved in polynomial time, the corresponding situation for the QAP looks pretty hopeless: Every exponential neighborhood that is considered in this paper provably leads to an NP-complete optimization problem for the QAP.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050010
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    On the complexity of function learning (1995)
    Springer
    Machine learning 18 (1995), S. 187-230 
    Details
    ISSN: 0885-6125
    Keywords: computational learning theory ; on-line learning ; mistake-bounded learning ; function learning
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract The majority of results in computational learning theory are concerned with concept learning, i.e. with the special case of function learning for classes of functions with range {0, 1}. Much less is known about the theory of learning functions with a larger range such as ℕ or ℝ. In particular relatively few results exist about the general structure of common models for function learning, and there are only very few nontrivial function classes for which positive learning results have been exhibited in any of these models. We introduce in this paper the notion of a binary branching adversary tree for function learning, which allows us to give a somewhat surprising equivalent characterization of the optimal learning cost for learning a class of real-valued functions (in terms of a max-min definition which does not involve any “learning” model). Another general structural result of this paper relates the cost for learning a union of function classes to the learning costs for the individual function classes. Furthermore, we exhibit an efficient learning algorithm for learning convex piecewise linear functions from ℝ d into ℝ. Previously, the class of linear functions from ℝ d into ℝ was the only class of functions with multidimensional domain that was known to be learnable within the rigorous framework of a formal model for online learning. Finally we give a sufficient condition for an arbitrary class $$\mathcal{F}$$ of functions from ℝ into ℝ that allows us to learn the class of all functions that can be written as the pointwise maximum ofk functions from $$\mathcal{F}$$ . This allows us to exhibit a number of further nontrivial classes of functions from ℝ into ℝ for which there exist efficient learning algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00993410
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    On the Complexity of Function Learning (1995)
    Springer
    Machine learning 18 (1995), S. 187-230 
    Details
    ISSN: 0885-6125
    Keywords: computational learning theory ; on-line learning ; mistake-bounded learning ; function learning
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract The majority of results in computational learning theory are concerned with concept learning, i.e. with the special case of function learning for classes of functions with range {0, 1}. Much less is known about the theory of learning functions with a larger range such as $$\mathbb{N}$$ or $$\mathbb{R}$$ . In particular relatively few results exist about the general structure of common models for function learning, and there are only very few nontrivial function classes for which positive learning results have been exhibited in any of these models. We introduce in this paper the notion of a binary branching adversary tree for function learning, which allows us to give a somewhat surprising equivalent characterization of the optimal learning cost for learning a class of real-valued functions (in terms of a max-min definition which does not involve any “learning” model). Another general structural result of this paper relates the cost for learning a union of function classes to the learning costs for the individual function classes. Furthermore, we exhibit an efficient learning algorithm for learning convex piecewise linear functions from $$\mathbb{R}^d $$ into $$\mathbb{R}$$ . Previously, the class of linear functions from $$\mathbb{R}^d $$ into $$\mathbb{R}$$ was the only class of functions with multidimensional domain that was known to be learnable within the rigorous framework of a formal model for online learning. Finally we give a sufficient condition for an arbitrary class $$\mathcal{F}$$ of functions from $$\mathbb{R}$$ into $$\mathbb{R}$$ that allows us to learn the class of all functions that can be written as the pointwise maximum of k functions from $$\mathcal{F}$$ . This allows us to exhibit a number of further nontrivial classes of functions from $$\mathbb{R}$$ into $$\mathbb{R}$$ for which there exist efficient learning algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1022851430087
    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...