Discrete Newton Method

Zhao Zhang () and Xiaohui Huang
Additional contact information
Zhao Zhang: Zhejiang Normal University
Xiaohui Huang: Zhejiang Normal University

A chapter in Nonlinear Combinatorial Optimization, 2019, pp 37-56 from Springer

Abstract: Abstract Newton method is a classic and powerful method in continuous nonlinear optimization. However in this chapter, we introduce its counterpart in combinatorial optimization: discrete Newton method, and show that there exists a strong polynomial time algorithm for finding the root of a piecewise linear decreasing function, where the number of pieces is exponential. Then we show how to apply it in solving linear fractional combinatorial optimization problem, inverse combinatorial problem, and bottleneck expansion problem.

Date: 2019
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-030-16194-1_2

Ordering information: This item can be ordered from
http://www.springer.com/9783030161941

DOI: 10.1007/978-3-030-16194-1_2

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().