skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: A Generalization of Parking Functions Allowing Backward Movement
Classical parking functions are defined as the parking preferences for $$n$$ cars driving (from west to east) down a one-way street containing parking spaces labeled from $$1$$ to $$n$$ (from west to east). Cars drive down the street toward their preferred spot and park there if the spot is available. Otherwise, the car continues driving down the street and takes the first available parking space, if such a space exists. If all cars can park using this parking rule, we call the $$n$$-tuple containing the cars' parking preferences a parking function.   In this paper, we introduce a generalization of the parking rule allowing cars whose preferred space is taken to first proceed up to $$k$$ spaces west of their preferred spot to park before proceeding east if all of those $$k$$ spaces are occupied. We call parking preferences which allow all cars to park under this new parking rule $$k$$-Naples parking functions of length $$n$$. This generalization gives a natural interpolation between classical parking functions, the case when $k=0$, and all $$n$$-tuples of positive integers $$1$$ to $$n$$, the case when $$k\geq n-1$$. Our main result provides a recursive formula for counting $$k$$-Naples parking functions of length $$n$$. We also give a characterization for the $k=1$ case by introducing a new function that maps $$1$$-Naples parking functions to classical parking functions, i.e. $$0$$-Naples parking functions. Lastly, we present a bijection between $$k$$-Naples parking functions of length $$n$$ whose entries are in weakly decreasing order and a family of signature Dyck paths.  more » « less
Award ID(s):
1659138
PAR ID:
10417377
Author(s) / Creator(s):
; ; ; ; ; ;
Date Published:
Journal Name:
The Electronic Journal of Combinatorics
Volume:
27
Issue:
1
ISSN:
1077-8926
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Random Structures & Algorithms)
    null (Ed.)
    In the parking model on ℤd, each vertex is initially occupied by a car (with probability p) or by a vacant parking spot (with probability 1−p). Cars perform independent random walks and when they enter a vacant spot, they park there, thereby rendering the spot occupied. Cars visiting occupied spots simply keep driving (continuing their random walk). It is known that p=1/2 is a critical value in the sense that the origin is a.s. visited by finitely many distinct cars when p<1/2, and by infinitely many distinct cars when p≥1/2. Furthermore, any given car a.s. eventually parks for p≤1/2 and with positive probability does not park for p>1/2. We study the subcritical phase and prove that the tail of the parking time τ of the car initially at the origin obeys the bounds exp(−C1tdd+2)≤ℙp(τ>t)≤exp(−c2tdd+2) for p>0 sufficiently small. For d=1, we prove these inequalities for all p∈[0,1/2). This result presents an asymmetry with the supercritical phase (p>1/2), where methods of Bramson--Lebowitz imply that for d=1 the corresponding tail of the parking time of the parking spot of the origin decays like e−ct√. Our exponent d/(d+2) also differs from those previously obtained in the case of moving obstacles. 
    more » « less
  2. ; ; (, International Conference on Combinatorial Optimization and Applications)
    We consider the online transportation problem set in a metric space containing parking garages of various capacities. Cars arrive over time, and must be assigned to an unfull parking garage upon their arrival. The objective is to minimize the aggregate distance that cars have to travel to their assigned parking garage. We show that the natural greedy algorithm, augmented with garages of k ≥ 3 times the capacity, is (1 + 2/k-2)-competitive. 
    more » « less
  3. ; ; (, Annals of Combinatorics)
    Abstract A classical parking function of lengthnis a list of positive integers$$(a_1, a_2, \ldots , a_n)$$ ( a 1 , a 2 , … , a n ) whose nondecreasing rearrangement$$b_1 \le b_2 \le \cdots \le b_n$$ b 1 ≤ b 2 ≤ ⋯ ≤ b n satisfies$$b_i \le i$$ b i ≤ i . The convex hull of all parking functions of lengthnis ann-dimensional polytope in$${\mathbb {R}}^n$$ R n , which we refer to as the classical parking function polytope. Its geometric properties have been explored in Amanbayeva and Wang (Enumer Combin Appl 2(2):Paper No. S2R10, 10, 2022) in response to a question posed by Stanley (Amer Math Mon 127(6):563–571, 2020). We generalize this family of polytopes by studying the geometric properties of the convex hull of$${\textbf{x}}$$ x -parking functions for$${\textbf{x}}=(a,b,\dots ,b)$$ x = ( a , b , ⋯ , b ) , which we refer to as$${\textbf{x}}$$ x -parking function polytopes. We explore connections between these$${\textbf{x}}$$ x -parking function polytopes, the Pitman–Stanley polytope, and the partial permutahedra of Heuer and Striker (SIAM J Discrete Math 36(4):2863–2888, 2022). In particular, we establish a closed-form expression for the volume of$${\textbf{x}}$$ x -parking function polytopes. This allows us to answer a conjecture of Behrend et al. (2022) and also obtain a new closed-form expression for the volume of the convex hull of classical parking functions as a corollary. 
    more » « less
  4. (, Latin and American Algorithms, Graphs and Optimization Symposium)
    We consider the online transportation problem set in a metric space containing parking garages of various capacities. Cars arrive over time, and must be assigned to an unfull parking garage upon their arrival. The objective is to minimize the aggregate distance that cars have to travel to their assigned parking garage. We show that the natural greedy algorithm, augmented with garages of k >= 3 times the capacity, is O(1)-competitive. 
    more » « less
  5. ; ; ; ; ; (, 2018 IEEE International Conference on Cognitive Computing (ICCC))
    The smart parking industry continues to evolve as an increasing number of cities struggle with traffic congestion and inadequate parking availability. For urban dwellers, few things are more irritating than anxiously searching for a parking space. Research results show that as much as 30% of traffic is caused by drivers driving around looking for parking spaces in congested city areas. There has been considerable activity among researchers to develop smart technologies that can help drivers find a parking spot with greater ease, not only reducing traffic congestion but also the subsequent air pollution. Many existing solutions deploy sensors in every parking spot to address the automatic parking spot detection problems. However, the device and deployment costs are very high, especially for some large and old parking structures. A wide variety of other technological innovations are beginning to enable more adaptable systems-including license plate number detection, smart parking meter, and vision-based parking spot detection. In this paper, we propose to design a more adaptable and affordable smart parking system via distributed cameras, edge computing, data analytics, and advanced deep learning algorithms. Specifically, we deploy cameras with zoom-lens and motorized head to capture license plate numbers by tracking the vehicles when they enter or leave the parking lot; cameras with wide angle fish-eye lens will monitor the large parking lot via our custom designed deep neural network. We further optimize the algorithm and enable the real-time deep learning inference in an edge device. Through the intelligent algorithm, we can significantly reduce the cost of existing systems, while achieving a more adaptable solution. For example, our system can automatically detect when a car enters the parking space, the location of the parking spot, and precisely charge the parking fee and associate this with the license plate number. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email