KAIST Discrete Math Seminar

The Curry–Howard correspondence says that there is an isomorphic relation between intuitionistic logic and a constructive type theory. The basic idea is that intuitionistic proofs of mathematical formulas contain constructive information to prove them and that the information can be represented as concrete terms in a constructive type theory. One can then use these information and terms to extract computer programs from proofs. The resulting programs are error-free and correct in the sense that they satisfy the prescribed specifications. That means it is certified that the programs work as expected. This talk will explain the basic idea of Curry-Howard correspondence and its use in extracting certified programs.

The purpose of this talk is to study the finite field analog of the Erdős distance problem. First, the conjecture and known results on the problem are reviewed. Second, we introduce basic skills to deduce results on the problem. Finally, we address how to improve currently known results on the Erdős distance problem.

In patrolling problems, several mobile agents move inside a given region and try to cooperate so that every designated point in the region is (perpetually) visited sufficiently often (that is, no point should be left unattended for any time period of specified length). There are many variants of this problem: the agents may have the same or different speeds; the terrain may be a line, a cycle, or more general graphs; the points to be visited may be the whole or a (finite) part of the terrain. Problems of this kind are studied in different contexts with various motivations, but finding an optimal patrolling strategy is not straightforward, even in very simple settings. For example, the optimal patrolling of a line segment by several agents is not always achieved by the simple strategy where each agent moves back and forth in a sub-segment of length proportional to its speed. This talk will introduce some positive and negative results and open questions about properties of and algorithms for optimal patrolling.

For a tournament T, the chromatic number of T is the minimum number of transitive sets with union V(T). We say a set ? of tournaments is heroic if there exists c such that every tournament excluding all members of ? has chromatic number at most c. Berger et al. explicitly characterized all heroic sets of size one. In this talk, we study heroic sets of size two. This is a joint work with Maria Chudnovsky, Ilhee Kim, and Paul Seymour.

This short course covers selected topics in mathematical models arising in the analysis of transportation systems and networks. We will briefly review basic topics in network optimization and then will proceed to commonly used models for logistics service planning by private companies as well as management of public vehicular infrastructure. This course will cover topics such as risk-averse routing, vehicle routing problems, network user equilibrium, road pricing and network design, location problems, and modeling drivers’ decision making processes, with applications in bike-sharing services, electric-vehicle charging, hazardous materials transportation, and congestion mitigation. This course will also introduce some computational tools available in the Julia Language.Outline (subject to change)</p>

1. Basic Topics in Network Optimization
– Shortest Path Problem
– Minimum Cost Network Flow
– Transportation Problem
– Multi-Commodity Network Flow
– Intro to Julia and JuMP

2. Risk-Averse Routing
– Robust Shortest Path Problem
* Scenario-based
* Interval data
* Polyhedral uncertainty set
* Two multiplicative coefficients
* Julia: RobustShortestPath.jl
– Value-at-Risk
– Conditional Value-at-Risk
– Worst-case Conditional Value-at-Risk

3. Vehicle Routing Problem
– Traveling Salesman Problem
– Subtour Elimination
– Vehicle Routing Problem
– VRP with Time Windows
– Green VRP / Electric-VRP
– Energy Minimizing VRP
– Medical-Waste Collection VRP
– Bike-Balancing VRP

4. Network User Equilibrium
– System Optimum
– User Equilibrium
* Complementarity Problem
* Variational Inequality Problem
– Computation
* Frank-Wolfe Algorithm
* Julia: VariationalInequality.jl
* Julia: Complementarity.jl
* Julia: TrafficAssignment.jl
– Stochastic User Equilibrium
– Braess Paradox
– Price of Anarchy

5. Network Regulation
– Bilevel Optimization
– Road Pricing
– Network Design
– Inverse Optimization for Road Pricing
– Single-level Reformulation
– Leader-Follower Game

6. Location Problems
– Classic Location Problems
* p-median
* p-center
* set-covering
* maximal covering
* fixed-charge facility location
* two-stage problem
– Hub Location Problems
* p-hub center
* hub-covering
* p-hub median
– Lagrangian Relaxation
– Flow-Capturing Location Problem
– Flow-Refueling Location Problem
– Infrastructure Planning for Electric Vehicles

7. Generalized Bounded Rationality
– Satisficing Behavior
– Perception-Error
– Equivalence
– Comparison with Random-Utility Model
– Monte-Carlo Method
– Julia: PathDistribution.jl
– Application in Robust Network Design