Optimizing some constructions with bars: new geometric knapsack problems

S. Bereg (), J. M. Díaz-Báñez (), D. Flores-Peñaloza (), S. Langerman (), P. Pérez-Lantero () and J. Urrutia ()
Additional contact information
S. Bereg: University of Texas at Dallas
J. M. Díaz-Báñez: Universidad de Sevilla
D. Flores-Peñaloza: Universidad Nacional Autónoma de México
S. Langerman: Université Libre de Bruxelles (ULB)
P. Pérez-Lantero: Universidad de Valparaíso
J. Urrutia: Universidad Nacional Autónoma de México

Journal of Combinatorial Optimization, 2016, vol. 31, issue 3, No 15, 1160-1173

Abstract: Abstract A set of vertical bars planted on given points of a horizontal line defines a fence composed of the quadrilaterals bounded by successive bars. A set of bars in the plane, each having one endpoint at the origin, defines an umbrella composed of the triangles bounded by successive bars. Given a collection of bars, we study how to use them to build the fence or the umbrella of maximum total area. We present optimal algorithms for these constructions. The problems introduced in this paper are related to the Geometric Knapsack problems (Arkin et al. in Algorithmica 10:399–427, 1993) and the Rearrangement Inequality (Wayne in Scripta Math 12(2):164–169, 1946).

Keywords: Geometric optimization; Combinatorial optimization; Inequalities; Optimal algorithms (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9816-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:jcomop:v:31:y:2016:i:3:d:10.1007_s10878-014-9816-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9816-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().