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
  • 1
    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
  • 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 $$\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
  • 3
    Electronic Resource
    Electronic Resource
    The Travelling Salesman Problem on Permuted Monge Matrices (1998)
    Springer
    Journal of combinatorial optimization 2 (1998), S. 333-350 
    Details
    ISSN: 1573-2886
    Keywords: travelling salesman problem ; subtour patching ; combinatorial optimization ; computational complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We consider traveling salesman problems (TSPs) with a permuted Monge matrix as cost matrix where the associated patching graph has a specially simple structure: a multistar, a multitree or a planar graph. In the case of multistars, we give a complete, concise and simplified presentation of Gaikov's theory. These results are then used for designing an O(m3 + mn) algorithm in the case of multitrees, where n is the number of cities and m is the number of subtours in an optimal assignment. Moreover we show that for planar patching graphs, the problem of finding an optimal subtour patching remains NP-complete.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009768317347
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    A note on the complexity of the transportation problem with a permutable demand vector (1999)
    Springer
    Mathematical methods of operations research 50 (1999), S. 9-16 
    Details
    ISSN: 1432-5217
    Keywords: Key words: Transportation problem ; permutable demand vector ; computational complexity ; minimum weight f-factor problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract. In this note we investigate the computational complexity of the transportation problem with a permutable demand vector, TP-PD for short. In the TP-PD, the goal is to permute the elements of the given integer demand vector b=(b 1,…,b n) in order to minimize the overall transportation costs. Meusel and Burkard [6] recently proved that the TP-PD is strongly NP-hard. In their NP-hardness reduction, the used demand values b j, j=1,…,n, are large integers. In this note we show that the TP-PD remains strongly NP-hard even for the case where b j∈{0,3} for j=1,…,n. As a positive result, we show that the TP-PD becomes strongly polynomial time solvable if b j∈{0,1,2} holds for j=1,…,n. This result can be extended to the case where b j∈{κ,κ+1,κ+2} for an integer κ.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s001860050031
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    The Steiner Tree Problem in Kalmanson Matrices and in Circulant Matrices (1999)
    Springer
    Journal of combinatorial optimization 3 (1999), S. 51-58 
    Details
    ISSN: 1573-2886
    Keywords: Steiner tree ; Kalmanson matrix ; circulant matrix ; computational complexity ; graph algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We investigate the computational complexity of two special cases of the Steiner tree problem where the distance matrix is a Kalmanson matrix or a circulant matrix, respectively. For Kalmanson matrices we develop an efficient polynomial time algorithm that is based on dynamic programming. For circulant matrices we give an $$\mathcal{N}\mathcal{P}$$ -hardness proof and thus establish computational intractability.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009881510868
    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...