5 papers · 1 filter
Maximum Coverage -Antichains and Chains: A Greedy Approach
Manuel Cáceres, Andreas Grigorjew, Wanchote Po Jiamjitrak +1
Given an acyclic digraph and a positive integer , the problem of Maximum Coverage -Antichains (resp. Chains) denoted as MA- (resp. MC-) asks to find set…
Simple approximation algorithms for Polyamorous Scheduling
Yuriy Biktairov, Leszek Gąsieniec, Wanchote Po Jiamjitrak +3
In Polyamorous Scheduling, we are given an edge-weighted graph and must find a periodic schedule of matchings in this graph which minimizes the maximal weighted waiting time betwee…
Width Parameters for Minimum Flow Decomposition
Andreas Grigorjew, Wanchote Jiamjitrak, Brendan Mumey +1
Minimum flow decomposition (MFD) is the strongly NP-hard problem of finding a smallest set of integer weighted - paths in an - DAG whose weighted sum is equal to a…
The Group Access Bounds for Binary Search Trees
Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak +2
The access lemma (Sleator and Tarjan, JACM 1985) is a property of binary search trees that implies interesting consequences such as static optimality, static finger, and working se…
Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition
Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak +3
Greedy BST (or simply Greedy) is an online self-adjusting binary search tree defined in the geometric view ([Lucas, 1988; Munro, 2000; Demaine, Harmon, Iacono, Kane, Patrascu, SODA…