Archive for the ‘2016’ Category

Cyril Nicaud, Introduction to analytic combinatorics

Tuesday, October 4th, 2016
Introduction to analytic combinatorics
Cyril Nicaud
Laboratoire d’Informatique Gaspard Monge (LIGM), Université Paris-Est, France
2016/10/19 Wed 4PM-5PM
In classical combinatorics, sequences of positive integers are usually studied through their generating series. These formal power series can be used to classify the sequences, to obtain closed formulas for the number of object of a given size, …
Seeing the generating series as analytic functions, we can use tools of complex analysis (such as the residue theorem) to obtain, typically, an asymptotic equivalent to the sequence under consideration.
In this talk I will give a quick overview of the main results obtained in this field, from the automatic construction of generating series to some theorems coming from the theory of functions of a complex variable.
The talk will not assume any specific knowledge in combinatorics or complex analysis.

[SoC Colloquium]Akitoshi Kawamura, Open Problems in Optimal Patrolling

Saturday, October 1st, 2016

FYI: Colloquium, School of Computing

Open Problems in Optimal Patrolling
Akitoshi Kawamura (河村彰星)
University of Tokyo, Tokyo, Japan.
2016/10/10 Mon 4PM-6PM (E3-1 Room #1501)
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.

Doowon Koh (고두원), Introduction of the finite field Erdős distance problem

Saturday, October 1st, 2016
Introduction of the finite field Erdős distance problem
Doowon Koh (고두원)
Department of Mathematics, Chungbuk National University, Cheongju
2016/10/14 Fri 4PM-5PM
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.

Ringi Kim (김린기), Unavoidable subtournaments in tournaments with large chromatic number

Friday, September 2nd, 2016
Unavoidable subtournaments in tournaments with large chromatic number
Ringi Kim (김린기)
University of Waterloo, Waterloo, Ontario, Canada
2016/9/9 Fri 4PM-5PM
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.

Changhyun Kwon (권창현), Mathematical Models of Transportation Systems and Networks

Thursday, June 23rd, 2016

FYI: Short Course on “Mathematical Models of Transportation Systems and Networks” organized by Dept. of Industrial and Systems Engineering, KAIST. You need to bring your laptop to learn the programming in Julia.

Mathematical Models of Transportation Systems and Networks
Changhyun Kwon (권창현)
Industrial and Management Systems Engineering, University of South Florida
2016/7/5 10am-12am, 1:30pm-3:30pm
2016/7/6 10am-12am, 1:30pm-3:30pm
(Room 1501 of Bldg. E2)
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)

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