Abstract We consider a natural generalization of classical scheduling problems to a setting in which using a time unit for processing a job causes some timedependent cost, the timeofuse tariff, which must be paid in addition to the standard scheduling cost. We focus on preemptive singlemachine scheduling and two classical scheduling cost functions, the sum of (weighted) completion times and the maximum completion time, that is, the makespan. While these problems are easy to solve in the classical scheduling setting, they are considerably more complex when timeofuse tariffs must be considered. We contribute optimal polynomialtime algorithms and best possible approximation algorithms. For the problem of minimizing the total (weighted) completion time on a single machine, we present a polynomialtime algorithm that computes for any given sequence of jobs an optimal schedule, i.e., the optimal set of time slots to be used for preemptively scheduling jobs according to the given sequence. This result is based on dynamic programming using a subtle analysis of the structure of optimal solutions and a potential function argument. With this algorithm, we solve the unweighted problem optimally in polynomial time. For the more general problem, in which jobs may have individual weights, we develop a polynomialtimemore »
An Efficient Algorithm for Routing and Recharging of Electric Vehicles
In this paper, we address the routing and recharging problem for electric vehicles, where charging nodes have heterogeneous prices and waiting times, and the objective is to minimize the total recharging cost. We prove that the problem is NPhard and propose two algorithms to solve it. The first, is an algorithm which obtains the optimal solution in pseudopolynomial time. The second, is a polynomial time algorithm that obtains a solution with the total cost of recharging not greater than the optimal cost for a more constrained instance of the problem with the maximum waiting time of (1−ϵ)⋅W , where W is the maximum allowable waiting time.
 Award ID(s):
 1724227
 Publication Date:
 NSFPAR ID:
 10288206
 Journal Name:
 COCOA 2020: Combinatorial Optimization and Applications
 Sponsoring Org:
 National Science Foundation
More Like this


We study the problem of maximizing a nonmonotone submodular function subject to a cardinality constraint in the streaming model. Our main contribution is a singlepass (semi)streaming algorithm that uses roughly $O(k / \varepsilon^2)$ memory, where $k$ is the size constraint. At the end of the stream, our algorithm postprocesses its data structure using any offline algorithm for submodular maximization, and obtains a solution whose approximation guarantee is $\frac{\alpha}{1+\alpha}\varepsilon$, where $\alpha$ is the approximation of the offline algorithm. If we use an exact (exponential time) postprocessing algorithm, this leads to $\frac{1}{2}\varepsilon$ approximation (which is nearly optimal). If we postprocess with the algorithm of \cite{buchbinder2019constrained}, that achieves the stateoftheart offline approximation guarantee of $\alpha=0.385$, we obtain $0.2779$approximation in polynomial time, improving over the previously best polynomialtime approximation of $0.1715$ due to \cite{feldman2018less}. It is also worth mentioning that our algorithm is combinatorial and deterministic, which is rare for an algorithm for nonmonotone submodular maximization, and enjoys a fast update time of $O(\frac{\log k + \log (1/\alpha {\varepsilon^2})$ per element.

Waiting at the right location at the right time can be critically important in certain variants of timedependent shortest path problems. We investigate the computational complexity of timedependent shortest path problems in which there is either a penalty on waiting or a limit on the total time spent waiting at a given subset of the nodes. We show that some cases are nondeterministic polynomialtime hard, and others can be solved in polynomial time, depending on the choice of the subset of nodes, on whether waiting is penalized or constrained, and on the magnitude of the penalty/waiting limit parameter. Summary of Contributions: This paper addresses simple yet relevant extensions of a fundamental problem in Operations Research: the Shortest Path Problem (SPP). It considers timedependent variants of SPP, which can account for changing traffic and/or weather conditions. The first variant that is tackled allows for waiting at certain nodes but at a cost. The second variant instead places a limit on the total waiting. Both variants have applications in transportation, e.g., when it is possible to wait at certain locations if the benefits outweigh the costs. The paper investigates these problems using complexity analysis and algorithm design, both tools from the fieldmore »

We present an $m^{4/3}+o(1) \log W$ time algorithm for solving the minimum cost flow problem in graphs with unit capacity, where W is the maximum absolute value of any edge weight. For sparse graphs, this improves over the best known running time for this problem and, by wellknown reductions, also implies improved running times for the shortest path problem with negative weights, minimum cost bipartite $b$matching when $\b\_1 = O(m)$, and recovers the running time of the currently fastest algorithm for maximum flow in graphs with unit capacities (LiuSidford, 2020). Our algorithm relies on developing an interior point method–based framework which acts on the space of circulations in the underlying graph. From the combinatorial point of view, this framework can be viewed as iteratively improving the cost of a suboptimal solution by pushing flow around circulations. These circulations are derived by computing a regularized version of the standard Newton step, which is partially inspired by previous work on the unitcapacity maximum flow problem (LiuSidford, 2019), and subsequently refined based on the very re cent progress on this problem (LiuSidford, 2020). The resulting step problem can then be computed efficiently using the recent work on $l_p$norm minimizing flows (KyngPengSachdeva Wang, 2019).more »

We present an m^{4/3+o(1)} log W time algorithm for solving the minimum cost flow problem in graphs with unit capacity, where W is the maximum absolute value of any edge weight. For sparse graphs, this improves over the best known running time for this problem and, by wellknown reductions, also implies improved running times for the shortest path problem with negative weights, minimum cost bipartite bmatching when b_1 = O(m), and recovers the running time of the currently fastest algorithm for maximum flow in graphs with unit capacities (LiuSidford, 2020). Our algorithm relies on developing an interior point method–based framework which acts on the space of circulations in the underlying graph. From the combinatorial point of view, this framework can be viewed as iteratively improving the cost of a suboptimal solution by pushing flow around circulations. These circulations are derived by computing a regularized version of the standard Newton step, which is partially inspired by previous work on the unitcapacity maximum flow problem (LiuSidford, 2019), and subsequently refined based on the very recent progress on this problem (LiuSidford, 2020). The resulting step problem can then be computed efficiently using the recent work on l_pnorm minimizing flows (KyngPengSachdevaWang, 2019). We obtainmore »